15.8 鳩の巣原理

よく知られたパズルがある:

電気の付いていない部屋に置かれた引き出しの中に、赤い靴下、緑色の靴下、青い靴下が大量に入っている (左右の区別は無いとする)。同じ色の靴下の組を確実に手にするには、引き出しの中からいくつの靴下を取り出す必要があるか？

例えば、$3$ 個では十分でない: 赤い靴下、緑色の靴下、青い靴下を一個ずつ取り出す可能性がある。この問題の解答は次の事実を使うと得られる:

鳩の巣原理

鳩より巣穴の方が多いなら、全ての鳩を巣穴に入れると二羽以上の鳩が入る巣穴が少なくとも一つ生まれる。

この事実を数学的に厳密に言い換えたものを次に示す:

規則 15.8.1[鳩の巣原理 (pigeonhole principle)]

$|A| > |B|$ なら、任意の全域関数 $f \colon A \to B$ に対して、$f$ の下で $B$ の同じ要素に移される $A$ の異なる二要素が存在する。

鳩の巣原理をこのように表現すると直感的に分かりにくくなるものの、この主張には見覚えがあるはずである: これは単射に関する写像則 (定理 4.5.4) が示す関係 $\text{(4.6)}$ の対偶である。$A$ は鳩全体の集合に、$B$ は鳩の巣穴全体の集合に対応し、$f$ はそれぞれの鳩がどの巣穴に入るかを定める。

数学者は鳩の巣原理の巧妙な応用を数多く発見してきた。そういった議論を生み出すためのレシピがあればここに示すのだが、残念ながらそんなものは存在しない。ただ、役立つはずのヒントが一つある: 鳩の巣原理を使って問題を解くときは、次の三つの事項が何かを考えるとよい:

集合 $A$ (鳩)
集合 $B$ (巣穴)
関数 $f$ (鳩を巣穴に割り当てる規則)

教皇の鳩の巣

イタリアの Umbriaウンブリアにある Orvietoオルヴィエートという街は、中世にローマから追い出された教皇を何人も迎え入れたとされる。この街は高原の頂上にあり、急な斜面が外敵からの防御を提供した。街の住民は何世紀もの時間をかけて約 $1200$ もの住居を含む地下洞窟を掘り、そこで腐ることのない食料として大量の鳩を飼育することで長期の攻撃に備えた。「Orvieto pigeonhole」で画像検索すると教皇を助けた「鳩の巣」を確認できる。

15.8.1 髪の毛の本数

鳩の巣原理には様々な一般化が知られている。例えば:

規則 15.8.2[一般化された鳩の巣原理 (generalized pigeonhole principle)]

$A$, $B$ を集合とする。もし $|A| > k\cdot |B|$ が成り立つなら、任意の全域関数 $f \colon A \to B$ に対して、ある $b \in B$ が存在して、$k + 1$ 個以上の異なる $A$ の要素が $f$ の下で $b$ に移される。

例えば、ランダムに選んだ二人が全く同じ本数の髪の毛を持つ可能性は非常に低い。しかし、マサチューセッツ州ボストンという素晴らしい街には、全く同じ本数の髪の毛を持つ三人組が間違いなく存在する！ もちろん、ボストンには髪の毛を一本も持たない人が多くいるだろう。そういった人々は $0$ 本という同じ本数の髪の毛を持つものの、ここでは考えないものとする: $1$ 万本以上の髪の毛を持つハゲでない人だけを考えたとしても、先ほどの主張は成り立つ。

ボストンにはハゲでない住民が少なくとも $500{,}000$ 人いる。そして人間の髪の毛はどんなに多くても $200{,}000$ 本を超えることはない。ハゲでないボストン住民全体の集合を $A$ として、$B = \left\{ 10{,}000, 10{,}001, \ldots, 200{,}000 \right\}$ とする。さらに $f$ を $A$ の要素からその人の髪の毛の本数への写像とする。すると $|A| > 2 \cdot |B|$ が成り立つので、一般化された鳩の巣原理から、全く同じ本数の髪の毛を持つハゲでないボストン住民が少なくとも $3$ 人いることが分かる。誰かは分からないものの、その存在だけは確実に言える！

15.8.2 和が等しい部分集合

