鳩の巣原理

カテゴリー：数学A

鳩の巣原理とは、n個の箱にm個の物を入れる時、nがmより小さければ必ずどこかの箱には2以上の物が入ると言う原理である。

文字にするとわかりにくいので、実際に図を使って説明する。

鳩の巣原理は直感的で簡単なので、ぜひ覚えて欲しい。

図1.

図1のように鳩4匹に対して、巣箱が3つある場合を考える。

すべての鳩が巣箱に帰ろうとすると、必ずどこかの巣箱に２羽入ることになる。

巣箱の個数に対して、鳩の数が多いので当たり前であるがこれが鳩の巣原理である。

図2.

鳩の巣原理を使った問題

自然数を適当に4つ選び、それぞれの差が3の倍数になる組み合わせが必ず一つ以上できることを証明せよ。 この時、差は必ず正になる方を選ぶことにする。

と言う問題を鳩の巣原理を使って証明したいと思う。

自然数は必ず以下の3つの\( A,\ B,\ C \)の集合の内、1つに属する。

\(A = \{n|n\)は3の倍数}

\(B = \{n|n\)を3で割ると1余る}

\(C = \{n|n\)を3で割ると2余る}

この3つの集合の中で同じ集合に属する自然数同士の引き算は必ず3の倍数になる。

この証明は簡単で、例えば集合\( B \)に属する2つの自然数は

と表される。この2つの自然数の差は\( 3(m-n) \)となり、3の倍数となることがわかる。

集合\( A \)、\( C \)に関しても同様である。

さて、問題に戻る。

自然数を4つ選ぶということは、集合\( A,\ B,\ C \)の中から4つ選ぶと言うことに等しい。

この時、鳩の巣原理より、4つのうち2つは必ず同じ集合に属することになるのである。

これにより、自然数を適当に4つ選び、それぞれの差が3の倍数になる組み合わせが必ず一つ以上できることを証明できた。

この類題は神戸大学の入試問題で出題されている。このように直感的で簡単に見える原理で大学入試問題も解けるのである。