2013年07月29日

2013年国際数学オリンピックの問題を解いてみよう

7月23日、24日にコロンビアで国際数学オリンピック(imo2013)が行われた。日本代表の6名は、すべて銀メダルをとり、国別では11位だったと報じられている。残念なことに、数学オリンピックは、どんな問題が出て選手がどうやって解いたのかという内容について、関心をもたれることが少ない。問題は公開されていることだし、いくつか解いてみましょう。

数学オリンピックは、高校生以下を対象とした大会で、おおむね高校1年くらいまでの範囲で解ける問題が出題される。日本では、国内予選 → 国内本選 → 合宿選抜、をへて6名の代表が選ばれる。

国際大会では、4時間30分で3問の試験を2回、あわせて6問を解く。上位1/12には金メダル、つぎの2/12は銀メダル、そのつぎの3/12には銅メダルが与えられる。

今年の問題は、下記のページから、2013 → Japanese → Download で読める。
http://www.imo-official.org/problems.aspx

問題1
任意の正の整数の組(k, n)に対して,ある k 個の(相異なるとは限らない)正の整数 m1, m2, ..., mk が存在して

e6e3d9183a52868bdbb9a3c45c2948f3745eaace.gif

となることを示せ.

解答例
a(i)=n+i-1 とし、p を k よりも小さな正整数とする。数列 a(1), a(1), ...a(2k-1) について考える。

この数列から部分列、a(i), ...a(j) を取り除いて出来る数列のペア a(1), ..., a(i-1); a(j+1), ..., a(2k-1) が次をみたすとき、これを p-数列と呼ぶことにする。

@ a(i) は 2p で割り切れる.
A a(j) は 2p で割った余りが -1.
B 左右の数列の項数の和が 2p-1.
ただし、a(i)=a(1) のときは、左の数列が存在しないが、これも p-数列と考える。a(j)=a(2k-1) も同じ。

p>1 の場合について考える。p-数列は、左右どちらか一方の数列のみ、項数が 2p-1以上になる。そこで、次の操作を考える。

A 左の数列の項数が2p-1以上であるとき。a(i-1) は 2p-1 で割った余りが -1 であるので、a(i-2p-1) は 2p-1 で割り切れる。そこで、左の数列から、a(i-2p-1), ..., a(i-1) を取り除く。

B 右の数列の項数が2p-1以上であるとき。a(j+1) は 2p-1 で割り切れる。a(j+2p-1)は 2p-1 で割った余りが、-1 である。そこで、右の数列から、a(j+1), ..., a(j+2p-1) を取り除く。

A,Bのいずれも、項数 2p-1 の数列を取り除くので、残った数列の項数は 2p-1-1 であり、(p-1)-数列を得る。

さて、元の数列において、a(1), ..., a(2k-1) のどれか1つは 2k-1 で割り切れる。それを a(i) とする。a(i+2k-1-1) は 2k-1 で割った余りが -1 である。そこで、数列 a(i), ..., a(i+2k-1-1) を取り除くと、(k-1)-数列を得る。

さらに、上述の操作を k-2 回繰り返すと、ただ1個の項が残る。したがって、元の数列は、a(i)=2pm, a(i+1)=2pm+1, ..., a(i+2p-1)=2pm+2p-1 (m は正整数)という形の数列を k 個つなげたものである。

f(x)=(x+1)/x とすると、f(a(i))f(a(i+1)) ...f(a(i+2p-1))=(2pm+2p)/2pm=f(m) である。

問題にもどって、1+(2k-1)/n=(n+2k-1)/n=f(a(1))f(a(2)) ...f(a(2k-1) であるから、1+(2k-1)/n=f(m1)f(m2) ...f(mk) となる m1, m2, ..., mk が存在する。

問題5
>0 を正の有理数の集合、Rを実数の集合とする。f:Q>0→Rを次の3つの条件をみたす関数とする:

(i) すべての x, y∈Q>0 に対して、f(x)f(y)≧f(xy),
(ii) すべての x, y∈Q>0 に対して、f(x+y)≧f(x)+f(y),
(iii) ある有理数 a>1 が存在して、f(a)=a.

このとき、すべての x∈Q>0 に対して、f(x)=x となることを示せ。

解答例
(i)より f(a)f(1)≧f(a) ⇔ af(1)≧a ⇔ f(1)≧1 …@
(ii)より f(x+x+ ...+x)≧f(x)+f(x)+ ...+f(x) であるから、正整数 m に対して、f(mx)≧mf(x) …A
x=1 とすると@より、f(m)≧m …B
(i)とAから、f(m)f(x)≧mf(x) ⇔ {f(m)-m}f(x)≧0 …C
Aの x に x/m を代入して、f(x)≧mf(x/m) より f(x)/m≧f(x/m) …D

次ぎに、すべての x∈Q>0 に対して、f(x)≧0 であることを示す。Bから、つぎの2通りについて考えればよい。

CaseI すべての正整数 m に対して、f(m)=m である場合。
ある正の有理数ν∈Q>0に対して、f(ν)≦0 であったとしよう。ν=p/q (p, q は正整数)とすると、f(p)=f(qν)≦f(q)f(ν)≦0 となってBに矛盾。したがって、すべての x∈Q>0 に対して、f(x)>0

CaseII ある正整数 m に対して、f(m)>m である場合。
Cより、すべての x∈Q>0 に対して、f(x)≧0.

x, y∈Q>0 が x>y をみたすとき、f(x)≧f(x-y)+f(y) であるから、f(x)≧f(y) である。よって f(x) は単調に増加する。

さて、ある b∈Q>0 が f(b)>b をみたしていたと仮定する。★

n を正整数、βn=an/b、[an/b] を、an/b を超えない最大の整数とする。
βn/[βn]≧1 かつ n → +∞ のとき、βn/[βn] → 1 である。したがって、bn=an/[βn] とすれば、bn≧b かつ n → +∞ のとき、 bn → b である。よって、f(b)>bn≧b となる bn が存在する。…E

(i)より、an=f(a)n≧f(an)
Dをもちいて、an/[βn]≧f(an)/[βn]≧f(an/[βn]).よって、bn≧f(bn)…F

Eより、bn≧b であるから、f(x)の単調性により、f(bn)≧f(b).これと、Fよりbn≧f(b) を得るが、これはEの f(b)>bn に矛盾。したがって★は成り立たず、すべての x∈Q>0 は x≧f(x) をみたす。

Bから、正整数 m については、f(m)=m となる。

ある c∈Q>0 が、c>f(c) をみたしていたとしよう。c=p/q(p, q は正整数)とすると、p=qc=f(qc)≦f(q)f(c)=qf(c)<qc=p となって矛盾。よって、すべての x∈Q>0 に対して、f(x)=x.


以下、よくある質問。

・東大の入試と国際数学オリンピック(IMO)の問題は、どっちが難しいか?
東大は国内の上位数千名を対象にしているが、IMOは上位数名レベル。IMOのほうが格段に難しい。

・数学者はIMOの問題が解けるのか?
できる人も、そうでない人もいる。時間制限を外せば、それなりに解ける。(F谷K治さんが試しに解いたときは、6問中2問は解く気にならなかったが、残りは全部解けて、銀メダル相当の成績だった、とどこかで聞いた。)




にほんブログ村 鳥ブログ 文鳥へ
posted by yanagisawa at 18:54| Comment(0) | TrackBack(0) | 日記
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/71466037

この記事へのトラックバック