数学の部屋へもどる◆広島県 清川 育男 さんからの解答。
【問題１】
先手が山Bから１個取って、後手に手を渡す。
先手必勝です。
【問題２】
後手必勝。
| 先手 | 後手 |
| 山Aから１個取る | 山A、山Bから２個ずつ取る |
| 山Aから２個取る | 山A、山Bから３個ずつ取る |
| 山Aから３個取る | 山Bから２個取る |
| 山Aから４個取る | 山Bから１個取る |
| 山Aから５個取る | 山Bから３個取る |
| 山Bから１個取る | 山Aから４個取る |
| 山Bから２個取る | 山Aから３個取る |
| 山Bから３個取る | 山Aから５個取る |
| 山A、山Bから１個ずつ取る | 山Aから３個取る |
| 山A、山Bから２個ずつ取る | 山Aから１個取る |
| 山A、山Bから３個ずつ取る | 山Aから２個取る |
【問題３】
山A １個 山B ２個
山A ２個 山B １個
山A ３個 山B ５個
山A ５個 山B ３個
山A ４個 山B ７個
山A ７個 山B ４個
山A ６個 山B １０個
山A １０個 山B ６個
【おまけ１、おまけ２】
フィボナッチ数列に関係しています
| 順番 | １ | ２ | ３ | ４ | ５ | ６ | ７ | ８ |
| フィボナッチ数 | １ | １ | ２ | ３ | ５ | ８ | 13 | 21 |
山A、山Bが連続したフィボナッチ数でその和が
４，６，８，・・，２Ｎのフィボナッチ数になっているときです
７個と４個の意味づけが？
先手が１つの山になるようにとれば、後手はその山を全部取ればよい
先手が２つの山が同数になるように取れば、２つの山を全部取ればよい
それ以外の取り方をしたときは、上記のフィボナッチ数になるように取ればよい
すぐに出来ないときは先手にそれを許さない手を打って次回に備える
先手が圧倒的に有利なゲームですね
それにしても、フィボナッチ数はいろんなところにでてきますね
植物の世界でも
【補足】
Sloane's On-Line Encyclopedia of Integer Sequences で The Wythoff Array and The Para-Fibonacci Sequence を見つけました。
その表をもとに以下のペアを見つけることが出来ます。
| lower | upper | upper-low |
| １ | ２ | １ |
| ３ | ５ | ２ |
| ４ | ７ | ３ |
| ６ | １０ | ４ |
| ８ | １３ | ５ |
| ９ | １５ | ６ |
| １１ | １８ | ７ |
| １２ | ２０ | ８ |
| １４ | ２３ | ９ |
| １６ | ２６ | １０ |
| １７ | ２８ | １１ |
| １９ | ３１ | １２ |
| ２１ | ３４ | １３ |
| ２２ | ３６ | １４ |
| ２４ | ３９ | １５ |
| ２５ | ４１ | １６ |
| ２７ | ４４ | １７ |
| ２９ | ４７ | １８ |
| ３０ | ４９ | １９ |
| ３２ | ５２ | ２０ |
| ３３ | ５４ | ２１ |
| ・・・・・・・・・・ | ||
いろんなことが紹介されています。
拡張型フィボナッチ数列とでも言えばよいのでしょうか。
後手必勝のパターンです。
◆石川県 平田 和弘 さんからの解答
(問題１解答)
A山1個、B山3個 なので先手が次の1手を試行したときのパターンを書くと、
| A山 | B山 | ここでの勝敗 → 結論 |
| ０ | ３ | ここでの先手番勝ち→後手勝ち |
| １ | ２ | ここでの後手番勝ち→先手勝ち |
| １ | １ | ここでの先手番勝ち→後手勝ち |
| １ | ０ | ここでの先手番勝ち→後手勝ち |
| ０ | ２ | ここでの先手番勝ち→後手勝ち |
先手はうまい手、ここでは2番目の手段でいくと先手勝ちとなります。
よって、先手必勝です。
(問題２解答)
準備として、(A山、B山を逆にしても同じですので)
| A山 | B山 | 結論 |
| 0個 | n(≧1)個 | 先手必勝・・・(1) |
| 1個 | 1個 | 先手必勝・・・(2) |
| 1個 | 2個 | 後手必勝・・・(3) |
| 1個 | n(≧3)個 | 先手必勝・・・(4) |
| 2個 | n(≧2)個 | 先手必勝・・・(5) |
| 3個 | 3個 | 先手必勝・・・(6) |
| 3個 | 4個 | 先手必勝・・・(7) |
を確認して、
A山5個、B山3個 なので先手が次の1手を試行したときのパターンを書くと、
| A山 | B山 | ここでの勝敗 → 結論 |
| ４ | ３ | ここでの先手番勝ち→後手勝ち((7)より) |
| ３ | ３ | ここでの先手番勝ち→後手勝ち((6)より) |
| ２ | ３ | ここでの先手番勝ち→後手勝ち((5)より) |
| １ | ３ | ここでの先手番勝ち→後手勝ち((4)より) |
| ０ | ３ | ここでの先手番勝ち→後手勝ち((1)より) |
| ５ | ２ | ここでの先手番勝ち→後手勝ち((6)より) |
| ５ | １ | ここでの先手番勝ち→後手勝ち((4)より) |
| ５ | ０ | ここでの先手番勝ち→後手勝ち((1)より) |
| ０ | ２ | ここでの先手番勝ち→後手勝ち((1)より) |
| ４ | ２ | ここでの先手番勝ち→後手勝ち((5)より) |
| ３ | １ | ここでの先手番勝ち→後手勝ち((4)より) |
| ２ | ０ | ここでの先手番勝ち→後手勝ち((1)より) |
なので、先手はどんなにうまい手を考えても勝てない。
従って後手必勝です。
(問題３)
上記問題２の準備として同様に求めていくと、石数の多いものは少ないものより先手必勝か、後手必勝が求められるので
| A山 | B山 | 結論 |
| 0個 | n(≧1)個 | 先手必勝 |
| 1個 | 1個 | 先手必勝 |
| 1個 | 2個 | 後手必勝・・・(★) |
| 1個 | n(≧3)個 | 先手必勝 |
| 2個 | n(≧2)個 | 先手必勝 |
| 3個 | 3個 | 先手必勝 |
| 3個 | 4個 | 先手必勝 |
| 3個 | 5個 | 後手必勝・・・(★) |
| 3個 | n(≧6)個 | 先手必勝 |
| 4個 | 4個 | 先手必勝 |
| 4個 | 5個 | 先手必勝 |
| 4個 | 6個 | 先手必勝 |
| 4個 | 7個 | 後手必勝・・・(★) |
| 4個 | n(≧8)個 | 先手必勝 |
| 5個 | n(≧5)個 | 先手必勝 |
| 6個 | 6個 | 先手必勝 |
| 6個 | 7個 | 先手必勝 |
| 6個 | 8個 | 先手必勝 |
| 6個 | 9個 | 先手必勝 |
| 6個 | 10個 | 後手必勝・・・(★) |
| 7個 | n(≧7)個 | 先手必勝 |
| 8個 | 8個 | 先手必勝 |
| 8個 | 9個 | 先手必勝 |
| 8個 | 10個 | 先手必勝 |
| 9個 | 10個 | 先手必勝 |
| 10個 | 10個 | 先手必勝 |
となり、上記(★)の、
(A山の個数,B山の個数)＝(1,2),(3,5),(4,7),(6,10)
A山、B山の個数を逆にしても同じです。
(おまけ1)
法則性を探りましたがはっきりとはわかりません。
ただ私が知っている有名な数列は、フィボナッチ数列だけですので、この数列との関係を調べてみました。
その結、(組み合わせ)の一般項はわかりませんが(組み合わせ)第n項は求められます。
フィボナッチ数列
1,1,2,3,5,8,13,21,34,55,89,144,233,・・・
後手必勝の組み合わせを、A山とB山の差およびA山の数がそれより以前にB山に出現したかだけで少し求めると、
(A山、B山逆のパターンを除いて)
(A山,B山)＝
(1,2),(3,5),(4,7),(6,10),(8,13),
(9,15),(11,18),(12,20),(14,23),(16,26),
(17,28),(19,31),(21,34),・・・(A)
となります。
何かフィボナッチ数列に現れる数が見え隠れしています。
そこでまず、
「(a,b)＋(c,d)＝(a＋b,c＋d) (要素ごとの単純な足し算)、
(a(1),b(1))＝(1,2) (現実的に1番目に現れたもの)」
と定義します。
さて、ここで定義のb(1)＝2より、
これをINDEXにした(a(2),b(2))を次のように考えます。
(a(2),b(2))
＝(a(1)＋b(1),a(2)＋b(1))
＝(a(1)＋b(1),(a(1)＋b(1))＋b(1))
＝(3,5)
同様に、b(2)＝5より、
これをINDEXにした(a(5),b(5))を次のように考えます。
(a(5),b(5))
＝(a(2)＋b(2),a(5)＋b(2))
＝(a(2)＋b(2),(a(2)＋b(2))＋b(2))
＝(8,13)
以下、INDEXが飛び飛びではあるが同様に考える。
(a(13),b(13))
＝(a(5)＋b(5),a(13)＋b(5))
＝(a(5)＋b(5),(a(5)＋b(5))＋b(5))
＝(21,34)
(a(34),b(34))
＝(a(13)＋b(13),a(34)＋b(34))
＝(a(13)＋b(13),(a(13)＋b(13))＋b(13))
＝(55,89)
(a(89),b(89))
＝(a(34)＋b(34),a(89)＋b(34))
＝(a(34)＋b(34),(a(34)＋b(34))＋b(34))
＝(144,233)
・
・
となり、これらはフィボナッチ数列の第1項を除いて、2つずつ区切ったもの
(1,2),(3,5),(8,13),(21,34),(55,89),(144,233),・・・と一致し、これを区切りとして考えます。
即ち、
(a(2),b(2))から(a(4),b(4))までは、(a(2),b(2))を基準に、
(a(5),b(5))から(a(12),b(12))までは、(a(5),b(5))を基準に、
(a(13),b(13))から(a(33),b(33))までは、(a(13),b(13))を基準に、
(a(34),b(34))から(a(88),b(88))までは、(a(34),b(34))を基準に、
・
・
計算します。
具体的に、
(a(2),b(2))＝(3,5) より、INDEXをもとに計算するようにして、
3＝2＋1 なので
(a(3),b(3))
＝(a(2),b(2))＋(a(1),b(1))
＝(3,5)＋(1,2)
＝(4,7)
4＝2＋2 なので
(a(4),b(4))
＝(a(2),b(2))＋(a(2),b(2))
＝(3,5)＋(3,5)
＝(6,10)
となり、
(a(5),b(5))＝(8,13) より、INDEXをもとに計算するようにして、
6＝5＋1 なので
(a(6),b(6))
＝(a(5),b(5))＋(a(1),b(1))
＝(8,13)＋(1,2)
＝(9,15)
7＝5＋2 なので
(a(7),b(7))
＝(a(5),b(5))＋(a(2),b(2))
＝(8,13)＋(3,5)
＝(11,18)
・
・
12＝5＋7＝5＋(5＋2) なので、
(a(12),b(12))
＝(a(5),b(5))＋{(a(5),b(5))＋(a(2),b(2))}
＝(8,13)＋(11,18)
＝(19,31)
となり、
(a(13),b(13))＝(21,34) より、INDEXをもとに計算するようにして、
14＝13＋1 なので
(a(14),b(14))
＝(a(13),b(13))＋(a(1),b(1))
＝(21,34)＋(1,2)
＝(22,36)
15＝13＋2 なので
(a(15),b(15))
＝(a(13),b(13))＋(a(2),b(2))
＝(21,34)＋(3,5)
＝(24,39)
・
・
33＝13＋20＝13＋(13＋7)＝13＋(13＋(5＋2)) なので、
(a(33),b(33))
＝(a(13),b(13))＋[(a(13),b(13))＋{(a(5),b(5))＋(a(2),b(2))}]
＝(21,34)＋(21,34)＋(8,13)＋(3,5)
＝(53,86)
となります。
以下、このようにして第n番目の組み合わせがいくらでも求められます。
また、これは上記(A)と一致しています。
(おまけ2)
数は、フィボナッチ数列ならばGoldenNumberしか考えられませんが、関係および理由は上記(おまけ1解答)のとおりです。
(感想)
どうも今一つすっきりしませんので自信がありません。
法則性があるようでないようなので、表計算ソフトでいろいろ分析してみた結果このようになりました。
もしかしたら、組み合わせの一般項は求められるのでしょうか。
例えば(100,○)(または(○,100))としたとき簡単に○を求める方法があるのでしょうか。
(おまけ1)の補足
前回感想欄に書きました、(100,○)または(△,100)に相当する○または△の求め方がわかりました。
昨日、フィボナッチ数列の第1項を除いて2つずつ区切ったものを基準とするとしましたが、言い換えて
1,1,2,3,5,8,13,21,34,55,89,144,233,377,・・・・・
の各項ををa(n)(n＝1,2,・・・・・・)として
このうち、nを奇数として差がa(n)のとき、
(a(n＋1),a(n＋2))が基準になり、これが第a(n)項になると考える。
１.
もし(△,100) とすると、上記基準のうち第2要素が100を超えない最大の基準は
(a(34),b(34))＝(55,89) なので、基準の組み合わせで考えて
(a(39),b(39))
＝(a(34),b(34))＋(a(5),b(5))
＝(55,89)＋(8,13)
＝(63,102) で
これの1つ前の項は
(a(38),b(38))
＝(a(34),b(34))＋(a(2),b(2))＋(a(2),b(2))
＝(55,89)＋(3,5)＋(3,5)
＝(61,99) で
(△,100)となる組み合わせは存在しない。
２.
もし(100,○) とすると、上記基準のうち第1要素が100を超えない最大の基準は
(a(34),b(34))＝(55,89) なので、基準の組み合わせで考えて
(a(60),b(60))
＝(a(34),b(34))＋(a(13),b(13))＋(a(13),b(13))
＝(55,89)＋(21,34)＋(21,34)
＝(97,157) とあたりをつけて
これの2つ後の項は
(a(62),b(62))
＝(a(34),b(34))＋(a(13),b(13))＋(a(13),b(13))＋(a(2),b(2))
＝(a(60),b(60))＋(a(2),b(2))
＝(97,157)＋(3,5)
＝(100,162) で
(100,○)となる組み合わせは○＝162のとき存在する。
例えば、自分が後手番でA山に100個あるとき、B山に162個あれば相手に勝てます。
◆東京都 Asami さんからの解答
第一象限に碁盤の目を置き、ｙ軸方向,χ軸方向に１,２,３,４,５,………のように番号を振る。
碁石を←or↓or左斜め下にいくつか動かすことを交互にやって、
最終的に(０,０)にした方が勝ち。というゲームと同値。
(０,０)に○をつける。
○含む“行,列,右斜め上”のマス目に半直線を(○を除いて)引く。
下から見ていって、線が引かれていない最小の行を選び、その行で、右から見ていって初めて斜め線にぶつかる位置(χ1)を選ぶ。
同様に、左から見ていって、線が引かれていない最小の列を選び、その列で、上から見ていって初めて斜め線にぶつかる位置(ｙ1)を選ぶ。
(位置(χ1),(ｙ1)は明らかに存在し、またｙ＝χに関して線対称な位置にある。)
(χ1),(ｙ1)に○をつけ、 (χ1),(ｙ1)の○含む“行,列,右斜め上”のマス目に半直線を(○を除いて)引く。
下から見ていって、線が引かれていない最小の行を選び、その行で、右から見ていって初めて斜め線にぶつかる位置(χ2)を選ぶ。
同様に、
左から見ていって、線が引かれていない最小の列を選び、その列で、上から見ていって初めて斜め線にぶつかる位置(ｙ2)を選ぶ。
………
………
このようにして(χi),(ｙi)を次々に構成していく。
(位置(χi),(ｙi)は明らかに存在。
また位置(χi-1),(ｙi-1)までがｙ＝χに関して線対称ならば
位置(χi),(ｙi)も線対称。)
このように構成されたすべての○は必勝の位置のはず
(厳密な証明は大変そう)。
またこのようにできた○に基づいて成分表を完成させると、
| χ成分： | 1 | 3 | 4 | 6 | 8 | 9 | 11 | 12 | ・・・ |
| ｙ成分： | 2 | 5 | 7 | 10 | 13 | 15 | 18 | 20 | ・・・ |
あとはこれのｙ＝χで線対称に移動したもの。というわけで
【問題１】は先手必勝
【問題２】は後手必勝
【問題３】は(1,2),(3,5),(4,7),(6,10)とこれらの成分を反転させたもの。
【おまけ】は上の表の部分列としてフィボナッチ数列が現れるんですよね。
どっかの本で読んだことあるけど、ちょっと難しそうですね。
◆北海道 くーりー さんからの解答
【問題１】
先手必勝
【問題２】
後手必勝
【問題３】
「２個と１個」「５個と３個」「７個と４個」「10個と６個」
【おまけ１】
その状況で自分に手番が回って来たら負ける状況の個数の組合せをここでは「ツボ」と呼ぶことにします。
(もちろん両者とも最善手を打つ前提です。)
逆に、ツボの状況にして相手に手番を回せば勝ちとなるわけです。
つまり、「自分の手番後にツボにして相手に手番を渡すことができない(手番前の)組合せ」がツボというわけです。
打てる手は「@片方からある個数を取る」と「A両方から同数取る」の２つですから、この２つの手いずれでもツボにできなければ、それはツボです。
ツボを求める手順として、個数が少ない方から考えて（求めて）行きます。
「最後の１個を取った方が勝ち」ということは「石が０個で手番が回ってきたら負け」ということです。
最も個数の少ないツボは「０個と０個」。
（これはゲームが成立しないけど、負けの定義だから当然。）
これは２数の差が０個でもあります。
さて、次に数の少ないツボはというと、
@「Ａ個(Ａは１以上)と０個」であれば、片方からＡ個取れば「０個と０個(ツボ)」
A２数の差が０の状況「Ａ個とＡ個(Ａは１以上)」でも、両数からＡ個取って「０個と０個(ツボ)」
@とAを避ける最小の組合せ（＝次のツボ）は、
「いずれも０でなく、差が０でない」最小の数の組合せ、
つまり「２個と１個」。
さて、次のツボを考えると、
@２数の一方がこれまでにツボとして出てきた数（０、１、２個）であれば、もう一方から都合の良い数を取ってツボに出来る。
A２数の差が、これまでに出てきたツボの２数の差（０、１個）と同じであれば、両者から都合の良い個数を取ってツボに出来る。
@とAを避ける最小の組合せ（＝次のツボ）は、
「@いずれも０、１、２でなく」
「A差が０、１でない」最小の組合せ、
ということは、少ない方が３で差が２。
つまり「３個と５個」
さて、次は、
「@いずれも０、１、２、３、５でなく」
「A差が０、１、２でない」最小の組合せ
＝少ない方が４で差が３、つまり「４個と７個」
一般化すると、
「@いずれもこれまでにツボとして出てきた数ではなく」
「A差がこれまでに出てきたツボの２数の差でない」
最小の組合せが次のツボとなります。
平たく言うと、
「これまでにツボとして出てきていない１番小さな数」を次のツボの片方にして、それに「１つ前のツボの２数の差より１大きい数」を足した数をもう片方にすれば求められます。
う〜ん、長くなってしまいました。
証明としては未だあちこち抜けているんでしょうね。
でもその前に、そもそもこのやり方で合っているんでしょうか？！
【おまけ２】
| ２ | １ |
| ５ | ３ |
| ７ | ４ |
| １０ | ６ |
| １３ | ８ |
| １５ | ９ |
| １８ | １１ |
| ２０ | １２ |
| ２３ | １４ |
| ２６ | １６ |
平方数（Ａ×Ａ）の相手はＡ×（３×Ａ＋１）／２
？？？
有名な数？？？？ 何でしょう？？ わかりません。
もしかしたら、答自体間違っているんでしょうか？！
◆ 問題へもどる
◆ 今週の問題へ