並んだカードをまだ見ていないのに、「この中には必ず同じものがある」と言える。そんな推理に使えるのが、鳩の巣原理です。
名前は少し変わっていますが、考え方は身近です。入れる物の数と、入れ先の数を比べます。この記事では、色と記号を組み合わせた小問で、その使い方を確かめます。
目次
鳩の巣原理とは？物の数が、箱の数を超えるとき
n個の箱にn＋1個以上の物を入れると、少なくとも一つの箱には2個以上入る。これが鳩の巣原理の基本形です。箱の数nは、1以上の整数とします。
例えば、4個の巣箱へ5羽の鳩が1羽ずつどこかの巣箱に入るなら、少なくとも一つの巣箱には2羽以上います。全ての巣箱が1羽以下だと、合計でも4羽までにしかならないからです。
鳩や箱は、実物である必要はありません。「物」を人や数字に、「箱」を誕生月や数字の性質に置き換えられます。基本形とその証明は、ニューヨーク州立大学バッファロー校の教材でも確認できます。
小問：13枚のカードを全部違うデザインにできる？
イベントで配るカードを13枚作ります。デザインのルールは、次の通りです。
- 背景色は、赤・青・黄の3種類から一つ選ぶ
- 中央の記号は、○・△・□・☆の4種類から一つ選ぶ
- 色と記号以外に、デザインを区別する要素はない
このとき、13枚を全て違うデザインにできますか？「同じデザイン」とは、背景色と記号の両方が一致することです。同じ色でも記号が違えば、別のデザインと数えます。
カードを実際に描く前に、まず「入れ先」に当たるものを探してみましょう。
答え：12種類のデザインを「箱」と考える
答えは、できません。少なくとも2枚は同じデザインになります。
赤い背景には、赤○・赤△・赤□・赤☆の4種類があります。青と黄にも、それぞれ4種類。全部で3×4＝12種類です。
そこで、この12種類のデザインごとに箱を一つ用意すると考えます。作ったカードを、そのデザインの箱へ入れていきます。どのカードにも背景色と記号が一つずつあるので、入れ先は必ず一つに決まります。
12個の箱に13枚を入れるため、少なくとも一つの箱には2枚以上入ります。それが、背景色も記号も同じカードです。全カードの組み合わせを一つずつ比較しなくても、一致するものの存在を示せました。
12枚なら？「必ず」と「できる」を区別する
12枚なら、12種類を1枚ずつ作れば、全て違うデザインにできます。ただし、12枚以下なら必ず重複しない、という意味ではありません。赤○を2枚作れば、その時点で重複します。
鳩の巣原理が教えるのは、箱の数を超えたら、重複を避けきれないことです。箱の数以下の場合は、実際の選び方を確かめる必要があります。
13枚を全て違うデザインにしたければ、例えば記号を5種類に増やすと、3×5＝15種類を用意できます。その15種類から異なる13種類を選べば、目的を達成できます。
25枚なら、少なくとも3枚が同じになる
元の12種類のまま、カードを25枚作る場合も考えてみましょう。各デザインを2枚ずつまでに抑えると、作れるのは12×2＝24枚までです。25枚目を作れば、どこかのデザインは3枚以上になります。
これは鳩の巣原理の一般化です。各箱に入る個数の上限を仮定し、全体で何個まで入れられるかを考えます。イェール大学の数え上げ教材にも、基本形と一般化が載っています。
使うときは「何を同じと数えるか」を決める
コツは、物を数える前に、分類のルールをはっきりさせることです。今回、箱を「色だけ」にすると3個ですが、それで示せるのは同じ色のカードがあることまで。記号まで一致すると言うには、色と記号の組を箱にする必要があります。
また、少なくとも2枚が一致すると分かっても、それが赤○なのか青☆なのかは、枚数だけでは特定できません。鳩の巣原理は、無作為に選ぶという前提なしに「必ずある」と示せる一方、具体的にどれかを探す作業は残るのです。
分類や条件の組み合わせを考えるのが好きな方は、Takeru Itoのアプリ一覧から、論理パズルや謎解きも楽しんでみてください。