石取りゲーム

質問

n を0 以上の偶数とするとき, (1; n; n + 1) は良形であることを示せ.
帰納法で証明するやり方を教えてください。お願いします。

回答No.3

nag0720

たぶん「三山くずし」のことだと思うので・・・

必勝形のことを良形とするなら、良形とは、
「相手がどんな石の取り方をしても、自分の番に良形にできる」
ことです。

１つの山が０の場合は、
(0; n; n)が良形、それ以外が悪形。
（相手が取った石と同じ数を違う山から取ればいい）

１つの山が１の場合は、
(1; 2n; 2n+1)が良形、それ以外が悪形。

帰納法での証明は、
n=0のときは、(1; 0; 1)で良形
n-1以下のとき良形としたとき、

(1; 2n; 2n+1)の左の山から１個石を取った場合、
左の山から１個石を取ると、(0; 2n; 2n)で良形

(1; 2n; 2n+1)の真ん中の山からk個(k≦2n)石を取った場合、
kが偶数なら、左の山からk個石を取ると、(0; 2n-k; 2n-k+1)で良形
kが奇数なら、左の山からk+2個石を取ると、(0; 2n-k; 2n-k-1)で良形　（2n-k-1は偶数、2n-kは奇数なので）

(1; 2n; 2n+1)の右の山からk個(k≦2n+1)石を取った場合、
kが偶数なら、真ん中の山からk個石を取ると、(0; 2n-k; 2n-k+1)で良形
kが奇数なら、真ん中の山からk-2個石を取ると、(0; 2n-k+2; 2n-k+1)で良形　（2n-k+1は偶数、2n-k-2は奇数なので）

詳しくは参考URLを。

参考URL：

http://www.ccad.sist.chukyo-u.ac.jp/~mito/syllabi/dscrtMath2/nim/index.htm

回答No.2

Tacosan

ついでに「良形」の定義も.

回答No.1

nag0720

石取りゲームといっても種類がいくつもありますから、まずは、ゲームのルールを明確にしてください。