入試史上最難問とされている問題です。問題文は省略しますが、東大 最難問 と検索すれば問題文を載せたサイトがいくつか見つかります。
ここでは、問（2）の必要条件を求めます。
（2）の必要条件がｎ≡2（mod3）ではないことを示します。
まず、最初の白丸に1という数字をつけます。1ステップ目の操作では、この最初の白丸の左右どちらかに新たな白丸を加えますがこの新たな白丸
を2とします。以下同様にＮステップ目の操作で加わる白丸をＮ+1とすれば、Ｎステップ目の操作が終わった時点での状態をある1つのＮ+1の順列と
みなす事ができます。
そこで、この順列が持つ性質を見ていきます。
7.1.3.6.8.5.4.2
これは、8の順列の1つです。ここで、それぞれのi（i=1～8）は右側の数字と左側の数字によって色が決定します。ある数字iの左右にある数字の列は、
iが置かれた後にiの両隣に何度白丸が置かれたのかという情報をもっています。
この情報は、つぎの様な手続きによって得る事ができます。
まず、左端の丸iを座標1に占める丸とします。左から2番目の丸を座標2に占める丸、同様にして左からＫ番目にある丸を座標Ｋに占める丸とします。（Ｋ＝1～Ｎ+1）
そして、丸iの座標がＫi、丸jの座標がＫjの時、 ｜Ｋi-Ｋj|を丸iと丸jの距離とします。
上の順列では、座標1に占める丸は7で座標2に占める丸は、1、丸7と丸1の距離は｜1-2｜＝1などとなっています。
時刻0に粒子Ａが丸iにあるとします。もしもiが座標Ｋを占めていて座標Ｋ+1を占める丸jがi＜jなら粒子Ａは、時刻1でjへ移動します。
i＞jの場合には、粒子Ａはiで停止します。
i＜jの場合粒子Ａは、Ｋ+2～Ｎ+1の座標を占める丸mでi＜mかつj＞m という条件を満たしjとの距離がもっとも近い丸mへ時刻2で移動します。
Ｋ+2～Ｎ+1の座標を占める丸mにこの条件を満たす丸mがない場合、すなわち、Ｋ+2～Ｎ+1の座標を占める丸mが全てi＞mまたはj＜mの場合
粒子Ａはjで停止します。
以下同様に、時刻ｎで粒子Ａが座標Ｓを占める丸tにあるとすると、粒子Ａは、Ｓ+1～Ｎ+1の座標を占める丸uでi＜uかつt＞uという条件を
満たしtとの距離がもっとも近い丸uへ時刻n+1で移動します。Ｓ+1～Ｎ+1の座標を占める丸uが全てi＞uまたはt＜uの場合粒子Ａはtで停止します。
これを粒子Ａが停止するか右に丸が無くなるまで続けます。この時、粒子Ａが移動した回数がiの右隣りに白丸が置かれた回数です。
これをiの右方向での反転回数とします。iの左側の数列についても同じことが言えます。
例.上の順列の3の左には自身より小さい数字1があります。
これは、3が置かれた後に3の左側に白丸が置かれなかったことを意味します。
この場合の左方向の反転回数は0です。3の右隣りには自身よりも大きい数字6があります。これは、最後に3の右隣に置かれた白丸です。
8は3に影響を与えていません。5は6の1つ前に3の右隣に置かれた白丸です。そして、4が最初に3の右隣に置かれた白丸です。
つまり、右方向での反転回数は3で、左方向での反転回数が0、3+0＝3 で奇数よって上の順列で丸3は最終的に黒丸になります。
Ｎ個の全ての丸の色が白となる最小のＮ Ｎ≡2（mod3）を考える。そして、
1より左、1と2の間、2より右に入る丸の個数をそれぞれr.s.tとし、(r=i(mod3).s=j(mod3).t=k(mod3)) とする。（i.j.k）の最大値が2、1、0の場合に分けると
次の3通りが考えられます。
（r≡0(mod3)個の丸）.1.（s≡1(mod3)個の丸）.2.（t≡2(mod3)個の丸）
（r≡1(mod3)個の丸）.1.（s≡1(mod3)個の丸）.2.（t≡1(mod3)個の丸）
（r≡0(mod3)個の丸）.1.（s≡0(mod3)個の丸）.2.（t≡0(mod3)個の丸）
（r≡0(mod3)個の丸）.1.（s≡1(mod3)個の丸）.2.（t≡2(mod3)個の丸）の場合2より右のt個の丸は2より
後に置かれている。したがって、これらt個の丸が全て白ならばＮ＞t t=2(mod3) となるtで全てが白丸となるようにする事ができＮの最小性に反する。
（r≡1(mod3)個の丸）.1.（s≡1(mod3)個の丸）.2.（t≡1(mod3)個の丸）の場合1の左側にあるr個の丸は1と1より右にあ
る丸の影響を受けない。よって1の左方向での反転回数が偶数ならばＮ＞1+r 1+r=2(mod3) となる1+rで全て白丸となるようにすることが出来Ｎの最小性
に反する。よって、1は左方向で奇数回反転している。
Ｎで1が白丸となるためには、1の右方向での反転回数は奇数でなくてはならない。1から右方向へ出発した粒子Ａが2で停止する時刻の1つ前の時刻での
移動回数が偶数の場合、Ｎ＞1+s 1+s=2(mod3) となる1+sで全て白丸となるようにすることが出来Ｎの最小性に反する。
したがって、1の右方向の反転回数は偶数回です。
すると（1の右方向の反転回数）+（1の左方向での反転回数）＝奇数となってＮで1は黒丸となります。
（r≡0(mod3)個の丸）.1.（s≡0(mod3)個の丸）.2.（t≡0(mod3)個の丸）の場合2の左方向での反転回数が偶数ならば
2より右のt個の丸を取り去り Ｎ＞2+r+s 2+r+s=2(mod3) となる2+r+sで全て白丸が作れるのでＮの最小性に反する。したがって、2の左方向での反転回数
は奇数回です。そこで、rとtを取り去り下のように並べる
（s≡0(mod3)個の丸）.1.2
こうすると1の左方向での反転回数は奇数回です。よって、Ｎ＞2+s 2+s=2(mod3)となる2+sで全て白丸に出来るのでＮの最小性に反する。
rとtの丸の数が0だとこの推論は成り立ちません。しかし、この場合2～Ｎ-1ステップ目の操作で常に1と2の間に白丸を置いたことになり、その操作では黒丸
が偶数個づつしか変化しないので考える必要がありません。また、tの丸の個数が0で2の左方向での反転回数が偶数の場合は、1の左隣りに最初に置かれ
た白丸を1Ｆとして、
パターン1（r≡2(mod3)個の丸）.1F.（s≡0(mod3)個の丸）.1.（t≡0(mod3)個の丸）.2 と
パターン2（r≡1(mod3)個の丸）.1F.（s≡1(mod3)個の丸）.1.（t≡0(mod3)個の丸）.2 を考える。
パターン1では、Ｎ＞r r=2(mod3)となるrで全て白丸に出来るのでＮの最小性に反する事が言える。
パターン2では、Ｎの最小性から1の右方向での反転回数が奇数でなくてはならない。また、1から左方向へ出発した粒子Ａが1Ｆで停止する時刻の1つ前の時刻
での移動回数が偶数 の場合もＮの最小性に反するため1の左方向での反転回数は、偶数です。
したがって、パターン2では、1は黒丸となります。
証明終わり
おまけ
この問題には、2つの黒丸の間にある白丸の個数の交代和を3で割った余りが変化しないことを利用した解法が知られていますが、この性質を利用すると
黒丸1個スタートと白丸1個スタートは、その後同じパターンを持たないことが言えます。
まず、右端か左端に白丸を加える操作を操作1、2つの丸の間に白丸を加える操作を操作2として、最初の白丸の最初の黒丸それぞれの両端に白丸を1つずつ
置き、操作2だけを考えれば良いようにします。
交代和を計算する時だけ、両端に黒丸を加えます。
最初の時点では、いずれの交代和も0です。
あるＮで白丸1個スタートと黒丸1個スタートが同じパターンをもったと仮定します。（下図はＮ＝20としました。）
操作2では黒丸の偶奇は変化しないので、白丸1個スタートと黒丸1個スタートが同じパターンをもったならば、右端か左端の丸の色のみ異なります。
この時、それぞれの交代和を計算すると、
このように、白丸1個スタートと黒丸1個スタートでは交代和の値が1異なります。したがって、3で割った余りも異なります。
トップページへ