ｸｲｽﾞ大陸

つづいて、問3です。

指標の導入

各コインに対して、「価値」をつける。
n番目のマスに配置されているコインの価値を(-2)ⁿと定める。

また、マスの上に置かれている各コインの価値の和を「総価値」、
勝利条件を満たすようにコインを配置した時の総価値を「目標価値」と呼ぶことにする。

目標価値の符号を調べる

星印の描かれたマスのうち、1番目のマスから最も遠いマスをn番目のマスとする。
勝利条件を満たした時、n番目のマスに置かれたコインの価値は(-2)ⁿである。
1番目から(n-1)番目までのマスに置かれているコインの価値の"絶対値"の和は
高々 2 + 4 + 8 + … + 2^n-1 = 2ⁿ-2 である。
|(-2)ⁿ| ＞ 2ⁿ-2 なので、目標価値の符号はn番目にコインが置かれた時の価値の符号と一致し、
・nが偶数なら、目標価値は正
・nが奇数なら、目標価値は負
ということになる。

最も遠い星印マスが偶数番目のマス＝目標価値が正の場合

それぞれの操作を行った時、操作1を行うごとに総価値は2減り、
操作2および操作3では総価値は変化しない。
初期状態での総価値は0であり、どの操作を行っても総価値を増やすことはできないので
勝利条件を満たす配置にはなりえず、勝利することは不可能。

最も遠い星印マスが奇数番目のマス＝目標価値が負の場合

「n番目のマスと、それよりも起点に近いすべての偶数番目のマスに、コインを1枚ずつ置く」
となるように、既存の操作を組み合わせる。これを操作Y(n)とする。

・操作Y(1)は、操作1を1回行うことに等しい。
・操作Y(n)となる手順が存在する時、操作Y(n+2)は
　（問1・2で証明した「操作X」を用いて） 操作Y(n)→操作X(n)→操作2(n) に等しい。
数学的帰納法により、任意の奇数nにに対し、操作Y(n)となる手順が存在することが確認できる。

勝利するための手順

星印が描かれているマスのうち、起点から最も遠いマスの番号を(2n+1)とする。
1. 操作Y(2n+1)を行う
　この操作を行うことで、(2n+1)番目以降のマスの星印の有無とコインの有無は一致し、
　それ以前のマスは、奇数番目ならばコインがなく、偶数番目ならコインが1枚だけ置かれている状態となる。

2. 必要に応じて、以下のa. とb. を行う
　a. 星印が描かれていない偶数番目のマスにコインが置かれている場合、「操作X(2k-1)→操作X(2k-1)→操作3(2k-1)」として、そのコインを取り除く
　b. 星印が描かれている奇数番目のマスにコインが置かれていない場合、操作X(2k-1)としてコインを置く

これで勝利することができます。