プロフィール

mathnegi

Author:mathnegi
ゆる~い人間です(*´ヮ`*)
宮城県在住~

カレンダー

07 | 2017/08 | 09
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

最新記事

全記事リスト

全ての記事を表示する

最新コメント

月別アーカイブ

カテゴリ

閲覧者数

検索フォーム

RSSリンクの表示

リンク

ブロとも申請フォーム

この人とブロともになる

QRコード

QR

電卓だよん♪

電 卓

お問い合わせはこちらまで~♪

名前:
メール:
件名:
本文:

受験ブログ 大学受験(指導・勉強法)へ

スポンサーサイト

--.--.-- --:--|スポンサー広告
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2014年日本数学オリンピック予選 第12問

2014.02.25 00:00|数学
どもども。


ついに最終問題ですねー。

今回は今年のJMO予選第12問を取り扱ってみます~


問題はこの辺などから~ 箱ドットおにおん2mini
http://www.imojp.org/challenge/old/jmo24yq.html


ここにきてようやく2014絡みの問題が出てきましたが,なかなか強烈です~
どうやって時間内に解くんだ!という感じです~

まぁ厳密な検証はさておいて,数学的直感に頼って答えの数値を叩き出すことくらいなら
もしかしたら出来るかもしれない,というかそういう能力を試されてたりするのでしょうか~

不等式の問題を解いてるはずが,選んだ方針によっては気付いたらなぜかグラフ理論の話になってる!
…という面白い問題ではありますので,しばらく考えこんでみる価値はあると思います~




というわけで中身に入りましょう~~


a_1, a_2, …,a_1000 はいずれも0以上で, a_1+a_2+…+a_1000=1 だそうですよ~
このとき (a_k)(a_ℓ) 型の項を適当に n 個取ってきて,それらを足した和を考えるのですが,
仮定を満たすどんな数列 {a_n} に対しても決まったこの n 個の和が必ず上から 1/2.014 で
押さえられてしまうようにしたいのだそうで,
そんな凄まじい n 個を選ぶことが出来るためには n がどんな値であればよいのでしょうか。
そんな n の最大値 m を求めてねーー という問題です~ sreep_dog.gif

数列 {a_n} ごとに選ぶ m 個を変えていいのではなく,
1回決めた m 個に対してどんな数列 {a_n} を持ってきても必ず成り立つ
というとても強気な主張が成りたたなければいけません。

1/2.014≒0.4965243 みたいです。
分母が2よりわずかにでかいので逆数は0.5よりわずかに小さいという感じですね~
このわずかな0.014のズレを巡って緻密な議論が要求されてくるという展開なんだろうか,
という雰囲気が漂います~


やっぱこういう問題はとりあえずテキトーーに手を動かしてみて
ベタな具体例を通した実験的考察から手掛かりを探ってみるのが良いでしょうねー rabi_happy.gif

ベタな例というのは, 1+0+0+…+0=1 とか
1/2+1/2+0+0…+0=1 とか 1/n+1/n+…+1/n+0+0+…+0=1 とか
1/1000+1/1000+…+1/1000=1 のようなのとかですかね。




まず, (a_k)(a_ℓ) 型の項たちの中に (a_k)^2 型の項が含まれていてはいけないという
ことに気づきましょーー wahakapa.gif
(a_k)^2 型の項が含まれていると,考察対象の和が 1/2.014 を越えてくるような
数列 {a_n} が存在します~

j1_20140217042646c62.jpg





次に見い出すべきは, (a_k)(a_ℓ) 型の項たちの中に同じ項(同じ (k,ℓ) を持つ項)が
あってはいけない
ということです~ ipon.gif
たとえば a_1a_2 という項は1回しか登場できません。もちろん a_2a_1 でもダメです~

 

j2_20140217042647c06.jpg
j3_20140217042648c76.jpg




(a_k)(a_ℓ) (k≠ℓ) 型の項たちは全部で C(1000,2) (←2項係数と思ってね)個しか
無いので,この時点で m≦C(1000,2) は確定です~
ただ, m=C(1000,2) で終わるほど単純な問題ではありません

0でないものが1個だけ,2個だけの具体例について見たので
次は一般の N について, N 個だけ0でないものがあるようなものから
何か条件を得てみたいと思います。
やはり 1/N+1/N+…+1/N+0+0+…0=1 (1/N が N 個) というものを
考察してみればいい気がするのですが,
ここで一応,0でないものが全部 1/N という形の数列を考察することの意義について考えておきます~ pampas_mov.gif


第 (N+1) 項以降全部0であるような数列については
C(1000,2) 個の (a_k)(a_ℓ) たちのうち何個かは0になってしまいます。
0にならずに生き残るのは,0でないもの同士をかけたものだけなので
高々 C(N,2) 個ということになります~
第 N 項まで全部0でないならぴったし C(N,2) 個です~

このとき, C(1000,2) 個(すなわち実質 C(N,2) 個)の (a_k)(a_ℓ) たちの総和が
最大になるのがちょうど N 個全部が 1/N になってるとき
なんです~ hanaji02.gif



j6_2014021704264928f.jpg
j4_20140217042648d27.jpg
j5_20140217042649250.jpg



N 個全部が 1/N になってる数列について
(a_k)(a_ℓ) たちの総和 (1/N)^2×C(N,2) が1/2.014以下であるならば,
0でない項が N 個以下であるようなどんな数列 {a_n} を持ってきても
C(1000,2) 個の (a_k)(a_ℓ) たちの総和は1/2.014以下である
ということがいえます~ hana14.gif

実際に (1/N)^2×C(N,2)≦1/2.014 を解くことで N≦143 が得られます~
つまり,もはや0以外である項数が143以下であるような数列は放っておいて大丈夫ということです~

厄介なのが,0でない項が144個以上ある数列です~
これらの数列に対して件の不等式が必ず成り立つようにするには
C(1000,2) 個ある (a_k)(a_ℓ) たちから何個かを取り除いてやらなければいけません

少なくともここまでの考察から, a_1,a_2,…,a_1000 の中から任意に144個
a_λ(1),a_λ(2),…,a_λ(1000) を選んできたとき,この144個を組合せてできる
C(144,2) 個の (a_λ(k))(a_λ(ℓ)) が件の不等式の左辺に全部は含まれていてはいけない

ことがいえます~ heart-ani01.gif
最低でも1個は抜け落ちているようにしなければいけないのです~


j7_20140217042718001.jpg

j8_2014021704271811c.jpg



j9_20140217042719f43.jpg

 j10_20140217042719320.jpg

  j11_201402170427206e8.jpg




さて,ここで a_1,a_2,…,a_1000 を1000個の点 A_1,A_2,…,A_1000 にそれぞれ対応させて
頂点数1000のグラフを考えてみることにしましょう~~ hana-ani03.gif
積 (a_k)(a_ℓ) は辺 A_kA_ℓ に対応するわけです~

そして頂点数144の部分完全グラフを含まないようなものに限定して考えていきます mushi.gif

件の不等式を成り立たせるような (a_k)(a_ℓ) たちの選び方に対応するグラフのうち
最も辺の数が多いものを求めれば良いことになります。


頂点数144の部分完全グラフを含まないようなグラフのうち
辺の数が最も多くなるもの(の1つ)を G としましょう~
G の辺の数を g 本とすると,現時点で m≦g であることが分かっています~


実は m=g になっている,というのが最終的な結論なんですが,
ここが数学的直感の働かせどころかもしれませんねー hiyoko04.gif



j12_20140217042721f84.jpg
j14_20140217042748f02.jpg



そんなわけで g を求めてみたいと思います~
一般に頂点数 n のグラフのうち,頂点数 r+1 の部分完全グラフを含まないようなものの中で
最も辺の数が多くなるものをグラフ理論業界では Turán graph と呼ぶらしいですね  
T(n,r) という記号を使うみたいです~
Turán graph の知識をあらかじめ持っている人であればこの後の g を求める部分の過程は
あっさりショートカットできるのでだいぶ楽だと思います~
といっても実際の試験場でそんな知識を有していた人が一体どれだけいたのかと~
グラフ理論の話は全然知らんので,自分も今回初めて知りましたよ~

参考:Turán graph:http://en.wikipedia.org/wiki/Tur%C3%A1n_graph
Turán's theorem:http://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem


今回の場合は T(1000,143) というやつを考えることになります~
これは具体的には1000個の頂点を,頂点7個ずつのグループ142個と6個のグループ1個の
計143個のグループに分けて,同じグループの頂点同士は一切辺で繋がず,
違うグループの頂点同士は全て辺で繋がっている
という,そういうグラフになっています~ hamu01.gif

グループの数が143個しか無いので,どのように144個を選んできても
必ず少なくとも2個は同じグループに属してる同士のものがあるため,
頂点数144の部分完全グラフは含みませんね~
いわゆる鳩ノ巣原理的な発想です。

何となく勘でこの形のグラフに辿り着くことも出来るかもしれませんね。

以下で,今述べたようなものが本当に G にあたるということ,およびこの G に対応する
(a_k)(a_ℓ) たちの総和が数列 {a_n} によらず1/2.014以下であることを確かめます



まず,2個の頂点 A_k と A_ℓ に対して,辺 A_kA_ℓ が結ばれていないとき,
A_k~A_ℓ と表してみたいと思います~

「同じグループに属する2頂点 A_k と A_ℓ に対して,は必ず A_k~A_ℓ が成り立つ」
というルールのもとに1000個の頂点をグループ分けしてみましょう~
一般にはこのルールに従ったグループ分けの方法は一意的ではありません。



j13_2014021704274783b.jpg



ここで第一に確認したいのは, G においては「~」が同値関係になっているということです~ hachi02.gif
ここでいう同値関係というのは必要十分とかいう意味の同値とは若干違って
反射律,対称律,推移律を満たす関係の方ですよ~。
高校数学の範囲の内容しか知らない人は誤解するかもしれませんね。
そういう人は一応こちらとか参照ということで~ 
同値関係:http://ja.wikipedia.org/wiki/%E5%90%8C%E5%80%A4%E9%96%A2%E4%BF%82

「~」が同値関係になっていることを確かめるのにここでは背理法を使います~
推移律が成り立つことを確かめるのが一番めんどくさいのですが,
この推移律が成り立たないぞ~~と仮定して矛盾を導く作戦でいきます。
推移律が成り立たないとすると G よりも辺数の多い新グラフ G´ が
新たに構成できてしまうという理由のもとに矛盾を引き出します~ zashiki.gif


j15_20140217042748623.jpg

j16_20140217042749ab1.jpg


この場合分けは,要は d(A_i), d(A_j), d(A_k) の中でどれが一番でかいのか
という点に着目しています~~

d(A_j) よりも d(A_i) または d(A_k) の方がでかいときは
A_j を一回捨てて,代わりに A_k のコピーを加えてしまえばよく,
逆に d(A_j) が一番でかいときは, A_i と A_k を捨てて A_j のコピー2つを加えるとよいのです~

このような操作をしても頂点数144の部分完全グラフは相変わらず含まないことに注意してくださいねー

j17_2014021704275056c.jpg
j18_20140217042750a3e.jpg


j19_20140217042817c8f.jpg




以上から G において 「~」 が同値関係になっていることが分かりました~

このことにより, G においては1000個の頂点が一意的に同値な頂点たちごとのグループに
類別されることになります~。したがって,
・同じグループに属す頂点同士は辺で繋がれていない
・互いに違うグループに属す頂点同士は全て辺で繋がれている

ということがいえます whale.gif

しかし,まだ1つのグループに何個の頂点があるのか,グループ数はいくつあるのか
といった点は分かっていません。

そこで,グループの個数を s とし,各グループに F_1, F_2,…,F_s と名前を付けます。
更に, F_k に属す頂点の数を f_k とおいてみることにしましょう~
次に検証するのは, G においてはどの k , ℓ に対しても |f_k-f_ℓ| の値が0か1である
ということです~~

それを確かめる手段はさっきと同じで背理法です~
やはり,元のグラフ G より辺数の多い新グラフが構成できちゃうからダメなのよという流れです~
さっきは頂点の置き換えによって矛盾を引き出しましたが,今度は頂点の属すグループを変えるという
ことによって矛盾を引き出します~ c-08.gif


j20_201402170428189e8.jpg
j21_20140217042819d20.jpg
j22.jpg




だいぶ G の実体が見えてきました~
しかしまだ,グループ数 s を何にしたら良いのかが決まっていません~

s=2 だったら f_1=f_2=500 のように分けることになるし,
s=3 だったら f_1=334, f_2=f_3=333 のように分けることになるし,
s=4 だったら f_1=f_2=f_3=f_4=250 のように分けることになるでしょう。

グループ数を決めると,頂点個数の割り振り方は自動的に決まります。
同じグループの頂点同士は辺で結べないのだから,
グループ数が多い方が辺の数は多くなりそうですね。
それを確かめてみましょう~

なお,グループ数が144以上になると頂点数144の部分完全グラフを含んでしまうのでアウトです。
というわけで,グループ数143というのがきっと当たりなんだと思いますー aicon_bbs19.gif



j23.jpg
j24.jpg

j25.jpg

j26.jpg




これで答えの数値っぽいものが出てきましたね。
C(1000,2)=499500なので,そんなに離れてはいませんね。

最後に G に対応する (a_k)(a_ℓ) たちの総和が数列 {a_n} によらず
1/2.014以下であることを確かめましょう~~

グループ F_k に属する a_i たちの総和を α_k とおきます~
このとき, (a_k)(a_ℓ) たちの総和は α_kα_ℓ たちの総和に等しいことに着目します~ aicon156.gif

この和は,すべての k に対して α_k=1/143 になるときに最大になります


j27.jpg
j28.jpg




ようやく結論に辿り着いたーーー><

とても険しい問題でしたーー。

かなり大掛かりなことになってしまったので,恐らくもっとスマートな解法があるのだと思います。
数オリの過去問集や大数の特集ページとかには,きっとより鮮やかな解法が載ることでしょう xmas_cake.gif



ちなみに最後に出てきた 71/143 という分数は小数表示で
71/143=0.496503496503496503・・・・・・
となっていて答えの数値496503が繰り返される循環小数になっています cat_4.gif
何だか気持ち悪いですね。

71/143 を導き出した(N-1)/(2N) の式を 10^6 倍したものが
ちょうど Turán graph の辺数の評価式になっているからこんなことになってるんすね car2_tank.gif





  

関連記事
スポンサーサイト

テーマ:算数・数学の学習
ジャンル:学校・教育

コメント

非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。