鳩の巣原理
𝑛個の物を𝑚個の箱に入れるとき、𝑛> 𝑚であれば、少なくとも1個の箱には1個より多い物が中にある、という原理 / ウィキペディア フリーな encyclopedia
親愛なるWikiwand AI, これらの重要な質問に答えるだけで、簡潔にしましょう:
トップの事実と統計を挙げていただけますか 鳩の巣原理?
この記事を 10 歳向けに要約してください
鳩の巣原理(はとのすげんり、英: Pigeonhole principle)[1]、またはディリクレの箱入れ原理(ディリクレのはこいれげんり、英: Dirichlet's box principle, Dirichlet's drawer principle)、あるいは部屋割り論法とは、n 個の物を m 個の箱に入れるとき、n > m であれば、少なくとも1個の箱には1個より多い物が中にある、という原理である。別の言い方をすれば、1つの箱に1つの物を入れるとき、m 個の箱には最大 m 個の物しか入れることができない(もう1つ物を入れたいなら、箱の1つを再利用しないといけないから)、ということである。
鳩の巣原理は数え上げ問題の例の一つで、一対一対応ができない無限集合など、多くの形式的問題に適用できる。
この原理に関する最初の記述は、ペーター・グスタフ・ディリクレが1834年に "Schubfachprinzip"(「引き出し原理」)の名前で書いたものであると信じられている。また、ディリクレが発見したためディリクレの原理と呼ばれることもある(同名の、調和関数における最小原理と混同してはいけない)。日本語では、以上の「—原理」はすべて「—論法」と訳されることもある。鳩の巣原理という訳語は pigeonhole が持つ「鳩小屋の仕切り巣箱」という意味に着目したものであるが、pigeonhole の第一義は仕切り箱や分類棚であるからこれは誤訳なのだと上野健爾は指摘している[2]。19世紀から整数論で使われてきた歴史を踏まえ上野はこの原理をディリクレの部屋割り論法と呼んでいる。
この原理は、ディオファントス近似において、小さな係数を持ち、なおかつ指定された解をもつ線形方程式系の存在を示すために応用される。この方法は、「ジーゲルの補題」という名前で知られる。発見者であるディリクレ自身、そのような高度な技巧を経由するものではないがディオファントス近似に関する彼の定理を証明するためにこの原理を用いている。また、さらに一般的な数学的構造においても類似の定理が数多く存在することが知られている。