読者です 読者をやめる 読者になる 読者になる

猫尾製作所

あまりアテにしないでね

空き巣の原理

数学

2010年12月16日付の私のはてなダイアリーの記事で『鳩の巣原理』というものをご紹介しました。この原理、というか考え方は「巣の個数を超える数の鳩がいる場合、必ずどれかの巣には2匹以上の鳩が入っている」ということでした。

で、昨日私がなんとなく思いついたのが『空き巣の原理』です。これについては次のような具体的な説明より入らせていただきます。

5匹の鳩がいるのですが、巣は6個あるとします。つまり鳩の数より巣の個数の方が多いのです。で、5匹の鳩に巣に入ってもらいましょう。同じ巣に複数の鳩が入ってもいいとしましょう。すると当然のことながら、少なくとも1つの巣は『空き巣』になってしまいます。仮に5匹の鳩が全て別の巣に入っても、5個の巣しか使われていないので、やはり (6 - 5) = 1 個の巣があまるのです。

さらに例を挙げると、プロ野球チップスとかビックリマンチョコのようなものを考えると、(1つの商品に1枚おまけがつくとして)10種類のカードを集めるには必ず商品を10個以上買わなければならないということも示しています。

私が勝手に命名した『空き巣の原理』とは、「鳩の数より多くの巣があれば、どれかの巣は空き巣になってしまう」というところです。ちょっと数学的にいうならば m 個の元をもつ集合  A = \{ a_1, a_2, a_3, \cdots a_m \} の各元がどの2つも共通部分を持たない  n 個の集合  S_1, S_2, S_3, \cdots,S_n のいずれか一つに属しているとき  n > m ならば  S_1, S_2, S_3, \cdots,S_n のうち少なくとも一つ(もっと詳しくいえば  n - m 個以上)の集合が空集合であると。

『鳩の巣原理』についても似たような文面で記述できます。 m 個の元をもつ集合  A = \{ a_1, a_2, a_3, \cdots a_m \} の各元がどの2つも共通部分を持たない  n 個の集合  S_1, S_2, S_3, \cdots,S_n のいずれか一つに属しているとき  n < m ならば  S_1, S_2, S_3, \cdots,S_n のうち少なくとも一つの集合は2つ以上の元をもつ」

当たり前の話なのですが、この事実によって解決できる問題も意外と少なくはないのかもしれません。