クイズ大陸



履歴 検索 最新 出題

No. 6≫ No.7 ≫No. 8
?朱雀 2012/11/11 07:55
自分で囁いたものって公開できないんですね (^^;)
こんなこともあろうかと,パスワードはanswerにしてあるので>>3に入力して見ることができます.面倒な方のために,若干修正した文章を以下に載せておきます.


指針:nの場合を考えるのにn-1の結果を使う.

n=Nで行うゲームをG(N)と表す.また,Aさんが先手の場合をG(N,A)と表す.今,G(N,A)を考えよう.Aさんが最初に左端を赤で塗ると,残りのマスは横に連続したN-1個なので,G(N-1)で用いるマスと同じである.そして,次はBさんが塗る番だが,左端のマスは絶対に紫にはされない残りのマスで行うゲームはG(N-1,B)と同等か,よりAさん有利である.

G(1,A):
A1対0Bで先手必勝

G(2,A):
1対1で引分なのは自明だが,次のように考えることもできる.Aさんが左端を赤で塗ると,前述のように残りのマスで行うゲームはG(1,B)と同等か,よりAさん有利である.つまり,G(1,B)はG(1,A)で求めた結果よりB1対A0が両者最善の場合の結果であり,この時,左端の赤を含めてA1対1Bで引分.

G(3,A):
Aさんが左端を赤で塗ると,残りのマスで行うゲームはG(2,B)と同等か,よりAさん有利である.G(2,A)の結果から考えて,両者最善の場合,G(2,B)の結果はB1対1Aの引分である.実際には,左端の赤で青を挟んでBの点数を減らすことも可能だし,たとえ挟まなくても,左端の1点リードのためにA2対1Bで先手必勝.

G(4,A):
Aさんが左端を赤で塗ると,残りのマスで行うゲームはG(3,B)と同等か,よりAさん有利である.G(3,A)の結果から考えて,両者最善の場合,G(3,B)の結果はB2対1AのBさん必勝である.この時,左端の赤を加えてA2対2Bの引き分けであるが,しかし,左端の赤を用いて青を挟めばAさんが勝てる.逆に言えば,左端の赤で挟まれることを確実に避ける方法がBさんにあれば引分,無ければAさん必勝である.実は,左端の赤の隣に青を塗らなければ良いのであり,G(3,B)だから最後に塗るのはBさんである.Bさんが左端の赤の隣を塗らないように手を進めて,仮に左端の赤の隣だけが最後まで残された場合,そこに入れても挟まれたことにはならない.したがって,左端の赤を無効化する方法がBさんにはあるから,G(3,B)の両者最善の結果をそのまま‐すなわちB2対1A‐実現でき,左端の赤を加えてA2対2Bの引分.

重要なことは
つまりG(N,A)の結果は,G(N-1,B)の両者最善の結果がAX対YBならば,A(X+1)対YBとなることである.
そして,先手必勝でも,両者最善ならば常に1点差であることである.

G(n,A)が引分ならば,G(n,B)も引分であり,G(n+1,A)はAさん必勝(1点差).
G(n,A)がAさん必勝(1点差)ならば,G(n,B)はBさん必勝(1点差)であり,G(n+1,A)は引分.

G(1,A)はA1対0Bの先手必勝だから帰納的に,
nが奇数の時,先手必勝
nが偶数の時,引分
編集