2008年 日本数学オリンピック本選 第２問 解答例
赤いカードと白いカードがそれぞれ$${2008}$$枚ずつある。$${2008}$$人のプレイヤーが、それぞれこれらのカードのうち$${2}$$枚ずつを配られた状態で、内側を向いて円形になって座る。１回のターンで全員が同時に次のことを行う。
・赤いカードを１枚でも持っていれば赤いカード１枚を左隣のプレイヤーに渡す。赤いカードを１枚も持っていなければ白いカード１枚を左隣のプレイヤーに渡す。
このとき、初めて全員が赤いカードと白いカードを１枚ずつ持っている状態になるまでにかかるターン数の最大値を求めよ。
考え方：
少ない枚数で実験してみると
・赤いカードを２枚持っているプレイヤーは、右隣のプレイヤーが白いカード２枚の状態になるまで状態が変化しない。
・「白いカード２枚」の状態は、赤いカードを２枚持っているプレイヤーにぶつかるまで１つずつ左に移動していく。
のイメージがつかめると思います。
そこから結論は割とあっさり出ると思います。
これを正確に答案に表現すればＯＫです。
（ちょっとやりづらいです・・・）
解答例：
初めにある１人が赤いカードを２枚、その左隣のプレイヤーが白いカードを２枚、
それ以外のプレイヤーは赤いカードと白いカードを１枚ずつ持っているとする。
この時、$${2006}$$回目のターンまでは白いカードを２枚持っている状態が１つずつ左のプレイヤーに移動する。
$${2007}$$回目のターンで初めて全員が赤いカードと白いカードを１枚ずつ持っている状態になる。
これが求める最大値であることを示す。
初めに赤いカードを２枚持っているプレイヤーは、
右隣のプレイヤーが赤いカードを１枚でも持っていれば、
次のターン後も赤いカードを２枚持ったままである。
また、赤いカードを２枚持っていないプレイヤーが
ターン後に赤いカードを２枚持った状態になることはない。
あるプレイヤーが白いカードを２枚持っており、
その左隣のプレイヤーが白いカードを１枚でも持っていれば、
次のターン後に左隣のプレイヤーが白いカードを２枚持った状態になる。
逆に、ターン後に白いカードを２枚持った状態のプレイヤーについて、
その右隣のプレイヤーはターン前に必ず白いカードを２枚持った状態となっている。
つまり、白いカードを２枚持っている状態は
赤いカードを２枚持っているプレイヤーの右隣に行くまで
各ターンごとに左に１つ移動する。
そしてその次のターンで、
その赤いカードを２枚持っているプレイヤーは
赤いカードと白いカードを１枚ずつ持っている状態に変化する。
プレイヤーは$${2008}$$人であるため、
初めに赤いカードを２枚持っている任意のプレイヤーについて、
$${2006}$$ターン以内に右隣に「白いカードを２枚持っている状態」が移動してくる。
つまり、最大でも$${2007}$$ターン以内に赤いカードと白いカードを１枚ずつ持っている状態に変化する。
このとき、赤いカードと白いカードの枚数は等しいため、
赤いカードを２枚持っているプレイヤーがいないとき、
全員が赤いカードと白カードを１枚ずつ持っている状態になる。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
間違いなど見つけましたら是非お教えください。
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)