手品師の二人組X,Yが次のようなカードマジックを考案した。 まず観客はジョーカーを除く\(52\)枚のトランプのカードから\(5\)枚を自由に選ぶ。 Xはそれを受け取り、そのうち\(4\)枚を選んで、\(1\)枚ずつ順にYに渡す。 Yは渡された\(4\)枚のカードだけを見て、残りの\(1\)枚のカードを当てるのである。 どうすればこのようなことが可能なのだろうか？
このパズルはWallace Leeの本「Math Miracles」で取り上げられており、そこではWilliam Fitch Cheneyという人が考案したとされている（詳しくはMichael Kleberの記事を参照）。 残り\(1\)枚のカードの可能性は\(52-4=48\)通りあり、Xはその中のどれが正解であるかをYに伝えなければいけない。 あらかじめ\(52\)枚のカードに順序をつけておけば、Yに渡す\(4\)枚のカードの順序によって\(4!=24\)通りの情報を伝えることができるが、これでは不十分である。 重要なのは、Xがどの\(4\)枚をYに渡すかを選べるということである。 以下の解答を見る前に、ぜひ自分で考えてみてほしい。
解答を見るさて、上の解答ではXとYの間の取り決めを具体的に構成したが、実は「何らかの方法が存在すること」を証明するだけであれば、グラフ理論の知識を使うだけでできてしまう。 ここで使うのは「Hallの結婚定理」と呼ばれる次の定理である。
この定理から直ちに導かれる次の命題を用いる。
証明 Hallの結婚定理より、\(V_1\)の部分集合\(W\)に対して\(|W|\leq |N_G(W)|\)が成り立つことを示せばよい。 \(W\)の頂点と\(N_G(W)\)の頂点を結ぶ辺全体を\(E'\)とし、二部グラフ\(H=(W,N_G(W),E')\)を考える。 \(H\)において\(W\)の頂点の次数は\(n\)以上なので、\(|E'|\geq n|W|\)である。 一方で\(H\)において\(N_G(W)\)の頂点の次数は\(n\)以下なので、\(|E'|\leq n|N_G(W)|\)である。 これらを合わせると\(|W|\leq |N_G(W)|\)が得られる。
カードマジックの話に戻ろう。 \(52\)枚のカードから\(5\)枚を選ぶ方法全体のなす集合を\(V_1\)とする。 そして、\(52\)枚のカードから\(4\)枚を選んで一列に並べる方法全体のなす集合を\(V_2\)とする。 \(V_1\)の要素\(v\)に対し、その中から\(4\)枚を選んで一列に並べることで\(V_2\)の要素\(w\)が得られるとき、\(v\)と\(w\)を辺で結ぶことにしよう。 これにより一つの巨大な二部グラフ\(G\)が得られる。 \(V_1\)の頂点の次数はすべて \[ \binom{5}{4}\cdot 4! = 120 \] であり、\(V_2\)の頂点の次数はすべて\(52-4=48\)である。 よって上の命題より、\(G\)は\(V_1\)-完全マッチングを持つ。 XとYはあらかじめこのようなマッチングを一つ選んで共有しておき、それに従ってカードを渡せばよいのである。
上の議論からわかるように、このマジックはカードの枚数が\(124\)枚以下であれば成立する。また、カードが\(125\)枚以上のときは\(|V_1|\gt|V_2|\)であるため、このようなトリックは不可能であることもわかる。
このようにHallの結婚定理を用いる考え方は、他の類似のパズルにも適用できる。 例として、2025年の「第4回高校生数学コンテスト in Hamamatsu」で出題された次の問題を考えよう。
この問題の場合には次のような二部グラフを考えればよい。 マス目に\(k\)以下の正整数を書き込む方法全体の集合を\(V_1\)とする。 そして、「\(2\times 2\)に並んだ\(4\)マス以外」に\(k\)以下の正整数を書き込む方法全体の集合を\(V_2\)とする。 \(V_1\)の要素\(v\)に対し、その中から\(4\)マスを消すことで\(V_2\)の要素\(w\)が得られるとき、\(v\)と\(w\)を辺で結ぶことにしよう。 これにより一つの巨大な二部グラフ\(G\)が得られる。 \(V_1\)の頂点の次数はすべて\((n-1)^2\)であり、\(V_2\)の頂点の次数はすべて\(k^4\)である。 \(n\gt k^2\)より\(n-1\geq k^2\)なので、上の命題より\(G\)は\(V_1\)-完全マッチングを持つ。 XとYはあらかじめこのようなマッチングを一つ選んで共有しておき、それに従って消すマスを選べばよいのである。
なお、Hallの結婚定理を用いず具体的な方法を構築するには、例えば次のようにする。 マス目を\(4\)色で塗り分け、どの\(2\times 2\)の\(4\)マスも全ての色を含むようにしておく。 各色のマスに書かれた数の総和を\(k\)で割った余りがわかれば、そこから消えている数を復元できる。 これらの余りのパターンは\(k^4\)通りであり、\((n-1)^2\geq k^4\)なので、消す位置の選び方\((n-1)^2\)通りにその情報を含めることができる。