読者の目の保養として、図 $\text{15.4}$ に $90$ 個の $25$ 桁の数字を示す。これら $25$ 個の数字の異なる部分集合であって和が等しいものは存在するだろうか？例えば、左側の列の末尾 $10$ 個の数字の和が右側の列の先頭 $11$ 個の数字の和と等しいかもしれない。

90 個の 25 桁の数字: 和が等しい異なる部分集合は存在するか？ — 図 15.4$90$ 個の $25$ 桁の数字: 和が等しい異なる部分集合は存在するか？

和が等しい部分集合を見つけるなど意味のない馬鹿げたパズルだと思うかもしれない。しかし、こういった問題の解法はコンテナに入れる荷物の選択や機密メッセージの解読で有用となる。

実は、和が等しい二つの部分集合を見つける問題は理論的に難しいことが分かっている。これは暗号理論で同様の問題がよく利用される理由でもある。ただ、和が等しい部分集合の存在は鳩の巣原理を使って簡単に証明できる。

図 $\text{15.4}$ に含まれる $90$ 個の数字の集合を $A$ とする。$25$ 桁の任意の数字は $10^{25}$ 未満なので、$A$ の任意の部分数字の和は $90 \cdot 10^{25}$ 未満だと分かる。そこで区間 $[0..90\cdot 10^{25}]$ に属する整数全体の集合を $B$ として、$A$ の部分集合をその和 ($B$ の要素) に対応付ける写像を $f$ とする。

第 15.2.2 項で示したように、$n$ 要素集合の部分集合は $2^{n}$ 個ある。よって次の関係が分かる:

\[ |A| = 2^{90} \geq 1.237 \times 10^{27} \]

一方で、次の関係も成り立つ:

\[ |B| = 90 \cdot 10^{25} + 1 \leq 0.901 \times 10^{27} \]

いずれの集合も巨大であるものの、$|A|$ の方が $|B|$ より少しだけ大きい。これは $f$ によって同じ $B$ の要素に移される $A$ の異なる二要素が存在することを意味する。言い換えれば、鳩の巣原理より和が等しい異なる部分集合は存在する！

この証明はどの二つの部分集合が等しい和を持つかを示さない点に注目してほしい。この腹立たしい特徴を持つ証明は非構成的証明 (nonconstructive proof) と呼ばれる。

本当に見つかるのか？

図 $\text{15.4}$ に示した $90$ 個の $25$ 桁の数字の中から和が等しい異なる二つの部分集合を実際に見つけることが人間に可能かどうかを確かめるために、学生たちに「最初に見つけた人に $\$100$ を渡す」と伝えたことがある。著者らは $\$100$ を渡すことはないだろうと思っていたのだが、学生の賢さと貪欲さを過小評価していた。ある情報科学専攻の学生は「実現可能性のある」ごく一部の部分集合だけを調べる賢いプログラムを書き、和が等しい部分集合の組を実際に発見した。彼は $\$100$ を受け取った。さらに数日後には、数学専攻の学生が問題を格子基底簡約 (lattice basis reduction) と呼ばれる問題に変換し、この問題を高速に解くソフトウェアパッケージを利用して和が等しい部分集合の組をいくつも見つけたと報告した。彼は賞金を受け取れなかったものの、講義室にいた学生とスタッフからのスタンディングオベーションを受けた。

部分集合の和が全て異なる集合

$n$ 個の正整数からなる集合であって、全ての異なる部分集合が異なる和を持つものはどうしたら構築できるだろうか？ $2$ の冪を使う方法が考えられる:

\[ \left\{ 1, 2, 4, 8, 16 \right\} \]

このアプローチは非常に自然なので、この条件を満たす集合には必ず大きな整数が含まれると思いたくなる。例えば、上記の例で $16$ は $17$ に置き換えられるのに対して、$15$ に置き換えることはできない。しかし意外なことに、少しだけ小さい整数からなる集合が条件を満たすことがある:

\[ \left\{ 6, 9, 11, 12, 13 \right\} \]

二十世紀で最も偉大な数学者の一人である Paulポール Erdősエルデシュは 1931 年に、非常に小さな整数しか含まない集合が上記の条件を満たすことはないだろうと予想した。正確には、条件を満たす任意の集合の最大要素が $c2^{n}$ より大きくなるような定数 $c > 0$ が存在すると予想した。Erdős は彼の予想を証明または反証した人物に $\$500$ の賞金を授与すると宣言したものの、この問題は現在でも未解決である。

