三山くずし

ゲーム概要
三つの山に分かれた石の山があります。二人が交互に山から石をとります.
一つの山からは任意の個数取ることができますが,二つの山に跨ってとることや,一つも取らないことは許されません.
石を取ることが出来なくなった方が負けです.

特殊な必勝形

このゲームには必勝法があり、最初の山の数で(相手がどのように取っても)勝つ方が定まっています.簡単な場合では (0,n,n) の場合,後手が必勝です.後手は先手と同じだけ別の山から石を取り、常に(0,n,n)の形を保てば勝つことができます.また,(3,2,1)も後手必勝です.

一般の必勝法
 一般的な必勝法は次の通りです.各山の数を(a,b,c)とします。a,b,cをそれぞれ二進数に展開し,各桁を ai,bi,ci とします.このとき,すべての桁iについて ai ^ bi ^ ci = 0 のとき、必勝形とよびます。ここで、^ はEXOR(排他的論理和)で、1の数が偶数のとき0、奇数のとき1となります.
必勝形にすることができればゲームに勝つことができます。この必勝形に対し,ルールに従って石をとれば,必ず必勝形でなくなり、また,必勝形でない場合,適当に石をとれば必ず必勝形にできることが証明できます.


ゲームは,例えば,次のように進行します。3つの数が、実行後の各山の数です。
最初の三つの山の数を(4,3,2)とします.A:(2,3,2)でプレーヤAが最初の山から2個取ったことを示します.以下次のように進行します。

 B:(2,3,1),A:(2,1,1),
 B:(0,1,1),A:(0,0,1),
 B:(0,0,0)でBの勝ちです.