数学の部屋へもどる【参考】
ニム（Nim）とは、物を並べて二人で交互に取合うゲームのことをいいます。
英語です。
◆石川県 Takashi さんからの解答
【問題１】
先手必勝。
まず、２段目の中央の１本を消す。 ｜
｜＋｜
すると、同時に２本以上消す事の出来ない棒が３本残っているので、先に消す後手が必ず負ける。
【問題２】
２段目の中央の１本を消すか、２段目を３本とも消す。
問１で説明した事を応用して考えると、
互いに独立した（２ｎ−１）本【ｎは自然数】を残して相手に渡すと勝つ事が出来る。
【問題３】
先手必勝。
まず、３段目の端から３本を消す。 ｜
｜｜｜
＋＋＋｜｜
＜ａ＞後手が、１段目を消したとき、
先手は、２段目の端の１本を消す。 ＋
｜｜＋
＋＋＋｜｜
次に、後手が１本消したら先手は２本
後手が２本消したら先手は１本消せば先手が勝。
＜ｂ＞後手が、２段目の端の１本を消したとき、
先手は、１段目を消す。 ＋
｜｜＋
＋＋＋｜｜
よって、＜ａ＞と同様となり先手が勝。
＜ｃ＞後手が、２段目の中央の１本を消したとき、
先手は、３段目の２本を消す。 ｜
｜＋｜
＋＋＋＋＋
よって、問１と同様に、先手が勝。
＜ｄ＞後手が、２段目の２本を消したとき、
先手は、３段目の１本を消す。 ｜
｜＋＋
＋＋＋｜＋
よって、問１と同様に、先手が勝。
＜ｅ＞後手が、２段目の３本を消したとき、
先手は、３段目の２本を消す。 ｜
＋＋＋
＋＋＋＋＋
よって、先手が勝。
＜ｆ＞後手が、３段目の１本を消したとき、
先手は、２段目の２本を消す。 ｜
＋＋｜
＋＋＋＋｜
よって、＜ｄ＞と同様に、先手が勝。
＜ｇ＞後手が、３段目の２本を消したとき、
先手は、２段目の３本を消す。 ｜
＋＋＋
＋＋＋＋＋
よって、先手が勝。
以上によって、先手が必勝である。
◆広島県 清川 育男 さんからの解答
【問題１】
先手 ２段目の３本を消す。
後手 １段目の１本を消さざるを得ない。
したがって、先手必勝。
【問題２】
後手 ２段目の３本を消す。
終局まで残り３手であるから、先手−後手−先手
したがって、後手の勝ち。
【問題３】
先手必勝。
３段目を左から１，２，３，４，５と番号を付けるとき、
（１，２，３）の３本か（３，４，５）の３本を消せばよい。
１ １
１１１ １１１
＋＋＋１１ １１＋＋＋
ブロック（つながっているもの）で考えると「３山崩しの問題」に還元される。
残りは（１，３，２）。
（１，１，１）または（２，２）にして後手に手を渡す。
例えば、後手が２段目の中央の１本を消せば、先手は３段目の２本を消す。
ブロックで考えると残りは、（１，１，１）となる。
２進法で最初の状態を表現すると、
「００１」 「００１」
「０１１」−＞＞「０１１」
「１０１」 「０１０」
1 XOR 3 XOR 5=7 ->> 1 XOR 3 XOR 2=0
排他的論理和を０にして後手に手を渡したことになる。
【問題４】
1 XOR 3 XOR 5 XOR 7=0 001
011
101
111
――――
224
排他的論理和が０でかつ２本以上の段が２個以上あるから、後手必勝です。
●例 １ １ １
１１１ １１１ １１１
１１１１１ −＞＞ １１１１１ −＞＞ ＋＋＋１１
１１１１１１１ １１＋＋＋１１ １１＋＋＋１１
1 XOR 3 XOR 5 XOR 2 XOR 2=7
1 XOR 3 XOR 2 XOR 2 XOR 2=0
最初の状態のとき排他的論理和０がであるから後手必勝となら。
【おまけ】
ブロック（つながっているもの）で考えると、「Ｎ山崩しの問題」に還元される。
今回のルールでは後手必勝のパターンは、２個以上の山が２個以上あり、かつ排他的論理和が０のときである。
１段（問題にならないと思います。）
４段，８段，１２段，・・・・，４Ｎ段（Ｎは自然数。）
のとき後手必勝で、他の場合は先手必勝である。
結局２進法の問題に還元されます。
またブロック（つながっているもの）で考えると、「Ｎ山崩しの問題」になります。
◆石川県 平田 和弘 さんからの解答。
【問題１】
勝ち方その1 先手 後手
｜ ｜ ＋
｜｜｜ → ＋＋＋ → ＋＋＋ → 先手勝ち
勝ち方その2 先手 後手 先手 後手
｜ ｜ ｜ ＋ ＋
｜｜｜ → ｜＋｜ → ＋＋｜ → ＋＋｜ → ＋＋＋ → 先手勝ち
以上より先手勝ちとなります。
【問題２】
先手 後手
｜ ｜ ｜ ｜
｜｜｜ ｜｜｜ ＋＋＋
｜｜｜｜｜ → ｜＋＋＋｜ → ｜＋＋＋｜ → ｜ ｜ → となり、
ここでの後手番勝ち即ち後手勝ちとなります。
【問題３および問題４】
1,3,5,7をそれぞれ山と呼ぶことにしてを各山を2進法で表して考えます。
また山の間(途中)を消されたときは山を分割して同様に考えます。
1)1,3,5 のとき
1＝ 1(2)
3＝ 11(2)
5＝101(2)
2)1,3,5,7 のとき
1＝ 1(2)
で、2進法表記の各位の1の個数が偶数個の時、偶数ポジションと呼び、そうでないとき奇数ポジションと呼ぶことにします。
3＝ 11(2)
5＝101(2)
7＝111(2)
上の例では1)は奇数ポジションで、2)は偶数ポジションです。
結論から言うと、奇数ポジションの時は、先手勝ちとなり、偶数ポジションの時は後手勝ちとなります。
戦略1)どの山にも1個しかないときは、奇数個の時に相手に手番が渡るようにする。
戦略2)どれかの山に2個以上あるときは、
A)奇数ポジションのときはうまい手を選んで偶数ポジションにすることができる。
B)逆に偶数ポジションのときは必ず奇数ポジションになる。
上記2つの戦略により、先手勝ち、後手勝ちが決まります。
実際、問題３では、奇数ポジションなので、
先手が5の山の左から1,2,3本目を消すと、
1＝ 1(2)
3＝11(2)
2＝10(2)
となり、偶数ポジションとなります。
以後は後手がどのような手を選択しても奇数ポジションになります。
以下、同様の戦略で先手勝ちとなります。
また、問題４では、偶数ポジションなので、先手がどんな手を選択しても奇数ポジションになります。
例えば、先手が5の山の左から2,3本目を消したとすると、後手が7の山の左から1〜6本目を消せば、再び偶数ポジションとなります。
2進法で表すと以下のようになります。
先手 後手
１ １ １
１１ １１ １１
１０１ １ １
１１１→ １０ → １０
１１１ １１１
以下同様の戦略で後手勝ちとなります。
【おまけの問題】
結論は段数が4n(n＝1,2,3,・・・・・)のとき後手勝ちとなります。
実は段数が4n(n＝1,2,3,・・・・・)のとき上記定義の、偶数ポジションとなります。
実際、1,3,5,7,・・・・の一般項は
a(n)＝2n−1 で、
1)n＝4m(m＝1,2,3,・・・) のとき、
a(n)＝8m−1
2)n＝4m−3(m＝1,2,3,・・・) のとき、
a(n)＝8m−7＝8m−22−2−1
3)n＝4m−2(m＝1,2,3,・・・) のとき、
a(n)＝8m−5＝8m−22−1
4)n＝4m−1(m＝1,2,3,・・・) のとき、
a(n)＝8m−3＝8m−2−1
従って、段数が4n(n＝1,2,3,・・・・・)のとき
| 8m | −1 | ||
| 8m | −22 | −2 | −1 |
| 8m | −22 | −1 | |
| 8m | −2 | −1 |
で、2進法で表したときの
1の位、2の位、22の位、23位以上の1の個数が必ず偶数個となります。
後は上記、戦略1)、2)に従えば後手勝ちとなります。
【問題４ 補足】
2進法表記で、
1
11
101
111
――――
の偶数ポジションでスタートして先手は(左右同形を除いて)次の30手しかありません。
しかも必ず奇数ポジションになります。
01)
＋
｜｜｜ １１
｜｜｜｜｜ １０１
｜｜｜｜｜｜｜ → １１１
――――
02)
｜ １
＋｜｜ １０
｜｜｜｜｜ １０１
｜｜｜｜｜｜｜ → １１１
――――
03)
｜ １
｜＋｜ １
｜｜｜｜｜ １
｜｜｜｜｜｜｜ → １０１
１１１
――――
04)
｜ １
＋＋｜ １
｜｜｜｜｜ １０１
｜｜｜｜｜｜｜ → １１１
――――
05)
｜ １
＋＋＋ １０１
｜｜｜｜｜ → １１１
――――
｜｜｜｜｜｜｜
06)
｜ １
｜｜｜ １１
＋｜｜｜｜ １００
｜｜｜｜｜｜｜ → １１１
――――
07)
｜ １
｜｜｜ １１
｜＋｜｜｜ １
｜｜｜｜｜｜｜ → １１
１１１
――――
08)
｜ １
｜｜｜ １１
｜｜＋｜｜ １０
｜｜｜｜｜｜｜ → １０
１１１
――――
09)
｜ １
｜｜｜ １１
＋＋｜｜｜ １１
｜｜｜｜｜｜｜ → １１１
――――
10)
｜ １
｜｜｜ １１
｜＋＋｜｜ １
｜｜｜｜｜｜｜ → １０
１１１
――――
11)
｜ １
｜｜｜ １１
＋＋＋｜｜ １０
｜｜｜｜｜｜｜ → １１１
――――
12)
｜ １
｜｜｜ １１
｜＋＋＋｜ １
｜｜｜｜｜｜｜ → １
１１１
――――
13)
｜ １
｜｜｜ １１
＋＋＋＋｜ １
｜｜｜｜｜｜｜ → １１１
――――
14)
｜ １
｜｜｜ １１
＋＋＋＋＋ → １１１
――――
｜｜｜｜｜｜｜
15)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
＋｜｜｜｜｜｜ → １１０
――――
16)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
｜＋｜｜｜｜｜ → １
１００
――――
17)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
｜｜＋｜｜｜｜ → １０
１００
――――
18)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
｜｜｜＋｜｜｜ → １１
１１
――――
19)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
＋＋｜｜｜｜｜ → １０１
――――
20)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
｜＋＋｜｜｜｜ → １
１００
――――
21)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
｜｜＋＋｜｜｜ → １０
１１
――――
22)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
＋＋＋｜｜｜｜ → １００
――――
23)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
｜＋＋＋｜｜｜ → １
１１
――――
24)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
｜｜＋＋＋｜｜ → １０
１０
――――
25)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
＋＋＋＋｜｜｜ → １１
――――
26)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
｜＋＋＋＋｜｜ → １
１０
――――
27)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
＋＋＋＋＋｜｜ → １０
――――
28)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
｜＋＋＋＋＋｜ → １
１
――――
29)
｜ １
｜｜｜ １１
｜｜｜｜｜ １０１
＋＋＋＋＋＋｜ → １
――――
30)
｜
｜｜｜ １
｜｜｜｜｜ １１
＋＋＋＋＋＋＋ → １０１
――――
たぶんもれていないと思いますが・・・・・。
◆埼玉県 ごろー さんからの解答
一般の場合の『Ｎ山崩し』、『棒取りゲーム』の証明です。
この証明は「棒取りゲーム（最後に取ったほうの負け）」のものです。
石川県平田和弘さんの戦略２）Ａ）Ｂ）が正しいことの証明と具体的にどのように棒を取るかについて書いてみました。
”（５）のときは次の一手で（１），（５）の形にはできないことの証明。”がＮ山崩しの証明とは異なる部分だと思います。
［命題、用語の説明］
｜｜｜・・｜ ａ本 ｜｜｜・・・｜ ｂ本 ｜｜｜・・・・｜ｃ本 ｜｜｜・・・・｜・ ・・・・・・・・・ ・・・・・・・・・を（ａ，ｂ，ｃ，・・・）のように書くことにします。
一般の場合（ａ，ｂ，ｃ・・・）の勝ち負けについて。
ａ*ｂ*ｃ*・・・を次のように決める。
各数を二進数表示して各桁ごとに１が奇数個なら１、偶数個なら０とした二進数とする。
（これはａ ＸＯＲ ｂ ＸＯＲ ｃ ＸＯＲ ・・・・と等しいものです。）
次の（１）〜（５）の場合しかなく、これで勝敗が判定できます。
（１）ａ＝ｂ＝ｃ＝・・・＝１かつ１が奇数個 →（この場面の時の）後手が必勝 （２）ａ＝ｂ＝ｃ＝・・・＝１かつ１が偶数個 →（この場面の時の）先手が必勝 （３）ａ，ｂ，ｃ，・・・の一個だけが１でない。→（この場面の時の）先手が必勝 （４）ａ，ｂ，ｃ，・・・の二個以上が１でないかつａ*ｂ*ｃ*・・・＝00・・0でない →（この場面の時の）先手が必勝 （５）ａ，ｂ，ｃ，・・・の二個以上が１でないかつａ*ｂ*ｃ*・・・＝00・・0 →（この場面の時の）後手が必勝（１），（２），（３）は正しいことが簡単にわかります。
［証明はここから］
石川県平田和弘さんの戦略２）Ａ）に対応する部分。
（４）のときは次の一手で必ず（５）の形にできることの証明。
なぜなら、ａ*ｂ*ｃ*・・・＝00・・0でないので、この値を左から順にみていけば１が必ず見つかります。
一番右が１桁目であると数えることにして、今見つけた１はｎ桁目だとします。
ａ，ｂ，ｃ，・・・を二進数表示したときｎ桁目が１であるものがある。
| なぜならｎ桁目の１の個数は奇数個なので、とくに１の個数は０ではありません。 |
それがａだとする。
ａ*ｂ*ｃ*・・・の１である桁とａを二進数表示したときの同じ桁の１と０をすべて入れ替えて、
それをａ’とおく。
ｎの決め方からｎより大きい桁（左側）の１と０は入れ替わらない。
ｎ桁目は１から０に変わるので、ａ＞ａ’となります。
| １からｎ−１桁目でもａとａ’は異なるかもしれませんが これは考えなくてもａ＞ａ’となります。 たとえば、７７７１２３＞７７７０９７であることと同じことです。 |
また、ａ’の作り方からａ’*ｂ*ｃ*・・・＝０です。
| なぜなら、各桁ごと１の個数が偶数個になっています。 |
ａ，ｂ，ｃ，・・・の三個以上が１でないなら
ａがａ’となるように棒を取れば（５）の形になります。
ａ，ｂ，ｃ，・・・の二個のみ１でないときは
ａ’＞１となるのでａがａ’となるように棒を取れば（５）の形になります。
石川県平田和弘さんの戦略２）Ｂ）に対応する部分。
（５）のときは次の一手で（１），（５）の形にはできないことの証明。
（１）にならないことは簡単にわかります。
（５）の形にならないことについて。
先手はａから棒を取ったとします。
このとき（ａ） → （ａ’）のように端の棒を含めてとる場合と
（ａ） → （ａ1，ａ2）のように端の棒を取らずに棒をとる場合があります。
前者ではどう取ってもａとａ’の二進展開のある桁は異なるので
ａ’*ｂ*ｃ*・・・＝00・・0ではありません。
だから（５）の形ではありません。
後者はａ＝ａ1*ａ2が成り立つように棒を取ることはできないことを証明します。
まず１本以上棒を取ることからａ＞ａ1＋ａ2となります。
次にａ1≧ａ2であるとしても問題ありません。
ａが二進でｎ桁の数であるとします。
ａ＝ａ1*ａ2となるためにはａ1は２nｰ1以上でなければなりません。
しかし、ａ2＜ａ−ａ1であるのでａ＝ａ1*ａ2が成り立つようにはできません。
そうすると、どう取ってもａと（ａ1*ａ2）の二進展開のある桁は異なるので
（ａ1*ａ2）*ｂ*ｃ*・・・＝00・・0ではありません。
だから（５）の形ではありません。
この証明から上のように棒をとっていけば最初の形だけで先手必勝か後手必勝かが決まっていることがわかります。
問題
(a，b，c，・・)＋(x，y，z，・・)=(a，b，c，・・，x，y，z，・・) ｋ(a，b，c，・・)=(２k*a，２k*b，２k*c，・・) で定める。 Ｖ=｛(・・・)｜(・・・)は後手必勝形｝−｛(1，1，1，・・)｜奇数個の１｝ は和、スカラー倍で閉じている。
◆ 問題へもどる
◆ 今週の問題へ