コントラクトブリッジのオークション
今回のネタはコントラクトブリッジです。知らない人にはさっぱりだと思いますが、がんばって知らない人向けに書きます。
まず、以下のゲームを考えます。
1. 2人のプレイヤーが、それぞれ1~Nの数字の書かれたN枚のカードを持つ
2.プレイヤーは交互にカードを1枚ずつ出す
3. 最初のプレイヤーは好きなカードを出せるが、以降は直前より大きい数字を出す
4.カードが出せないor出したくない時はパスを宣言する
5.どちらかのプレイヤーがパスした時点でゲームを終了する
★ブリッジプレイヤーはここからしばらく読まなくていいです
このゲームの目的は勝敗を決めることではなく、自分の出したカードによって相手に情報を伝えることです。
例えば、最初の選択肢は1~Nとパスなので、N+1通りの情報を伝えることができます。次に相手がNのカードを出したりパスしたりすればゲーム終了ですが、そうでなければまたいくつかの選択肢が発生するため、さらに相手に情報を伝えることができます。
伝える情報はこの話には関係ありません。誕生日とか電話番号とか、数字で決められるものなら何でも良いですし、あらかじめ番号を振っておけばそれ以外も何でもです。
本当は双方向に情報を伝え合うのですが、今回は先攻プレイヤーが一方的に後攻に数値を教えることにします。
先攻の動きを考える前に、後攻の動きは明らかに「先攻が何を出しても、それの一つ上の数字を出す(出せない時のみパス)」に確定します。後攻はただの置物なので、先攻の選択肢を減らさないことだけ考えるとこれしかありません。
この状態で、先攻プレイヤーはゲーム終了までに何通りの行動が取れるか、が今回の問題です。
※一応言っておきますが、本当のコントラクトブリッジはこんな無意味なクソゲーではありません。もっと奥深く頭を使うクソゲーです。
★ブリッジプレイヤーはここからどうぞ
N=1のとき、先攻の取れる手は1を出すかパス(以下、P)しかなく、それで終わりなので2通りです。
N=2のとき、先攻はP,1,2の3通りが選べます。1を選んだ場合のみ後攻が2を出しますが、次はPが確定なので選択肢が増えるわけではありません。3通りです。
N=3のとき、1手目はP,1,2,3の4通り。1を出したときのみ3とPの選択肢が増えるので、合計5通り
記号で表すとこんな感じ
N=1 : P,1
N=2 : P,1,2
N=3 : P,1→P,1→3 ,2,3
N=4 : P,1→P,1→3,1→4,2→P,2→4,3,4
数値の上下をひっくり返す、すなわち、前より小さい数字を出すゲームだとするとわかりやすくなります。以下、矢印を省略します。
N=1 : P,1
N=2 : P,1,2
N=3 : P,1,2,3P,31
N=4 : P,1,2,3P,31,4P,41,42
N=5 : P,1,2,3P,31,4P,41,42,5P,51,52,53P,531
続けていくとわかりますが、フィボナッチ数で増えていきます。
N枚のカードを持っているときはN-1枚の時の動きすべてが可能で、かつ最初にNを置いてからN-2枚の時の動きがすべてできる、と考えれば分かりやすいと思います。
とりあえず正式な証明は置いておいて、ゲーム終了時に先攻が出したカードから一つの数値を導き出す方法が必要です。例えば先攻が853Pと出したとき、これは何番だ、というのをさくっと計算できる方法を考えます。
N=4 : P,1,2,3P,31,4P,41,42 のように辞書順で並べた場合、Nが大きくなっても先頭は変わらず、常に末尾に新しい手が追加されていくことになります。このため、先攻の手は辞書順で番号を振っていくのが良さそうです。
P=0と読み替えて0から順に番号を振っていくと、N=3までは出したカードの合計がそのまま番号になるので良い感じです。
N=4でずれますが、4を5に読み替えると補正できます。同様に、N=5では4を5に、5を8に読み替えればOKです。
並べると
1→1
2→2
3→3
4→5
5→8
はい。これもフィボナッチ数です。
まとめると、
・N枚のカードでは、(N+2番目のフィボナッチ数)までの数値を伝えられる
・計算方法は、(出したカードの数値+1)番目のフィボナッチ数の合計
この後ちゃんとした証明を書こうと思ったのですが、既にありました。
「ゼッケンドルフの定理」というらしいです。Wikipediaに証明があるのでそっちを読んでください。
★ここ最後までからブリッジの話
1Cをアスキングの開始にすると14930352まで聞けます。電話番号とまでは行きませんが、JCBLナンバーくらいなら余裕ですね。
お誕生日コンベンションなら12stepあればOK。13step目をパスの代わりにすることで最終コントラクトを保証できます。1NTや2Cオープンに対して7NTを確信したときの5Dとかに入れておきましょう。