パズルの国のアリス

悩ましい入札ゲーム(解答)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 ダムの入札が5枚とわかっている場合を考えてみよう。ディーの入札が1枚なら,ダムが先手となり,いきなり5枚の銀貨の山を0枚にされてディーの負けだ。 ディーの入札が2枚なら,ダムが減らせるのは偶数枚だから,いきなり0枚にされることはないが,5枚を3枚に減らすのが良い手で,これに対してディーは3枚をさらに1枚に減らすことしかできない。その結果,2枚の山を0枚にされて,ディーの負けだ。ディーの入札が3枚なら,ダムの初手は5枚を2枚にするしかないが,その結果3枚と2枚の山が残るので,先と同様にディーの負けだ。ディーの入札が4枚なら,ダムの初手は5枚を1枚にするしかない。次の手でディーは4枚の山を0枚にして勝つことができる。こうして,ダムの入札が5枚の場合にディーが勝てる最低入札額は銀貨4枚ということになる。一般に相手の入札額n(≧3)に対して,n-1の入札は良い手で,後手にはなるが,相手はn枚を1枚にするしかないので2手目で勝てる。

 さて一般には相手の入札額はわからないので,確実に勝つことは無理だが,額の上限がわかっているとやりようがある。簡単なやり方は,可能性がある相手の入札額全ての最小公倍数で入札することだ。例えば,ダムの入札が5枚を超えることがないなら,1・2・3・4・5の最小公倍数60で入札することで先手を取り,初手でいきなり60枚の山を0枚に減らして勝つことができる。

 しかし,銀貨60枚はいかにも大金なので,もっと少額で勝つ方法がないだろうか。先に検討したように,ダムの入札が5枚の場合,4枚未満では勝てない。また4~6枚ではダムが3~5枚で入札する可能性があるので,確実とはいえない。では7枚ではどうか?ダムの入札が5枚なら,ディーは先手で,7枚を2枚にするしかない。その結果,ダムの手番で5枚と2枚が残り,5枚を3枚にするのが良い手だったからダムの勝ちになる。ディーの入札が8枚だった場合も,ダムの入札が5枚なら似たような経過をたどりダムの勝ちになる。では9枚の場合は?この場合,ダムの入札が5枚なら,ダムの手番で5枚と4枚が残り,先に見たようにディーの勝ちになる。ダムの入札が4枚でも,ダムの手番で5枚と4枚が残るようにできる。ダムの入札が3枚なら,いきなり9枚を0枚にしてディーの勝ちだ。ダムの入札が1~2枚でも,ディーが勝てることは容易にわかる。

 というわけで,ダムの入札が5枚以下とわかっている場合に,ディーが確実に勝つための最低入札額は9枚である。しかし,少し調べてみればわかるが,この場合のディーの入札額は,10枚でも11枚でも,要は9枚以上ならよいのだ。この結果を含めてこれまでの検討から予想できることは, 2つの山の銀貨の差が十分あれば先手が勝ちそうだということである。

 少ないほうの山の銀貨枚数をm,多いほうをnとする。「比n/mがある値αを超えていれば先手勝ち,それ以下なら後手勝ち」といえると簡単でよい。もしそのようなαが存在するならその値は2未満である。なぜなら,n/m=2のときは,n 枚の山をいきなり0枚にすることで先手が勝てるからだ。したがって,後手勝ちの局面が上の条件を満たすなら,そのときの先手が打てる手はn枚の山をnm枚にすることだけである。もとの局面の比をn/mrとすると,このとき新しい局面の比はm/( nm)=1/( r-1)である。これらが等しくなるのはrがいわゆる黄金比

のときだが,これは無理数だから決してn/mに等しくなることはない。また,rφなら1/(r-1)<φrφなら1/(r-1)>φであり,φは上のαが満たすべき条件に合致する。

 実際,先のn=5やm=5の具体的なケースに照らしてみても,αφとすると,先手勝ち,後手勝ちがうまく分類されている。

 こうして有望そうなαの値が見つかったので,証明を試みてみよう。nmφとする。nmの倍数ならもちろん先手の勝ちである。そうでない場合,正の整数pによってnpmk(0<km)と書ける。先手は,m/kφならnkに減らし,m/kφならnkmに減らすことができ,どちらの場合も新しい局面の比がφ以下であることは容易に示される。逆にnmφとしよう。このとき先手はnnmにするほか手がない。この結果,比m/(nm)はφ以上となる。あとは数学的帰納法によって証明を完結させればよい。

 この結果は,奇妙といえばいえよう。相手に勝ちたいと思うとき,かなりかけ離れた大きな額で入札してもよいが,相手の入札額が予測できればそれよりちょっとだけ少ない額を提示してもよいということだから。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004)
Mathematical Mind-Benders(2007) P. Winkler著

問題はこちらです