実験と証明(JMO2008h-2)

今回は、本選の組み合わせの典型問題を解いていきます。この問題はかなりオーソドックスな問題だと思うので是非マスターしてください。それでは、よろしくお願いします。

問題

この手の問題は実験が命です。

解説

step0.実験

あるプレイヤーが赤と白のカードを持っている状況を \((r,w)\) などと表す。 以下はあるプレイヤーのカードの遷移である。

\[(r,r)→(?,r), (r,w)→(?,w), (w,w)→(?,w)\]

\((r,r)\) となるためには直前が少なくとも \((r,r)\) である必要である。 これは、\((r,r)\) の数はターンが進むにつれて広義短調減少していくことを意味する。 \((r,r)\) の人が0人になる状況はすなわち全員が \((r,w)\) の状況なので、全員が赤いカードと白いカードを一枚ずつ持っている状態になる。

(まずは状況の把握するために遷移を考えようというモチベーションです。\((r,r)\) はターンが進むと、\((r,r)\) か \((r,w)\) のどちらかになり、\((r,r)\) が \((r,r)\) 以外から生まれる事はないので、広義単調減少していくということですね。)

step1.最大ターン数を上から評価するために

出来るだけ長続きさせるためには \((r,r)\) の人が一人でもいれば良い。 ある \((r,r)\) の人に着目し、その人を出来るだけ \((r,r)\) の状態に保つことを考える。 ある \((r,r)\) のプレイヤーが次のターンも \((r,r)\) であるためには、右隣のプレイヤーから \(r\) をもらう必要がある。 すなわち、右隣のプレイヤーは \((r,r)\) か \((r,w)\) であれば良い。 ここで、帰納的に \((r,r)\) の人が \(k\) ターン後も \((r,r)\) であるためにはその人から右隣 \(i\) 人の人が計 \(i\) 枚以上の赤いカードを所持している必要がある。 (\(i\) は \(0\) 以上 \(k\) 以下の任意の正整数を動く。)

step2.最大ターン数を上から評価する

最初に\((r,r)\) である人の中で最後まで \((r,r)\) であるような人の一人：\(A\) に着目する。 \(A\) が \(k\) ターン後も \((r,r)\) であるためにはその人から右隣 \(i\) 人の人が計 \(i\) 枚以上の赤いカードを所持している必要がある。 ここで、\(A\) 以外が所持している赤いカードの枚数は \(2006\) 枚なので最大で \(2006\) ターン \((r,r)\) を保つことができる。 逆に \(2007\) ターン以上 \((r,r)\)に保つことはできない。 よって、\((r,r)\) を保てる最大ターン数は \(2006\) 以下である。 逆に、ある人を \((r,r)\)、その左隣の人を \((w,w)\)、その他の人を \((r,w)\) とすれば \(2006\) ターン \((r,r)\) を保つことができる。 よって、解答は \(2007\) である。

(必要条件で絞る→構成するというお決まりの流れです。参考：必要条件と構成(JJMO2022h-3))

まとめ

・状況の把握と、答えの予測のために実験をしましょう。実験は本当に大切です。

・必要性で絞って十分性(構成する)で攻めるという流れは競技数学では頻出です。押さえておきましょう。

・\((r,r)\) などの記号を自分で定めて答案で使用することは時間短縮、可読性向上に繋がります。積極的に使っていきましょう。