Wait a moment...

【数学】絶対勝ちたいマンの数学

nem408xem (16)
685
13
2019-12-27 16:29:26
【数学】絶対勝ちたいマンの数学




三山崩し(みやまくずし)という、石ころを使った簡単なゲームがあります。

これは、次のようなゲームです:



☆準備・まず、石ころを何個か集めてきます。石ころを何個か集めたもののことを と呼ぶことにします。
・さらに石を集めて、合計三つのを作ってください。


☆遊び方・二人で、交互に石を取っていくゲームだよ。先攻の人、後攻の人を決めてね。

・先攻の人は、三つの山の中から一つの山を選択し、そこから石を取るよ。
 何個石を取ってもいいけど、必ず一個以上は取らないとダメ。一つの山の石を全部取ってもOK。
 (必ず一つの山を選択して、そこから石を取る。二つ以上の山から石を取るのは禁止だよ!)

・次に後攻の人も同じルールで、山を一つ選択して、石を一個以上取る。

・これを交互に繰り返して、全部の山の石が取られるまで続ける。最後に石を取った人が勝ちだよ!



☆ゲームの流れの例









公園に行けば、だれでもタダで楽しめるゲームですね。


実はこのゲームには必勝法がありまして、最初に三つの山が、それぞれいくつ石を持っているか、ということから、
先手必勝か、後手必勝か、というのが数学的に決まってしまうのです。今回はこのことについて考えてみましょう。


※以下、先攻の人のことを先手、後攻の人のことを後手と呼びますね!



こんなとき、あなたの一手は?



まずは、三つの山のうち、二つの山が、同じ数の石を持っている場合を考えてみましょう。
この場合は、先手必勝なります。

 

例えば、次のような場合です:




弐の山の石の個数、参の山の石の個数が、同じ4個ですね。もしあなたが先手だったら、どの山から、何個、石を取りますか?





このような場合、先手の必勝法は以下の通りです:

・三つの山のうち、二つの山が同じ数の石を持つので、最初に先手は、もう一つの山の石を全て取ってしまいます
 これにより、同じ数の石を持つ山が、二つ残されることになります。



※今の例だと、弐の山、参の山が同じ数の石を持っているので、もう一つの壱の山の石を全て取る。



・後手は、残された二つの山のうち、片方の山から石をいくつか取ることになります。その次に先手は、
後手が取ったのと違う方の山から、後手が取ったのと同数の石を取るのです。
そうすると、二つの山の石の個数が、再び揃います。




あとはこれの繰り返しです。

つまり、後手はまた、二つの山のうち、片方の山から石をいくつか取ることになりますが、
やはり先手は、もう片方の山から、後手が取ったのと同数の石を取ります。
二つの山の石の個数が、再び揃います。

先手はこれを繰り返すことで、絶対に勝つことができます。







こんな感じで、
「最初に一つの山の石を全部取って、同数の石を持つ二つの山だけが残された状態にする」
「あとは、後手がやることを真似するように石を取っていく」
というシンプルな戦法により、先手は絶対に勝利することができるわけです。

先手は毎回、「石を取った瞬間、二つの山の石の数が同じになる」という状態で、後手は毎回、
石を取った瞬間、二つの山の石の数が違ってしまう」という状態が続きます。

なので、「石を取った瞬間、二つの山の石の数が、同じ0になる」という状況に辿りつけるのは先手のみ、
つまり、絶対に先手が勝つ、というトリックになっているんです。


「石を取った瞬間、二つの山の石の数が違ってしまう状態」のように、相手を一定の状態に閉じ込めてしまい、
自分が勝つまでその状態を続ける、というのは、必勝法を考える上での強力な戦法になるわけです!


二進法はこんなことにも使える




さきほどは、三つの山のうち、二つの山が同数の石を持つ場合を考えましたが、
次は、そうとは限らない一般の場合を考えてみましょう。

この場合、先手必勝のときも、後手必勝のときもあります。どちらが必勝かは、最初の三つの山が、
いくつ石を持っているかで決まります。