15.8.3 トランプを使った手品

手品師が助手に $52$ 枚のトランプ一式を持たせて後ろを向いた。助手は聴衆の元に向かい、$5$ 人の聴衆に $1$ 枚ずつカードを抜き取るように頼んだ。助手は抜き取られた $5$ 枚のカードを集め、その中から $4$ 枚を手品師に見せた。手品師は見せられた $4$ 枚のカードを見て少しの間ウムムと考え、見せていない $5$ 枚目のカードを正しく言い当てた！

手品師が人の心を読めるとは思えないので、助手が何らかの方法で手品師に $5$ 枚目のカードを伝えたに違いない。現実の手品師と助手は裏で通じているので、秘密の言葉や身振りで情報を伝えることができる。しかし、このマジックではそういったインチキをする必要がない。実は、手品師と助手がお互いを一切認識できないとしても手品は成立する。助手が手品師に見せる $4$ 枚のカードを選び、助手から受け取った $4$ 枚のカードを聴衆が手品師に見せるとしても、手品師は $5$ 枚目のカードを正しく言い当てられる。

インチキをしないとしても、助手が手品師に情報を伝える明らかな方法が一つある: 手品師に見せる $4$ 枚のカードの並べ方である。しかし、これだけでは情報として十分でない: $4$ 枚のカードを並べる方法は $4! = 24$ 通りあり、残りのカードは $52-4=48$ 枚ある。そのため、助手は $5$ 枚目のカードを伝えるのに十分な選択肢の自由度を持たない (二択にすることはできる)。

15.8.4 手品の種

助手が $5$ 枚目のカードを伝えるのに利用できる手法は、本書で学んできた数え上げとマッチングに関する理論の素晴らしい応用である。

実は、助手が手品師に情報を伝える手段はもう一つある: 手品師に見せない $5$ 枚目のカードの選択である。もちろん、手品師は助手が見せなかったカードを $4$ 枚のカードから直接知ることはできない。しかしこれから説明するように、十分な情報を受け取ることはできる。

手品師と助手が直面する問題は本質的に二部グラフのマッチング問題である。考える二部グラフの左頂点は助手に明かされる情報 ($5$ 枚のカードの集合) に対応する。よって左頂点全体の集合を $X$ とすれば、$X$ は $\binom{52}{5}$ 個の要素を持つ。そして右頂点は手品師に明かされる情報 ($4$ 枚のカードの列) に対応する。よって右頂点全体の集合を $Y$ とすれば、$Y$ は $52 \cdot 51 \cdot 50 \cdot 49$ 個の要素を持つ。

聴衆が $5$ 枚のカードの集合を選ぶと、助手はその中から選んだ $4$ 枚のカードの列を手品師に見せる。この関係は左頂点と対応する右頂点を辺で結ぶことで表現できる。つまり、任意の左頂点は、その要素だけが並んだ右頂点と辺で結ばれる。これらの頂点と辺から構築される二部グラフの一部を図 $\text{15.5}$ に示す。

手品師と助手の問題を表す二部グラフ: 左頂点は 5 枚のカードのstrong集合/strongに対応し、右頂点は 4 枚のカードのstrong列/strongに対応する。集合と列が辺で結ばれるのは、列が集合の要素だけからなるときである。マッチングに含まれる辺を強調している。 — 図 15.5手品師と助手の問題を表す二部グラフ: 左頂点は $5$ 枚のカードの集合に対応し、右頂点は $4$ 枚のカードの列に対応する。集合と列が辺で結ばれるのは、列が集合の要素だけからなるときである。マッチングに含まれる辺を強調している。

例えば、$5$ 要素集合

\[ \{8\heartsuit,\, K\text{$\spadesuit$},\, Q\text{$\spadesuit$},\, 2\text{$\diamondsuit$},\, 6\text{$\diamondsuit$}\} \tag{15.2}\]

