小六のふたごらが夏休みの宿題で提出したものが、まぁまぁのできだったので小学生から高校生を対称にしたある算数コンテストに出してみたらそこそこの賞を得てしまった。
でも特別賞と2，3の優秀賞しか内容を公開されていない。結構おもしろいできで、かれらも最後の方でいっているようにこんなやり方はネットでないようなので、せっかくだから、親馬鹿の勢いもあってネットに残して置こうと思う。
なお久しぶりのアップでもあり行間が間の抜けたものになっているけど、それはかれらのせいではないのであしからす。
考えたきっかけ
三山くずしというゲームがあります。ルールは次の通りです。
「小石がいくつか三つの山に分けて積んである。二人のプレイヤーが交互に石を取っていく。ただし一度に二つ以上の山から取ることはできない。一つの山からなら何個 取ってもよい。最後に石を取ったプレイヤーが勝ち」
数年前，父からそのゲームのことを教えてもらい，父とやってみましたが，なんどやっても勝てずふたりとも悔しい思いをしたことがあります。
最近，ある雑誌にこのゲームに必勝法があると書いてありました。ひょっとしてその方法を父はずる賢く使っていたのではないかと思い，その必勝法をふたりで考えてみました。
簡単な必勝型を考えた
わかりやすいように，できた形を相手に渡すことを ↑ で ある形を相手から受け取ることを ↓ で表すことにしました。
また三つの山の個数をそれぞれ Ａ，Ｂ，Ｃ とすると （Ａ，Ｂ，Ｃ）で表すことにしました。
またよりわかりやすくするため，受け取りのつながりを表す → を使いました。当たり前のことですが，一山だけ残して相手に渡すと必ず相手はそれを全部取って勝ってしまうので，そのような場合を考えるのをときどき省略しました。
そこで相手に渡すときの必勝型がないか考えてみました。まず思い浮かぶのが （１，１，１） です。
これはたとえば
↑（１，１，１）→ ↓（１，０，１） → ↑（０，０，１） または
↑（１，１，１）→ ↓（１，１，０） → ↑（１，０，０）
などで必ず相手が最後に取る形になり負けてしまいます。
では↑（１，２，１）→ は？ これはたったいま見たように自分が負けてしまうので相手が（１，１，１）の形をこちらに返すことはありません。だから相手が返すのは
↓（１，０，１）→ か ↓（０，２，１）→ ですが ↓（１，０，１）→↑（０，０，1）で相手は必ず勝つので，これを返してくるはずです。だから
↑（１，２，１）→ は 負けです。
では ↑（１，２，２）→ は？
（１，２，１）はたったいま見たようにこれを相手に示せば負けなので相手がその形を渡すことはありません。だから
↑（１，２，２）→↓（１，２，１）または
↑（１，２，２）→↓（１，１，２）はありません。
だから↑（１，２，２）→ のあとは ↓（１，２，０） か ↓（０，２，２）になります。これは（１，２，０）と（０，２，２）は山が二つになったことになります。では（１，２）と（２，２）のそれぞれの ↑ ↓ はどうなっていくのだろうと考えていると，あることに気づきました。
↑（１，２，１）→ を考えたときにも↓（１，０，１）→ か ↓（０，２，１）→ の形が出てきています。これも二つの山になっているわけで，まず二山くずしの必勝型があるか考える必要がありそうだということです。
二山の必勝基本型を考える
これもまず思い浮かぶのが （１，１） です。これは簡単で ↑（１，１） → ↓（０，１）と必勝型です。では最初の山をひとつ増やしてみます。
↑（２，１） → ↓（１，１） これは相手から必勝型を出されることになり負けです。
さらに続く数は以下のように考えられます。
↑（３，１） → ↓（１，１）
↑（４，１） → ↓（１，１）
－－－－－－－－
↑（ｎ，１） → ↓（１，１）
だから（ｎ，１）の形で必勝型は （１，１）だけです。
次に（１，２）の形を考えましたが，これは（ｎ，１）で ｎ＝２ のとき一度考えているので実際は（２，２）から見ればいいことになります。
↑（２，２） → ↓（１，２）→ ↑（１，１） で（２，２）は必勝型です。
そのあとに続く数は以下のように考えられます。
↑（３，２） → ↓（２，２）
↑（４，２） → ↓（２，２）
－－－－－－－－
↑（ｎ，２） → ↓（２，２）
相手から必勝型を出されることになり負けです。
だから（ｎ，２）の形で必勝型は （２，２）だけです。
次に（１，３）の形を見ますが，これは （１，２）と （１，３）は（ｎ，１）で ｎ＝２とｎ＝３ のとき一度考えているので実際は（３，３）から見ればいいことになります。
すると同じように （ｎ，３）の形での必勝型は （３，３）ということになります。
以下も同じで，だから二山くずしの必勝型は （ｎ，ｎ）であることが分かりました。
三山の必勝型を考える
簡単な形は↑（１，１，１）でしたが，→↓（０，１，１）になり相手が二山くずしの必勝型を出すのでこちらの負けです。
次にひとつ増やした場合を考えようとしましたが，少し戸惑ってしまいました。
というのはひとつ増やしたときは （２，１，１） なのか （１，２，１）なのか，（１，１，２）なのかこれまではっきりと考えていないことに気づきました。
だから数え上げの仕方を樹形図を使って考えてみました。
（１，１， ）－（１，１，１）
（１，１，２）
（１，１，３）
－－－－－－－
（１，１，ｎ）
（１，２， ）－（１，２，１）
（１，２，２）
（１，２，３）
－－－－－－－
（１，２，ｎ）
（１，ｍ， ）－（１，ｍ，１）
（１，ｍ，２）
（１，ｍ，３）
－－－－－－－
（１，ｍ，ｎ）
これらを数え上げたあと
（２，１， ）－（２，１，１）
（２，１，２）
（２，１，３）
－－－－－－－
（２，１，ｎ）
という順に考えればいいと思いました。
だから（１，１，１）をひとつ増やした場合は（１，１，２）を考えることにしました。
これは（１，１，１）と同じように→↓（０，１，１）となり，さらには（１，１，ｎ）はすべて負け型と分かります。
次に考える場合は（１，２，１）です。これも
↑（１，２，１）→ ↓（１，０，１） で負けます。
次の ↑（１，２，２）も → ↓（０，２，２） で負けです。
次の ↑（１，２，３）は少し複雑になり，こちらが自滅しないような場合分けが必要でした。
↑（1,2,3）→ ↓（0,2,3）→↑（0,2,2）
↑（1,2,3）→ ↓（1,1,3）→↑（1,1,0）
↑（1,2,3）→ ↓（1,0,3）→↑（1,0,1）
↑（1,2,3）→ ↓（1,2,2）→↑（0,2,2）
↑（1,2,3）→ ↓（1,2,1）→↑（1,0,1)
↑（1,2,3）→ ↓（1,2,0）→↑（1,1,0）
やったー！ 三山くずしの初めての必勝型が見つかりました。
次に考えるのは （１，２，４）です。でもこれは
↑（１，２，４）→ ↓（１，２，３）と必勝型を相手から出されることになり負けです。
同じように
↑（１，２，４）→ ↓（１，２，３）
↑（１，２，５）→ ↓（１，２，３）
－－－－－－－－
↑（１，２，ｎ）→ ↓（１，２，３）
で （１，２，ｎ）の形の必勝型は （１，２，３）だけと分かりました。
次に考えるのは （１，３，１）ですがこれは （１，１，ｎ） を見たとき、ｎ＝３で一度考えていることになります。また次の （１，３，２）も－これは必勝型でした－（１，２，ｎ）を見たとき、ｎ＝３ で一度考えていることになります。次の（１，３，３）は → ↓（０，３，３）なので考えるのは（１，３，４） とそれ以降の組み合わせです。
でも（１，３，ｎ）は → ↓（１，３，２）で負けです。だからｎが４以上の（１，３，ｎ）には必勝型がありません。
次に考えるのは （１，４，１）ですが，これも同じように （１，１，ｎ）を見たとき、ｎ＝４ で一度考えています。次の（１，４，２）も （１，２，ｎ）を見たとき、ｎ＝４ で一度考えていて，次の（１，４，３）も （１，３，ｎ）を見たとき、ｎ＝４ で考えています。次の（１，４，４）は → ↓（０，４，４）なので考えるのは（１，４，５） とそれ以降の組み合わせです。
↑（１，４，５）も少し複雑になり，これもこちらが自滅しないような場合分けが必要でした。
↑（1,4,5）→↓（0,4,5）→↑（0,4,4）
↑（1,4,5）→↓（1,3,5）→↑（1,3,2）
↑（1,4,5）→↓（1,2,5）→↑（1,2,3）
↑（1,4,5）→↓（1,1,5）→↑（1,1,0）
↑（1,4,5）→↓（1,4,4）→↑（0,4,4）
↑（1,4,5）→↓（1,4,3）→↑（1,2,3）
↑（1,4,5）→↓（1,4,2）→↑（1,3,2）
↑（1,4,5）→↓（1,4,1）→↑（1,0,1）
↑（1,4,5）→↓（1,4,0）→↑（1,1,0）
最後はすべて必勝型で（１，４，５）は三山の二つ目の必勝型だとわかりました。
次は（１，５，１）ですが，いままでと同じように（１，５，６）から考えればいいとわかりました。でもこれも同じように相手から（１，５，４）の必勝型を返されることになり負けになることがわかります。
次は（１，６，１）ですが，いままでと同じ理屈で（１，６，７）から考えました。
↑（１，６，１）も少し複雑になり，これもこちらが自滅しないような場合分けが必要でした。
↑（1,6,7）→↓（0,6,7）→↑（0,6,6）
↑（1,6,7）→↓（1,5,7）→↑（1,4,5）
↑（1,6,7）→↓（1,4,7）→↑（1,4,5）
↑（1,6,7）→↓（1,3,7）→↑（1,3,2）
↑（1,6,7）→↓（1,2,7）→↑（1,2,3）
↑（1,6,7）→↓（1,1,7）→↑（1,1,0）
↑（1,6,7）→↓（1,6,6）→↑（0,6,6）
↑（1,6,7）→↓（1,6,5）→↑（1,4,5）
↑（1,6,7）→↓（1,6,4）→↑（1,5,4）
↑（1,6,7）→↓（1,6,3）→↑（1,2,3）
↑（1,6,7）→↓（1,6,2）→↑（1,3,2）
↑（1,6,7）→↓（1,6,1）→↑（1,0,1）
最後はすべて必勝型で，ということは（１，６，７）は必勝型です。
見つけた！！
これまでの必勝型をまとめてみます。
（１，２，３）（１，４，５）（１，６，７）
なんだか分かってきました。きっと次の必勝型は
（１，８，９）のはずです。
いままでの考えを繰り返すと（１，６，７）の次の必勝型を考えるのは（１，７，１）からです。
でもいままでと同じ理由で↑（１，７，８）から考えればいいことになります。でもこの形はいままで通り →↓（１，７，６）になり負けてしまうのです。
だから次の（１，８，１）を考えることになります。これも（１，８，９）から考えることになります。
↑（１，８，９）の１個だけの山を取って返すときは →↓（０，８，９）→↑（０，８，８）で勝ちです。また →↓（１，８，８） は ↑（０，８，８）で勝ちます。
問題はそれ以外の８個か９個の山から取って返す場合です。
難しそうでしたが，ふたりでいろいろ話しているうちに規則性を見つけました。
８と９は，９を最初に考えると９，８，だから奇数とそれより１少ない偶数です。
ということは相手が８と９のどちらの山から取ってもまた奇数とそれより１少ない偶数の形にすることができ，それはいままで分かった必勝型（１，２，３）（１，４，５）（１，６，７）のどれかです。
だから（１，奇数，その奇数より１少ない偶数）の形でそのひとつ前の形が必勝型であるなら，その形は必勝型になるはずです。
ということで、お待たせしました。発表します。
これが三山くずしの必勝法だ
１）最初にひとつの山を１個にする
２）もし相手が二山の状態を作れば，（ｎ，ｎ）の形にする
３）もし相手が１個の山以外から取れば １個以外の二山を奇数個とその奇数－１個の形にする
インターネットで調べてみた
三山くずしの必勝法がないか、インターネットを利用しましたが，調べた限りではわたしたちのやり方は見つかりませんでした。そのかわり，２進法の足し算に似たやり方で桁を繰り上げないような計算で必勝型を作るというものがありました。
たとえば
（４，３，７）の山があったとします。これは２進法で
（１００，１１，１１１）です。
２進法でそれぞれの山のを足すと
１００
０１１
１１１
——–
１１１０
ですが，桁を繰り上げないと
１００
０１１
１１１
——–
０００
になります。
こうした計算で０だけの形にできれば，それが必勝型だというのです。
実際に二人でやってみました。先手がその必勝法を知っていて，もうひとりは知らないということでやった結果をいくつか書きます。最初の三山の個数は適当にしました。（００００）などと書かれているのは上にある三山の合計を繰り上げのない２進法で計算したものです。
確かに勝ちましたすが、どれもとても大変でした。また結局最後は、今回分かった必勝法と同じ形になると思いました。
最初（１２，７，２１）→↑（１２，７，１１）→↓（１２，５，１１）→↑（１２，５，９）→↓（７，５，９）→↑（７，５，２）→↓（６，５，２）→↑（６，４，２）→↓（５，４，２）→↑（５，４，１）
最初（１４．８．１１）→↑（１４、４，１１）→
↓（１４，４，９）→ ↑（１３，４，９）→↓（１３，４，７）→↑（１１，４，７）→↓（１１，４，３）→↑（１０，４，３）→↓（７，４，３）→↑（３，４，３）→↓（３，２，３）→↑（１，２、３）
最初（１３．９．６）→↑（１１，９，６）→
↓（１１，８，６）→ ↑（１１，８，２）→↓（７，８，２）→↑（７，８，１）→↓（７，５，１）→↑（５，４，１）
最初（１１１１０）→↑（００００）→↓（００１０）→↑（００００）→↓（１０１１）→↑（０００）→↓（００１）→↑（０００）→↓（０１１）→↑（０００）
最初（１１０１）→↑（００００）→
↓（００１１）→ ↑（００００）→↓（１１００）→↑（００００）→↓（１０１０）→↑（００００）→↓（１０１）→↑（０００）→↓（１０）→↑（００）
最初（００１０）→↑（００００）→
↓（０１０１）→ ↑（００００）→↓（１１０１）→↑（００００）→↓（０１１）→↑（０００）
まとめ
このやり方を見つけるのに、きちんと数え上げることがとても大切だと感じました。
父はどういう風にやっていたか聞くと、この２進法のような計算をしていたということでした。以前の対戦で父がテーブルの片隅でなにかこそこそやっていて、ときに「あ，間違えた」などといっていたことも思い出しました。でもなぜそうすれば勝つのかは知らないらしいです。
二人でその方法を使って実際にやってみると相手に勝つまでにかなり面倒な計算をしました。相手が必勝法を知らないなら，今回分かった方法が簡単で絶対いいと思いました。
でもなぜ２進法のような計算が必勝型になるのかも、気になります。
わたしたちのやり方は ひとつの山を１個 にすることから始めました。でもその山を２個以上にしたときのことを考えていませんでした。
きっとそれをていねいに数え上げていくと２進法のようなやり方になっていくような気がします。
参考にしたホームページ
三山くずしの数理とゲームマシン http://maicommon.ciao.jp/ss/dscrtMath2/nim_hs/index.htm （見た日 2018年8月14日）