先手必勝か、後手必勝か。それは、二進法を使って、判定できるのです。


二進和(にしんわ) という、普通の足し算とは異なる、不思議な足し算 ⊕ を考えます。これは、次のような計算です:


1 ⊕ 2 = 3

3 ⊕ 3 = 0

2 ⊕ 7 = 5

5 ⊕ 6 = 3


↑これ、どんな規則かと言いますとね、例えば 「5 ⊕ 6」を計算したい場合は、まず、5, 6 を、二進法に直します。
 
5 → 101  6 → 110

そのあと、二つの数字 101, 110 の各桁を比較し、以下の図のように、

1
0 だったら 1 を, 

11 だったら 0 を, 

 00 だったら 0 を, 書いていきます:


`⊕' は、このような手続きで計算される演算です: 101 ⊕ 110 = 011 

これを十進法に直すと、5 ⊕ 6 = 3 となります。


他の例も見てみましょう。1 ⊕ 2 を計算したい場合は、1, 2 をそれぞれ
二進法に直します :  1 → 1,   2 → 10  .

桁数が異なる場合は、桁数が少ない方 (今の場合は 1) の頭に0をつけて、桁数を揃えてください。
各桁を比較して、やっぱり

10 だったら 1 を, 11 だったら 0 を,   00 だったら 0

を書いていきます:



てことで、01 ⊕ 10 = 11 となって、十進法に直すと、1⊕2=3 となります。

他の計算も全く同じです:



二進法に直した後、各桁を比較して、「1 と 0」 のように異なってたら 1 ,
「1 と 1」,「0 と 0」のように同じだったら 0 を書いていく。

このような手続きで計算される `新しい足し算' ⊕ のことを、二進和と呼びます。

次の定理が成り立ちます:


