https://smooth-pudding.hatenablog.com/entry/2024/05/18/215944

こんにちは。今回はとある論理パズルを紹介します。

アコナール入りボトルを特定せよ

問題. とある星には「アコナール」と呼ばれる物質がある。アコナールをその星の住人が摂取すると、摂取から1時間後に、普段は白い体が赤くなることが知られている。特にそれ以外に健康に影響はなく、赤くなった体も数時間後には元に戻る。

アコナールのイメージ
この星で水の入ったボトル1000本が倉庫から見つかった。このうち1本にのみアコナールが含まれることが分かっている。このアコナール入りのボトルをうまく特定したい。
そこで特定のための試飲会を開き、試飲係を何人か雇うことにした。試飲は以下の手順で行う。

すべての試飲係に一つずつコップを配り、それぞれに1000本のボトルのいずれかから水を注ぐ。このとき一つのコップに複数のボトルの水を注いで混ぜてもよいし、同じボトルの水を複数のコップに注いでもよい。

すべてのコップに注ぎ終わったら、試飲係全員に合図を送る。各試飲係は合図と同時に持っているコップの水をすべて飲む。

合図から1時間後の各試飲係の色(赤か白か)を確認したら、給料を渡して解散。

この試飲会でアコナール入りボトルを確実に特定するには、最低何人の試飲係を雇う必要があるだろうか？

この問題自体はとても有名なもので、ググると割とすぐに解法を見つけることができると思います*1。

以下に解答を書きます。自分で考えたい人は一度読むのをストップしてください。

↓

【答え】10人
【解説】
試飲係の人数を $N$ とおきます。試飲会の最終盤、各試飲係の色はそれぞれ赤または白なので、結果のパターンは $2^{N}$ 通りあります。一方で、1000本のボトルのうちどれがアコナール入りかについては、当然 $1000$ 通りあります。したがって、試飲の結果からアコナール入りのボトルを確実に特定するには、少なくとも $2^{N} \geqq 1000$ を満たす必要があります。 $2^{9}=512 < 1000 < 1024 = 2^{10}$ なので、最低でも $N \geqq 10$ を満たす必要があります。

逆に試飲係 10 人で実際に特定する方法を与えます。試飲係を仮に A, B, C, D, E, F, G, H, I, J としましょう。さらに各ボトルにも 1 ~ 1000 の番号を振っておきます。1 ~ 1000 の数を二進法で表示すると、以下の通り10桁以下の数で表示できます。

$\begin{aligned} 1 &= 00000 00001_{(2)} \\ 2 &= 00000 00010_{(2)} \\ 3 &= 00000 00011_{(2)} \\ &\vdots \\ 999 &= 11111 00111_{(2)} \\ 1000 &= 11111 01000_{(2)} \end{aligned}$
これをもとにして、以下の手順でコップに注ぐようにします。

$k$ 番目のボトルを手に取る。
$k$ を10桁の二進法で表示し、各桁を左から A, B, ..., J に対応させ、1となった試飲係のコップにこのボトルの水を注ぐ。
以上を $k = 1, 2, 3, \dots, 1000$ のすべてで順に行う。

さて、この注ぎ方をしたあと、試飲係に飲んでもらいます。1時間後、例えば A, B, ..., J の色が以下のパターンになったとしましょう。

白白赤白赤赤赤赤白赤これに対して、白は 0, 赤は 1 に対応させた二進法の数を作ります。 $0010111101_{(2)}$ これに対応する番号、つまり189番が振られたボトルがアコナール入りであることが分かります。同様に、試飲係の色のパターンに二進法を対応させることで、必ずアコナール入りのボトルを特定することができます。

アコナール入りボトルを特定せよ（強化版）

ではこの問題をさらに難しくしてみましょう。

問題. アコナール入りのボトルが1000本中2本の場合、アコナール入りボトルをすべて確実に特定するには、最低何人の試飲係を雇う必要があるか？

実は本数を2本にするだけで途端に難しい問題となり、実は私もまだ解けていません。ですが、問題を言い換えているうちに面白い数学っぽい問題が生えたので、それを紹介したいと思います。

1000であることに深い意味はないので、一般化しておきます。

問題. アコナール入りのボトルが $K \text{ } (\geqq 2)$ 本中2本のとき、 $N$ 人の試飲係でアコナール入りボトルをすべて確実に特定することは可能か？

通常版の問題でやったように、各ボトル $k \text{ }(= 1, 2, \dots, K)$ に対して、各試飲係 $n \text{ }(=1, 2, \dots, N)$ に飲ませるかどうかを 0 or 1 で表すことにします。これを $a_{n, k}$ とでも置いてみましょう。添え字が2つあるので、行列にしてみます。

$A = \begin{pmatrix} a_{1, 1} & a_{1, 2} & \dots & a_{1, K} \\ a_{2, 1} & a_{2, 2} & \dots & a_{2, K} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N, 1} & a_{N, 2} & \dots & a_{N, K} \end{pmatrix} \in \mathrm{Mat}_{N \times K}(\{0, 1\})$

さて、もしボトル $k_{1}$ とボトル $k_{2}$ がアコナール入りだったらどうなるか考えてみます。試飲会の最後に赤くなるのは、 $a_{n,k_{1}}$ が 1 または $a_{n,k_{2}}$ が 1 となる $n$ さんです。ここで

