パズルの国のアリス

悩ましい入札ゲーム(問題)

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

 アリスが面白いことはないかと鏡の国をうろついていると,見覚えのある雑貨屋の前を通りかかった。前に来た羊の老婆の店だと思い出し,アリスは,何か掘り出し物はないかと入ってみたが,目を凝らした棚からは,例によって品物が消えてしまう。

 「まったくあんたは何が買いたいんだね」と羊。

 ほしいものを思いつこうとアリスがむなしい努力をしていると,トウィードルダムとトウィードルディーの兄弟が息せき切って飛び込んできた。

 「ガラガラ! ガラガラ! 新しいのが入ったかい?」異口同音に叫ぶ。まったくこの2人っていつもガラガラなんだからとあきれながら,羊があごで示した棚をアリスが見ると,さっきまで何もなかったのに今は新品のガラガラが1つ鎮座している。

 「1つだけ?」とダム。「当たり前さ。この子みたいにほしいものがわからないのも困りものだけど,あんたたちみたいにいつも同じものじゃ,在庫のたまる余地なんかあるもんかい」と羊。

 それを聞いてディーがダムをちらっとにらんだのを見て,羊は続ける。「どうせあんたら,自分が買うって譲らないんだろうね。では,今日は,ちょっとだけ商売っ気の入った,競りがらみのゲームで決着をつけようか?」

 アリスも双子もゲームと聞いて目を輝かせた。「銀貨何枚で買うかまず2人で入札する。普通は高い値をつけたほうに売っておしまいなんだけど,そうじゃなくて高い値をつけたほうが先手で次のようなゲームをするんじゃよ。入札枚数からなる2つの銀貨の山を作って,先手は,銀貨が多いほうの山から少ないほうの整数倍の銀貨を引いてその枚数を減らす。後手は,残った2つの山に対して同じことをする。こうして交互にプレーして山の1つを0枚にしたほうが勝ちで,最初の入札額でガラガラを手に入れるというのはどうじゃね? もちろん最初の入札が同額の場合は引き分けでやり直しじゃが」。

 読者には,このゲームの分析をお願いしよう。まずウォーミングアップとして,ダムの入札が銀貨5枚とわかっている場合,ディーが一番安い価格でガラガラを手に入れるには入札額をいくらにすればよいだろうか? また,ダムの入札が5枚を超えることがないとわかっている場合,ディーが確実にガラガラを手に入れるための入札額はいくらだろうか? もっと一般には,ダムm枚,ディーがn枚の入札をした場合,ディーが勝つための条件はどういうものになるだろうか?

解答はこちらです