定理 三つの山に、壱の山、弐の山、参の山 と名前を付ける。最初の三つの山における石の個数が

 (壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0

となっているとき、後手必勝

 (壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) ≠0

となっているとき、先手必勝



※ `⊕' のことを「足し算」と呼んでいますが、⊕は、通常の足し算`+' と似た性質を持ちます。(一番の下部のあぺんでぃくす1参照)



ちょっと例を見てみましょう。最初の三つの山における石の個数が、次のような場合を考えます。

壱の山の石: 7個  弐の山の石:5個  参の山の石: 4個 

二進法で表すと、

→ 壱の山の石: 111 個  弐の山の石:101 個  参の山の石: 100個 .

なので、「111 ⊕ 101 ⊕ 100」 が 0 になるか否かを計算すると、先手必勝か後手必勝かがわかります。

`⊕' は、三つ以上の数字の計算も、そこまで難しくありません。

というのも、各桁ごとに比較して、1 の個数が奇数個だったら 1 を、偶数個だったら 0
書くことで、計算できてしまうのです:




なので、

(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) = 7 ⊕ 5 ⊕ 4 

--(二進法) → 111 ⊕ 101 ⊕ 100 = 110 ≠ 0

となって、上の定理により、先手必勝ということになります。


別の例として、最初の山の状態が

壱の山の石: 5個  弐の山の石:6個  参の山の石: 3個 

だったとき、二進法で表すと、

→ 壱の山の石: 101 個  弐の山の石:110 個  参の山の石: 11個 .

となります。(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) を計算してみましょう:



各桁を比較すると、それぞれ1が2個ずつ(偶数個ずつ)あるので、計算結果は 000 = 0 となります。
なのでこの場合、後手必勝ということになります。

こんな感じで、二進和を使うことで、どちらが必勝かが判定できちゃいます。


では、実際にどのように石を取っていけば勝てるのか。その必勝戦略のキーも、

(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) 

という二進和です。

そのメカニズムがわかると、なぜ上の定理が成立するのかもわかってくるはずです!



必勝戦略



まず、三つの山の最初の状態が


 (壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) ≠0


となっている場合を考えましょう。つまり、先手必勝の場合です。
先手はどのように石を取っていけば勝てるのか。

戦略はただ一つ。

「 (壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0となるように石を取り続ける」

というものです。


さきほど、壱の山の石: 7 個  弐の山の石:5個  参の山の石: 4個 の場合は、

 (壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) ≠0

となっていることを確認しました。そして、それは、



という計算によって確かめられました。

先手は、

(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0

となるように、壱、弐、参のどれかの山から石を取るのです。

そのためには、各桁の1の個数が偶数個になればいいわけです。

今は右から二桁目と三桁目の1の個数が奇数個になっていますね。そこで、111, 101, 100 のうちから一つを選び、
右から二桁目、三桁目に書かれている数字が、0だったら1に、 1だったら 0 に、反転させるように石を取ってやりましょう。

例えば、壱の山の石の個数 `111' を選んで、右から二桁目、三桁目の数字の1↔0を反転させると、001 という数字ができあがります:



こうなるように、壱の山から石を取ると、(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数)という
計算を考えたとき、右から二桁目、三桁目の1の個数が、それぞれ一個ずつずれて、各桁の1の個数が偶数個になります:




111 は十進法で 7、001 は十進法で 1 なので、先手は壱の山から個石を取れば、

(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0

という関係式が成り立つようになるのです。


※今は、111, 101, 100 のうちから 111 を選択しましたが、101 や 100 を選択してもOK。
101を選択した場合、右から二桁目、三桁目の1↔0を反転させると、


となって、


と、(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0が成立します。
101 は十進法で 5,   011 は十進法で 3 なので、先手は弐の山から 2個石を取ればいいことになります。 
ちなみに 100 を選択した場合は、参の山から 2個石を取ればいいことになります。




ここでは、壱の山の 111 を選択したとしましょう。


先手が壱の山から6個石を取ると、石の個数は、

壱の山の石: 1 個  弐の山の石:5個  参の山の石: 4個 

となります。


後手は、ここからどのように石を取っても、

 (壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0

という関係を崩すことになってしまいます。例えば、後手が、弐の山から石を 2個取ると、

壱の山の石: 1 個  弐の山の石:3個  参の山の石: 4個 

となります。1, 3, 4 を二進法に直すと、1, 11, 100 です。



つまり、 1⊕3⊕4 =001⊕ 011 ⊕ 100 = 110 ≠ 0

となって、確かに「 (壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0」
という関係式が崩れています。

次に先手は、後手が崩した (壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0
という関係を修復するように、石を取ります。やり方はさっきと一緒。

今は右から二桁目と三桁目の1の個数が奇数個になっているので、やはり 001, 011, 100 の中から
一つ選んで、右から二桁目、三桁目の 1,0 が反転するように石を取ります。

ただし! 壱の山の001 を選択して、右から二桁目、三桁目を反転させると、111 と、
元の個数より石の数が増えてしまいます : 

001 は十進法で 1, 111は十進法で 7             

今は石を取ることによって, 山の石の個数を変化させるので、元の個数より増えてしまってはいけません。
弐の山の011 を選択しても、右から二桁目、三桁目を反転させると 101 と、元の石の個数より増えてしまう。 


なので、参の山の100 を選択し、右から二桁目と三桁目の1,0 を反転させます。




これで、



となって、確かに 1⊕3⊕2 = 001 ⊕ 011 ⊕ 010 = 0 となっています。
関係式が修復されました。

100 は十進法で 4, 010 は十進法で 2 なので、先手は参の山から2個石を取ればいいのです。

これにより、石の個数は、

壱の山の石: 1 個  弐の山の石:3個  参の山の石: 2個 




やはり、後手は、ここからどのように石を取っても、

 (壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0

という関係式を崩してしまいます。例えば、後手が弐の山から3個の石を全て取ってしまうと、

壱の山の石: 1 個  弐の山の石:0個  参の山の石: 2個 

となります。二進法に直すと、

壱の山の石: 1 個  弐の山の石:0個  参の山の石: 10個.



なので、

(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =11 ≠ 0

と、確かに関係式が崩れています。

次に先手がやるべきは、やはり、「(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0」
という関係式を修復すること。やり方もさっきと一緒です。

今、右から一桁目、二桁目の1の個数が奇数個となっているので、参の山の石の個数 `10' の 右から一桁目、二桁目の
1,0 を反転させて、 `01' としてやれば、各桁の1の個数が偶数個になり、



と、(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0 となります。

`10' は十進法で2, `01' は 1 なので、先手は参の山から 1個石を取ればいいことにわかり、

壱の山の石: 1 個  弐の山の石:0個  参の山の石: 1個 

となります。

後手は、壱、または参の山から石を1個取るしかなく、例えば壱の山から取ると、

壱の山の石: 0 個  弐の山の石:0個  参の山の石: 1個 

となます。0 ⊕ 0 ⊕ 1 = 1 ですね。なので、

(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0

という関係式が、またまた崩れます。

先手は最後の1個を参の山から取ることで、

壱の山の石: 0 個  弐の山の石:0個  参の山の石: 0個 

となり、勝利となります。ちなみにこの状況でも、0 ⊕ 0 ⊕ 0 = 0 
なので、(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0 が修復されています。


こんなふうに、

先手は、「(壱の山の石の個数) ⊕ (弐の山の石の個数) ⊕ (参の山の石の個数) =0」となるように石を取る



後手は、どう石を取ってもこの関係式を崩してしまう



先手は、この関係式を修復するように石を取る



後手、崩す



先手、修復



・・・

の繰り返しで、後手を「どう石を取っても関係式を崩してしまう」という状態に閉じ込めてしまうんですね。

先手は、「石を取った瞬間、(壱の山の石の個数)⊕(弐の山の石の個数)⊕(参の山の石の個数)=0」となる状態、
後手は、「石を取った瞬間、(壱の山の石の個数)⊕(弐の山の石の個数)⊕(参の山の石の個数)≠0」となる状態
がずっと保たれる。

そのため、「石を取った瞬間、壱の山、弐の山、参の山の石の個数全てが 0 になり、
(壱の山の石の個数)⊕(弐の山の石の個数)⊕(参の山の石の個数)=0 ⊕ 0 ⊕ 0=0」となれるのは
先手だけ、つまり先手が絶対に勝てる、ということなのです。


今は、最初の三つの山における石の個数が、「(壱の山の石の個数)⊕(弐の山の石の個数)⊕(参の山の石の個数)≠0」
となっている場合を考えました。

先の定理によると、最初に「(壱の山の石の個数)⊕(弐の山の石の個数)⊕(参の山の石の個数)=0」
となっている場合は、後手必勝になるのでした。

その理由は、最初に「(壱の山の石の個数)⊕(弐の山の石の個数)⊕(参の山の石の個数)=0」となっている場合、
先手はどのように石を取っても、「(壱の山の石の個数)⊕(弐の山の石の個数)⊕(参の山の石の個数)=0」という
関係式を崩してしまうからです。

後手は、先手が崩したこの関係式を修復するように石を取っていくことで、絶対に勝つことができます。

先手が、「(壱の山の石の個数)⊕(弐の山の石の個数)⊕(参の山の石の個数)=0」という関係式を崩す



後手が、「(壱の山の石の個数)⊕(弐の山の石の個数)⊕(参の山の石の個数)=0」となるように石を取る



先手が、崩す



後手、修復


と、さっきと真逆の関係でゲームが進んでいき、後手が絶対に勝てる、というトリックなのですね。





二進和を駆使することで、必勝法が作れてしまう、というお話でした。


二人で交互に石を取っていく、というようなシンプルなゲームも、「絶対勝ちたい!」と
必勝法を探っていくと、そこに数学が生まれることもあるんですね。



ということで、今日はここまで!








参考文献
・一松 信、「石とりゲームの数理」

↑今回の記事は、こちらの本の第一章を参考にしました。
いろいろなゲームの必勝法と、そこに隠された数学が学べる本です。
今回の記事では、例えば「なぜ後手が石を取ったら必ず関係式が崩れるのか」

など、しっかり説明していない部分がいくつかあります。そういった詳細を学びたい方は、
こちらの本をどうぞ。



あぺんでぃくす1



今回ご紹介した 二進和 ⊕ は、通常の足し算 + と、同じような性質を持ちます。

例えば、通常の足し算は、a + b = b + a と、足す順番を入れ替えてOKですが、
二進和も同じように、a ⊕ b = b ⊕ a と、計算する順番を入れ替えてOKです。

また、通常の足し算は、三つ以上の数字を足し算しようとするとき、

(a + b) + c = a + (b + c)

と、最初に前半二つを計算してから三つ目の数字を足すのも、後半二つを計算してから一つ目の数字を足すのも、
同じ結果になります。二進和も同様で、 

(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

となります。


あぺんでぃくす2



今回のお話は、3つ以上の山を使った 「n山崩し」にも適用できます。
 
つまり、

(壱の山の石の個数)⊕(弐の山の石の個数)⊕・・・⊕(n の山の石の個数)≠0

となっているときは先手必勝で、

(壱の山の石の個数)⊕(弐の山の石の個数)⊕・・・⊕(n の山の石の個数)=0

は後手必勝です。

その戦法は、やはり「(壱の山の石の個数)⊕(弐の山の石の個数)⊕・・・⊕(n の山の石の個数)=0」
となるように石を取り続ける、というものです。




Comment
やってみよう
やってみよう
2020-01-01 13:07:02ID:166968

>>サバトラ::さん

明けましておめでとうございます。
今年もどうぞよろしくお願いします!
この計算を暗算でやろうとすると相当難しそうですね;
要領だけでもOKです!(^^)

サバトラ
サバトラ
2020-01-01 11:50:47ID:166940

明けましておめでとうございます。♬
今年も宜しくお願いします。(^^)

勝ち方の要領はわかっても、
数式になると難しい〜…わかりませんでした。\(//∇//)\
遊びにも数学役に立つの凄いです!(*'ω'*)

やってみよう
やってみよう
2019-12-28 20:27:05ID:166328

>>ぺぺ α::さん

ありがとうございます。
確かに、難しいですよね。雰囲気を掴んでいただければOKです(^^)

ぺぺ α
ぺぺ α
2019-12-28 17:59:52ID:166306

直感人間の僕には分かりそうで、なかなか難しいです(^_^;)
でもなんとなく分かる感じです♫

やってみよう
やってみよう
2019-12-28 17:37:24ID:166301

>>わんこイン.nem::さん

自分も最初に学んだとき、まさか二進法が出てくるとは思いもしませんでした。
石取りゲームで連勝し続けてる人がいたら、間違いなくこの話を知ってる人ですね!

わんこイン.symbol
わんこイン.symbol
2019-12-28 14:12:57ID:166296

こんな単純なゲームにも、必勝理論があるなんて驚きです。
勝つべくして勝つんですよね。
わかってる人は!!

やってみよう
やってみよう
2019-12-27 22:44:02ID:166226

>>オーウェン::さん

笑いましたw ありましたねそんなセリフ!
福永は良いキャラクターでした!

オーウェン
オーウェン
2019-12-27 22:27:43ID:166221

めちゃくちゃ頭に浮かんだライアーゲーム。
福永がなおちゃんに「勝つか負けるか五分五分だからやろうよ」って提案してそう(笑)

やってみよう
やってみよう
2019-12-27 22:18:09ID:166219

>>YUTO::さん

確かに!カイジいいですねw 
昔放送されてた、「ライアーゲーム」とか「トリック」にも合うかも!

YUTO
YUTO
2019-12-27 21:59:01ID:166217

何かのゲーム系のドラマで扱って良さそうですね!!
(例えば、カイジとか・・・)

この記事を書いた人
数学関連の記事が多めです。