$0 \lor 0 = 0, \quad 0 \lor 1 = 1 \lor 0 = 1 \lor 1 = 1$ という演算子 $\lor$ を導入すると、 $N$ 次元のベクトル $\begin{pmatrix} a_{1, k_{1}} \lor a_{1, k_{2}} \\ a_{2, k_{1}} \lor a_{2, k_{2}} \\ \vdots \\ a_{N, k_{1}} \lor a_{N, k_{2}} \end{pmatrix}$ の第 $n$ 要素が 1 なら赤、0 なら白です。このベクトルは形式的に以下のように書くことができます。 $A \begin{pmatrix} 0 \\ \vdots \\ 1 (\leftarrow k_{1} \text{ 成分}) \text{ } \\ \vdots \\ 1 (\leftarrow k_{2} \text{ 成分}) \text{ } \\ \vdots \\ 0 \end{pmatrix}$ これは、行列の積の成分計算の際に、和の代わりに先ほどの $\lor$ を用いるようにすればちゃんと意味の通る表現となります。一般化すると、ボトル $k$ にアコナールが入っていれば 1、入っていなければ 0 となる変数 $b_{k}$ を導入すれば $A \mathbf{b} \text{ ただし } \mathbf{b} = \begin{pmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{K} \end{pmatrix}$ の第 $n$ 成分が、ちょうど $n$ さんが赤 (=1) か白 (=0) かを表すことになります。

さて、試飲係たちの色の組み合わせによって、アコナール入りのボトルを確実に特定するためには、どのような条件が必要でしょうか？それは以下のように書くことができます。

$\forall \mathbf{b}, \forall \mathbf{b}' \in B, \quad \mathbf{b} \neq \mathbf{b}' \Rightarrow A \mathbf{b} \neq A \mathbf{b}'$ ただし $B$ はある二つの成分のみが1で、他は0であるようなベクトルの集合です。これが成り立てば、色のパターンに対してアコナール入りボトルの組み合わせがただ一つに定まることになります。またこれは次のように言い換えることもできます。 $\# \left\{ A \mathbf{b} \ \right| \left. \mathbf{b} \in B \right\} = \# B$ これにより、問題は以下のように言い換えることができます。

問題. $N, K$ を自然数とし、 $K \geqq 2$ とする。等式
$\# \left\{ A \mathbf{b} \ \right| \left. \mathbf{b} \in B \right\} = \# B$ が成立するような $A \in \mathrm{Mat}_{N \times K}( \{ 0, 1 \} )$ は存在するか？

以下は、この問題について数値的に探索した結果です。〇は $A$ が存在、×は $A$ が存在しないことを表し、？は不明です。

↓ $N$ → $K$	2	3	4	5	6	7	8	9	10
1	〇	×	×	×	×	×	×	×	×
2	〇	〇	×	×	×	×	×	×	×
3	〇	〇	〇	×	×	×	×	×	×
4	〇	〇	〇	〇	×	×	×	×	×
5	〇	〇	〇	〇	〇	×	×	×	×
6	〇	〇	〇	〇	〇	〇	〇	×	×
7	〇	〇	〇	〇	〇	〇	〇	〇	？

以下は数値計算によらずとも示すことができます。

上の表のあるマスが〇なら、そのすぐ下も〇 (一部の試飲係をサボらせればOK)
上の表のあるマスが×なら、そのすぐ右も× (判定できない状態でボトルを増やすともっと無理)
$K \leqq N + 1$ なら〇 (実際、 $K = N$ なら単位行列、 $K = N + 1$ なら単位行列の右に 0 の列を追加したもの、 $K < N$ なら単位行列の下に 0 の行を追加したものが条件を満たす)
$2^{N} < \dfrac{K(K - 1)}{2}$ なら× ( $\# \{ 0, 1 \}^{N} < \# B$ となるため)

もちろんすべての $N, K$ について数値的に求めることはできないので、具体的に構成できた例を眺めながら、なにかしら一般法則を見いだせないかなぁと考えているのが現在の状況です。

もし「解けたよ」という方や「答えを知っているぞ」という方がいれば、こっそり教えてください。

ではまた。

*1:元ネタは毒入りのワインを特定する問題です。ちょっとだけマイルドな状況にしてみました。

↓ $N$ → $K$	2	3	4	5	6	7	8	9	10
1	〇	×	×	×	×	×	×	×	×
2	〇	〇	×	×	×	×	×	×	×
3	〇	〇	〇	×	×	×	×	×	×
4	〇	〇	〇	〇	×	×	×	×	×
5	〇	〇	〇	〇	〇	×	×	×	×
6	〇	〇	〇	〇	〇	〇	〇	×	×
7	〇	〇	〇	〇	〇	〇	〇	〇	？

↓ $N$ → $K$	2	3	4	5	6	7	8	9	10
1	〇	×	×	×	×	×	×	×	×
2	〇	〇	×	×	×	×	×	×	×
3	〇	〇	〇	×	×	×	×	×	×
4	〇	〇	〇	〇	×	×	×	×	×
5	〇	〇	〇	〇	〇	×	×	×	×
6	〇	〇	〇	〇	〇	〇	〇	×	×
7	〇	〇	〇	〇	〇	〇	〇	〇	？

↓ $N$ → $K$	2	3	4	5	6	7	8	9	10
1	〇	×	×	×	×	×	×	×	×
2	〇	〇	×	×	×	×	×	×	×
3	〇	〇	〇	×	×	×	×	×	×
4	〇	〇	〇	〇	×	×	×	×	×
5	〇	〇	〇	〇	〇	×	×	×	×
6	〇	〇	〇	〇	〇	〇	〇	×	×
7	〇	〇	〇	〇	〇	〇	〇	〇	？