connecting...
Google translation for articles :
16 NEMBER donated to you!!

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

nem408xem (16) 410 13 4




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

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



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

 


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

・先攻の人は、三つの山の中から一つの山を選択し、そこから石を取るよ。
 何個石を取ってもいいけど、必ず一個以上は取らないとダメ。一つの山の石を全部取っても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」
となるように石を取り続ける、というものです。




Why don't you get crypt currency 'nem' by posting your blog article?

nemlog is blog posting service which has donation feature by crypt currency nem.
nemlog was launched to create environment which can be donated nem among NEMbers via blog articles.
Let's get nem by posting good blogs.

Nem prize event is being held frequently, Please join us on this opportunity!

nemlog registration from here
Register
Comments from NEMber
やってみよう
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::さん

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

わんこイン.nem
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
2019-12-27 21:59:01ID:166217

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

NEMber who posted this article

「やってみよう」は、プログラマであるタノウエと、数学を勉強しているカナクボが、共同で管理しているアカウントです。
勉強をして身に付けた NEM の知識や数学の話題を、随時投稿していく予定です。
35771
0

Why don't you read following articles?