は左頂点の集合 $X$ に属する。聴衆がこの $5$ 枚を選択したとき、助手が選択できる $4$ 枚のカードの列には $(8\text{$\heartsuit$},\, K\text{$\spadesuit$},\, Q\text{$\spadesuit$},\, 2\text{$\diamondsuit$})$ や $(K\text{$\spadesuit$},\, 8\text{$\heartsuit$},\, Q\text{$\spadesuit$},\, 2\text{$\diamondsuit$})$ など様々な選択肢があり、これらはどれも右頂点の集合 $Y$ に属する。

手品を成功させるには、手品師と助手が $X$ 全体を被覆するマッチングに前もって合意しておく必要がある。マッチングが決まっていれば $4$ 枚のカードの列から $5$ 枚のカードの集合が一意に定まるので、列に含まれず集合に含まれるカードが $5$ 枚目のカードだと分かる。

例えば、二人が合意するマッチングが図 $\text{15.5}$ の二本の太線が表す辺を含むとしよう。その上で、聴衆が次の $5$ 枚のカードを選んだとする:

\[ \{8\text{$\heartsuit$},\, K\text{$\spadesuit$},\, Q\text{$\spadesuit$},\, 9\text{$\clubsuit$},\, 6\text{$\diamondsuit$}\} \tag{15.3}\]

このとき、助手はマッチングでこの集合に対応する次の列を手品師に見せる:

\[ (K\text{$\spadesuit$},\, 8\text{$\heartsuit$},\, 6\text{$\diamondsuit$},\, Q\text{$\spadesuit$}) \tag{15.4}\]

この列を目にした手品師は、マッチングにおいて列 $\text{(15.4)}$ が集合 $\text{(15.3)}$ に対応することを確認する。そして列に含まれず集合に含まれる $9 \clubsuit$ が $5$ 枚目のカードだと判断する。集合と列の対応関係がマッチングであること、つまり異なる集合が異なる列に対応する事実が重要なことに注目してほしい。例えば、集合 $\text{(15.2)}$ が聴衆によって選ばれたときにも、助手は列 $\text{(15.4)}$ を手品師に見せることができる。しかし、そうしてはいけない: もしそうすると、手品師は最後の $1$ 枚が $9 \spadesuit$ と $2 \diamondsuit$ のどちらなのか判別できなくなる。

では、この手品を成立させるマッチングが必ず存在すると言えるのはどうしてだろうか？鍵となるのは、任意の左頂点が $5 \cdot 4! = 120$ の次数を持つ事実である: 手品師に見せないカードの選択肢が $5$ 個、見せる $4$ 枚のカードの並べ方が $4!$ 通り存在する。そして、任意の右頂点は $48$ の次数を持つ: $5$ 枚目のカードの選択肢が $52 - 4 = 48$ 個ある。つまり、考えている二部グラフは定義 12.5.5 の意味で次数制約を満たす。よって定理 12.5.6 よりマッチングは存在する。

この議論からは、右頂点の次数が $120$ まで増えたとしてもマッチングは存在すると分かる。つまり、手品師は $52$ 枚ではなく $120 + 4 = 124$ 枚の異なるカードを使う場合でも正しいカードを言い当てられる ── 魔法もインチキも必要ない！

15.8.5 手品の本当の種

ちょっと待った！「手品師と助手は前もってマッチングに合意しておく」と軽々しく言ったものの、$\binom{52}{5} = 2{,}598{,}960$ 本の辺からなるマッチングを記憶するのは全く現実的でない。この手品を実際に披露するには、助手が示したカードの列を見て対応する集合を頭の中で素早く求められる必要がある。

この問題を解決するアプローチの一つをこれから具体例を通して示す。次の $5$ 枚のカードを聴衆が選んだとする:

\[ 10 \heartsuit \quad 9 \diamondsuit \quad 3 \heartsuit \quad Q \spadesuit \quad J \diamondsuit \]

助手は同じ絵柄を持つ $2$ 枚のカードを選ぶ。この例では $3 \heartsuit$ と $10 \heartsuit$ を選ぶとする。絵柄が同じ $2$ 枚のカードは鳩の巣原理より常に存在する ── 絵柄が $4$ 種類でカードが $5$ 枚なので、いずれかの絵柄は $2$ 枚以上ある。

