王選会議 解説
ドパおじ数学パズル工房
元になった問題
このゲームは「二人の保安官パズル」を元にしています。二人の保安官が、それぞれ8人の容疑者を2人まで絞り込み、2人のリストに共通する1人が犯人です。二人は盗聴されている電話で話し合い、盗聴者には犯人を特定させずに、自分たちだけが犯人を知ろうとします。
この問題は D. Beaver、S. Haber、P. Winkler の論文「On the Isolation of a Common Secret」に載っているもので、Winkler の数学パズルの本でも紹介されています。ここで紹介する解き方は、その本の解答を、このゲームのコマンドに置き換えたものです。
鍵になる表
8人を2人ずつ4組に分ける分け方を、7通り並べた表を使います。28通りある2人組が、表の中にちょうど1回ずつ現れるように作ります。
| 列 | 4つの組 | |||
|---|---|---|---|---|
| 0 | [1,2] | [3,4] | [5,6] | [7,8] |
| 1 | [1,3] | [2,4] | [5,7] | [6,8] |
| 2 | [1,4] | [2,3] | [5,8] | [6,7] |
| 3 | [1,5] | [2,6] | [3,7] | [4,8] |
| 4 | [1,6] | [2,5] | [3,8] | [4,7] |
| 5 | [1,7] | [2,8] | [3,5] | [4,6] |
| 6 | [1,8] | [2,7] | [3,6] | [4,5] |
作り方は簡単です。番号から1を引いて 0〜7 にし、2人の番号の排他的論理和(XOR)を計算します。その値が c になる組を、c-1 列目に集めます。たとえば [3,5] は、2 XOR 4 = 6 なので 5 列目です。
この表には大事な性質が2つあります。
- 同じ列の4組は、互いに重なりません。どの列も、8人をちょうど4組に分けています。
- どの2人組も、表全体でちょうど1回だけ現れます。
3手の手順
例として、あなた(P)の支持候補が [4,7]、A の支持候補が [1,4] の場合を追ってみます。後継者は 4 です。
1手目:A の組がある列を聞く
表全体を table として、A に質問します。
ask(table) → A の候補の組は 2番目 にあります
A の組は 2 列目 [[1,4],[2,3],[5,8],[6,7]] のどれかです。
あなたの組は、この列にはありません。同じ列の組は互いに重ならないので、1人だけ重なる2つの組が同じ列に入ることはないからです。そのため、あなたの2人は、この列の別々の2組に1人ずつ入っています。例では 4 が [1,4] に、7 が [6,7] に入っています。A の組は、この2組のどちらかです。
2手目:その2組のどちらかを聞く
あなたの2人が入っている2組をグループ0、残りの2組をグループ1とします。2つのグループから1組ずつ取って並べた配列を作り、A に質問します。
select = [[[1,4],[2,3]], [[6,7],[5,8]]] ask(select) → A の候補の組は 0番目 にあります
あなたは、どちらがグループ0か知っているので、A の組が [1,4] だと分かります。後継者は、自分の組と重なる 4 です。
B には、どちらがグループ0なのかが分かりません。B から見ると、A の組は [1,4] か [2,3] のどちらかです。
3手目:後継者が A の組のどちら側かを伝える
A の組の小さいほうと大きいほうを、対になるグループ1の組と並べて、カミングアウトします。
reveal([[1,2], [4,3]]) → わたしの候補の1人は 1番目にいます。もう1人は どこにもいません
A は自分の組が [1,4] だと知っています。あなたの候補の1人が [4,3] の中にいるので、それは 4 です。これで A も後継者が 4 だと分かります。
B に分かるのは、後継者が「大きいほう」の側、つまり 4 か 3 のどちらかだということだけです。あとは 4 を指名すればクリアです。
なぜ B にばれないのか
2手目と3手目は、どちらも2つのグループについて同じ形をしています。B には、二人がどちらのグループの話をしているのかが分かりません。もし A の組が [2,3] で、あなたの組が [3,5] や [3,6] だったとしても、会議の記録は配列の並び順を除いてまったく同じになり、そのときの後継者は 3 です。
配列の形から意図を読もうとしても、手がかりになりません。表はどの組も同じ立場に置いていて、2手目と3手目の配列も、2つのグループを入れ替えても同じ形です。あなたの組だけが特別な場所にあることは、どこにもありません。
本の手順との違い
本の解答では、二人の保安官が交互に4回話します。1人目が列を言い、2人目がその列の4組を2つのグループに分けて伝え、1人目がグループ内の1つ目か2つ目かを言い、最後に2人目が犯人は小さいほうか大きいほうかを言います。
このゲームでは A は質問に答えるだけなので、グループの分け方を、2手目の配列の作り方の中に埋め込んでいます。グループ分けと「何番目か」の質問を1手にまとめることで、3手で済みます。
自分で試すには
答えのページにある「ソルバー付きゲーム」を開くと、会議が始まるたびに、この手順が自動で実行されるのが見られます。