使える電池を選ぶための最小の試行回数を求める

The return of the graphs (and an interesting puzzle) というブログ記事に載っていた問題が面白かったので紹介したい。日本語訳 (by DeepL) をすると

あなたは8個の電池を与えられ、そのうち4個は良品、4個は消耗品であるが、見た目には違いがない。 あなたは懐中電灯を持っており、その懐中電灯を作動させるためには良品の電池2個が必要である。 あなたは懐中電灯を作動させたい。最悪の場合、懐中電灯が確実に作動するために、2本の電池を懐中電灯に入れる回数は何回必要か。

電池は全部で8個あり、そこから2つ選ぶ方法は28通りで、良品の4つから選ぶのは6通りなので、何も考えず懐中電灯に入れていっても23回目には確実に動作させることができる。

が、もちろんもっと少ない試行回数で済ませることが可能で、正解は7だ。

7回で十分なことはすぐにわかる。1から8までの番号を振った電池を、{1, 2, 3}, {4, 5, 6}, {7, 8} の3グループに分けると、どこかのグループには少なくとも二つの良品が入る。なので、各グループ内で全ペアを試していけばよく、その回数は $3+3+1=7$ だ。

6回では不十分なことの証明は少しややこしいので、冒頭のブログを見てほしい。

面白いのはこの問題は、グラフの問題としてもアプローチできることだ。ノード数8のグラフを用意し、ノード $i$ と $j$ の間にエッジがあるとき、対応する電池を懐中電灯に入れると考える。

例えば、7回の比較でうまくいくパターンは以下のようなグラフとして表現できる。

  1      4    7
 / \    / \   |
2---3  5---6  8

そうすると、考えるべき問題は「ノードが8個、エッジが $E$ 本の無向グラフにおいて、ノードの部分集合でその間にエッジがないもの (independent set と呼ぶ) の最大サイズを3以下にすることができるか？」になる。もしサイズ4以上の independent set があれば、良品が全てそこに入った場合、良品ペアを発見できないことになる。逆にどんな independent set もサイズが3以下になるなら条件を満たせる。

例えばエッジ7本でも

  1      4    7
 / \    / \
2---3--5---6  8

のようなグラフを作ってしまうと、{1, 4, 7, 8} がサイズ4の independent set になり、これらが良品の場合に発見できないことになる。

このような問題に帰着できればあとは計算機の力でゴリ押して解くことができる。エッジの本数ごとにありうるグラフをすべて列挙して条件を満たすかを調べれば良い。具体的には、エッジが0本のグラフから初めて以下の手順を繰り返す：

1. エッジ $E$ 本のグラフにあらゆるパターンでエッジを一本加えてエッジ $E+1$ 本のグラフをすべて列挙する。同型なグラフは一つにまとめる
2. 各グラフについてノードの independent set の最大サイズを求める
3. エッジ $E+1$ 本のグラフ全体におけるこの最大サイズの最小値を求める
4. この最小値が3以下になれば終了

ブログに載っていたJuliaコードが自分の環境で動かなかったので、以下にRustに書き直したものを貼っておく

Graphs puzzle

Gist