続いて、助手は選んだ $2$ 枚のカードが図 $\text{15.6}$ に示す円のどこに位置するかを確認する。この円上の任意の異なる $2$ 個の数字に対して、いずれか一方から時計回りに移動してもう一方に到達するために必要なホップ数は $1$ 以上 $6$ 以下である。考えている例では、$10$ から $3$ には $6$ ホップで到達できる。
助手は円上の位置関係に関して時計回りで「後にある」方のカードを手品師に見せない秘密のカードとして、「前にある」方のカードを手品師に見せる $1$ 枚目のカードとする。考えている例では $3 \heartsuit$ が秘密のカードとなり、$10 \heartsuit$ は手品師に開示される $1$ 枚目のカードとなる。このとき、次の関係が成り立つ:
- 秘密のカードの絵柄は、開示されるカード列の $1$ 枚目の絵柄と等しい。
- 秘密のカードの数字は、開示されるカード列の $1$ 枚目の数字から「環状に」進むことで $1$ ホップ以上 $6$ ホップ以下で到達できる。
よって、後は $1$ 以上 $6$ 以下の数字を一つ伝えればよい。手品師と助手は前もって全てのトランプカードの順序に関して合意しておくとする。例えば:

\[ A \clubsuit\ A \diamondsuit\ A \heartsuit\ A \spadesuit \ 2 \clubsuit\ 2 \diamondsuit\ 2 \heartsuit\ 2 \spadesuit \ldots \ K \clubsuit\ K \diamondsuit\ K \heartsuit\ K \spadesuit \]

その上で、残りの $3$ 枚のカードに数字の大小関係に応じて「大」「中」「小」と名前を付け、それらを並べる順番で次のように $1$ 以上 $6$ 以下の数字を伝える:

\[ \begin{aligned} (\text{小},\ \text{中},\ \text{大}) \longrightarrow 1 \\ (\text{小},\ \text{大},\ \text{中}) \longrightarrow 2 \\ (\text{中},\ \text{小},\ \text{大}) \longrightarrow 3 \\ (\text{中},\ \text{大},\ \text{小}) \longrightarrow 4 \\ (\text{大},\ \text{小},\ \text{中}) \longrightarrow 5 \\ (\text{大},\ \text{中},\ \text{小}) \longrightarrow 6 \\ \end{aligned} \]

先ほどの例では $6$ を伝える必要があるので、助手は残りのカードを「大」「中」「小」の順番で並べる。つまり、手品師は次の列を目にする:

\[ (10 \heartsuit,\ Q \spadesuit,\ J \diamondsuit,\ 9 \diamondsuit) \]
手品師は $10 \heartsuit$ から $6$ ホップ進んで $3 \heartsuit$ を得る。これが秘密のカードである！

以上で通常の $52$ 枚のトランプ一式を使うときのアプローチが説明できた。ただ、先ほど見たように、Hall の定理からは最大で $124$ 枚のカードを使う同様の手品が理論上は可能だと分かる。実は、カードが $124$ 枚ある場合でも十分練習した人間であれば実行可能なアプローチが存在する。ここでは説明しないので、詳しくは Michael Kleber による The Best Card Trick を見てほしい。

15.8.6 $4$ 枚のカードで同じことができるか？

聴衆が選ぶカードが $4$ 枚で、助手が手品師に見せるカードは $3$ 枚だとしよう。このときも手品師は $4$ 枚目のカードを言い当てられるだろうか？

$X$ を聴衆が選ぶ $4$ 枚のカードの集合全体の集合、$Y$ を助手が手品師に見せる $3$ 枚のカードの列全体の集合とする。このとき、部分集合則から次の等式が分かる:

\[ |X| = \binom{52}{4} = 270{,}725 \]

一方で、一般化された乗算則からは次の等式が分かる:

\[ |Y| = 52 \cdot 51 \cdot 50 = 132{,}600 \]

ここから次を得る:

\[ \left\lceil \frac{|X|}{|Y|} \right\rceil = \left\lceil \frac{ 270{,}725}{132{,}600} \right\rceil = 3 \]

よって一般化された鳩の巣原理より、助手は少なくとも一度 $3$ 個の異なる集合に対して同じ列を選択しなければならない。これは手品師にとって悪いニュースである: $4$ 枚目のカードの選択肢が $3$ 個以上あり、それらは区別できない。つまり、インチキに頼らずに助手が $4$ 枚目のカードを手品師に伝える手段は存在しない！