第二問です。
2008人？？なにやら、見たことのあるような、無いような問題・・・
どうやら、今年の数学オリンピックは丸い机に座るのが好きなのか・・・
そして、前回は右隣だったような・・・
（
数学オリンピック予選第10問）
正直言って、こういう問題苦手です。
こと数学オリンピックのような難問・奇問は、問題文が短ければ短いほどヒントを見つけにくい為、難しいと言いますが、私は長い問題はあまり好きではありません。
この問題を解くのと、2008人が座れる円形の机を作るのとどちらの方が難しいのか？
では、解答してみます。
このままだと、何ターンなのか想像もつきませんね。
一度、実験してみましょう。
勝手に左周りに番号をつけて、１，２，３の席の人は赤いカード２枚。
他は、皆白いカードしか持っていないとします。
こんな感じですね。
という事は次のターンは
2ターン目
3ターン目
ってな感じですね。
どうやら、この調子で行くと、７ターン目で一枚ずつになる。
他に例えば
こん感じだったら、
1ターン目は
2ターン目は
このままだと、どうやら７ターンで終了しそう。
なんとなく、見えてきたような気がする。
なるべく、ターン数が大きくなるようにするには
「赤いカードを少なくとも１枚以上持っている人が並んで座れば座るほど、ターン数が大きくなる」おそらく、こんな感じに座れば最大になる。
この時、かかるターン数は2007ターン。
これが最大値をとるっぽい。ちなみに、
この場合でも2007ターン数かかる。ここで、2007ターンが最大値である事を証明する。
証明すべき事は
①2007ターンかかるカードの配り方が存在する。
②2008ターン以上かかる事はない。これが示せればよい。
実際に、①に関してはわかっているので問題は②である。
（補題）
2008ターン以上かかる配り方は存在しない。まず、白いカードを1枚以上持っている人は、その1枚はずっと動かないと考える。
要するに、次のターンで赤いカードが来ても、白いカードが来ても、そのカードを次のターンに渡す事になります。
赤いカード2枚持っている人に焦点を当ててみると、赤いカード2枚持っている人は、初めて白いカードが来た時点で、その白いカードが固定される。
そして、2008枚の白いカードが全て固定されるされるターン数を考えてみる。
もし、2008ターン以上かかって、題意を満たす状態になる時、ある固定されていない白いカードは2008ターン後には、最初に持っていた人に戻ってくる事になる。白いカードが、2008人のプレーヤー全てに固定されなかったという事は、全ての人が赤いカードと白いカードを1枚ずつ持っている状態になっている。これは、2008人のプレーヤーが2008枚の赤と2008枚の白いカードを配っている状態ではありえない。
要するに2008ターン以上で題意が成立することはありえない。
従って、最大のターン数は2007回である。
～一言～
何とも言いがたい問題でした・・・
こういう問題は嫌いです・・・
よろしければ、クリックお願いします⇒
「数学ブログ」
ついでに、こちらも参加しております⇒
「人気ブログランキング」
« 2008年日本数学オリンピック本選 第三問 l ホーム l 2008年日本数学オリンピック本選 第一問 »
解答だけ見てたら解けそうに思えそうだが、
実際にはなかなか解けない。
やはり難しい問題です。
確かに難問です。奇問ですかね・・・？
答えは概ね理解していても、それを説明しにくい。
説明する言葉を選べない。
どこまでを周知の事実とするのか？
これって本当に証明になってるの？
という所が、アルゴリズムの難しさですね。
こういうのは本当に難しいです。