Nim

Misere(正しくはMisère) Game とは,(多分)"最後の一個をとったら負け"みたいなゲームの事で,例えばNimに対して Misere Nimというものが考えられる.
Nimの勝利条件がNimber(Grundy number)であることはwell known factだが,Misere Nimの勝利条件を知らなかったのでメモ.(2014年12月放送の頭脳王という番組に番組独自の問題として出てきた,後述)

実はNimとほとんど同じで基本的に相手にxorが0の状態を渡せばいいのだが,最後までそれをやるとこっちが負けるので,最後はちょっと変える.正確には,その状態で次に動かすプレイヤーの敗北条件は,

となる.
prf(の概略).
後半は自明(残り奇数個なら最後取ってしまうので).
前半はNimと一緒で,あとは前半から後半にうまく移行できるかだが,全て1以下の状態でこっちに帰ってくることがないようにすれば良い.
普通のNimっぽくやって自分に1,..,1(2k-1個(k>=1))が来るような手になった時どう改善すればよいか考える.
その直前の相手の状態は,"1が2k個"または"1が2k-2個,xが1個(x>1)"(以下x>1とする)だが,後者はありえない(xorが0にならないので).
よって更にその直前の自分の状態を考えると,

• 1が2k+1個

この時はこの段階で対処をすべき(ちゃんというと,帰納法で示される(前半から後半へ移行出来る状態では必ず対処できる段階があるため)).

• 1が2k個,x(>1)が1個

xからx-1個取る
よって必敗を相手に回せることがわかった.
それ以外で負けることは,それ以外の状態で以上の状態のどれかに引き渡せることが(Nim同様に)わかるため言える.■

なんでこの記事を書こうと思ったかというと,2014年12月放送の頭脳王という番組で,番組独自のゲームとしてpileが3個のmisere Nimを出場者にやらせていて(vs コンピュータ),まあそれはまだ百歩譲って許せなくはないのだが,しかも数十手先を見通す力とか的はずれなことを言っていたが(石は数十個もない)(まあいつもの煽りだから許される).許されないのは,それぞれの人に初期状態として別の手が渡されていたのだが,
そのうちいくつかは必敗でいくつかは必勝だったという激ヤバな事実があったからです(先手で(3,9,10)が渡された人と(4,5,9)が渡された人がいた).
しかもコンピュータ側の動きを見ると,ちゃんと必勝の手に従っていたので,多分わざとだと思う.(一応コンピュータは探索をしているだけで,必勝かどうかは出題側は知らなかった(独自のゲームとして紹介しているので)と言い張ることは可能だけれど)
必敗の人かわいそうだった.
50点問題で,その時点での点数が150,110,100,60で2位以上勝ち抜けだったので同点を避けたのかなあ.

追記:
genkiさんのコメントの通り,"この状態は必敗である"という主張ができたら流石にOK(つまり点数を得られる)と思われるので,(当然ゲーム的には必敗だが,)"参加者は"完全"に勝ちの目を閉ざされた"というのは言いすぎだという注釈をつけておきます.