Pigeonhole principle (original) (raw)
In der Mathematik ist das Schubfachprinzip (engl. pigeonhole principle, daher auch Taubenschlagprinzip) eine einfache, intuitive und oftmals hilfreiche Methode, um gewisse Aussagen über eine endliche Menge zu machen. Das Prinzip wird oft in der diskreten Mathematik verwendet.
| Property | Value |
|---|---|
| dbo:abstract | El principi de les caselles, de Dirichlet o del colomar diu que si repartim n objectes en k caselles, i n és més gran que k, aleshores, necessàriament alguna de les caselles ha de rebre més d'un objecte. La idea en què es basa és molt senzilla: si s'han de col·locar tres coloms en dues gàbies, per força dos coloms han de compartir una mateixa gàbia. L'origen del principi, almenys en el camp de les matemàtiques, és atribuït al matemàtic Johann Peter Gustav Lejeune Dirichlet el 1834. Segons , a la dècada de 1950 els especialistes en teoria de nombres de les universitats de Viena i Hamburg ja parlaven del principi de les caselles, referint-lo de vegades a Dirichlet. La denominació original en alemany fa referència a calaixos (Schubfachprinzip, on Schubfach vol dir calaix), però la traducció anglesa, pigeonhole principle, ha fet que en els exemples sovint es parli de pigeons ('coloms') i holes ('forats'), i això duu a la pintoresca denominació de principi del colomar. Hi ha diverses versions més generals del principi que es poden enunciar de diferents maneres. Una versió diu que per k i m nombres naturals, si es distribueixen n = km + 1 objectes en k caselles, aleshores almenys una de les caselles tindrà com a mínim m + 1 objectes. Per a n i k arbitraris, això es generalitza de manera que almenys una casella tindrà ⌊n/k⌋ + 1 objectes, si k no és divisor de n, o n/k objectes, si k és divisor de n, a on els símbols ⌊·⌋ denoten la part entera. Encara que pugui semblar trivial, el principi de les caselles és molt eficaç per a demostrar, en un conjunt amb condicions que afecten només el nombre d'elements, l'existència d'alguns elements que comparteixen les mateixes propietats. (ca) Dirichletův princip (někdy také označovaný jako zásuvkový princip, přihrádkový princip nebo princip holubníku) je matematické tvrzení z teorie množin, případně nekonečné kombinatoriky. Nejjednodušší, „populární“ znění principu se dá formulovat například, že pokud umístíme m předmětů do n přihrádek (m, n jsou přirozená čísla), kde m > n, pak bude existovat alespoň jedna přihrádka ve které budou alespoň dva předměty. Umístíme-li tedy například deset holubů (m = 10) do devíti přihrádek v holubníku (n = 9), pak v alespoň jedné přihrádce musí být alespoň dva holubi. V jeho obecnější verzi pak lze říct, že pokud umístíme kn+1 předmětů do n přihrádek, pak v alespoň jedné přihrádce bude alespoň k+1 předmětů (pro 19 holubů a devět přihrádek bude existovat alespoň jedna, v které budou alespoň 3 holubi). Tato jednoduchá tvrzení jsou poté dále zobecněna a formálněji definována – viz níže. Ačkoliv tento samozřejmý princip byl používán již dříve, za prvního, kdo ho užíval vědomě k dokazování složitějších tvrzení, je považován německý matematik Johann Peter Gustav Lejeune Dirichlet (1805–1859). Ten jej jako první výslovně uvedl v roce 1834 pod názvem Schubfachprinzip (zásuvkový princip). Pod označením zásuvkový princip (principio dei cassetti) je dodnes používán např. v italštině. V angličtině se používá zejména označení pigeonhole principle (princip holubníku), v dalších jazycích (např. v ruštině) pak Dirichletův princip. Princip holubníku není úplně přesný překlad, protože slovo pigeonhole se v angličtině používá prakticky už jen v přeneseném významu, kdy znamená buď přihrádku, typicky v nějakém třídicím regálu na poštu, nebo i sloveso zaškatulkovat, zařadit do kategorie. Přesto se tento překlad používá (podobně i do němčiny zpětně pronikl pojem Taubenschlagprinzip) a holubi jsou oblíbeným příkladem, na kterém se tento princip ilustruje. (cs) في الرياضيات وعلم الحاسوب، ينص مبدأ برج الحمام (بالإنجليزية: Pigeonhole principle) على أنه إذا تم وضع n عناصر في m خانات بحيث أن n > m، إذن هنالك على الأقل خانة واحدة تحتوي على أكثر من عنصر.يمكن تمثيل هذه المبرهنة ببديهيات من واقع الحياة مثل: «في صف مكون من 13 طالب يوجد على الأقل طالبين ولدوا في نفس الشهر».بالرغم من أن المبدأ يظهر بديهيا، إلا أنه بالإمكان استخدامه لإثبات نتائج ربما غير متوقعة; على سبيل المثال، بأنه هناك شخصين في القاهرة لديهم نفس عدد الشعر على رأسيهما.(انظر إلى الأسفل) يعتقد بأن أول من أضاف طابعا رسميا على الفكرة هو ديركلي في 1834 تحت اسم Schubfachprinzip («مبدأ الجارور» أو «مبدأ الرف»). (ar) In der Mathematik ist das Schubfachprinzip (engl. pigeonhole principle, daher auch Taubenschlagprinzip) eine einfache, intuitive und oftmals hilfreiche Methode, um gewisse Aussagen über eine endliche Menge zu machen. Das Prinzip wird oft in der diskreten Mathematik verwendet. (de) Matematikan, Usategi printzipioak izanik elementu kaxetan sartzen direnean kaxa batek gutxienez elementu bat baino gehiago izan behar duela ezartzen duen teorema edo printzipioa da. Teorema honen izena usategietan sarritan ikusten den kasuarengatik ezarrita dago. Askotan, habiko usategi batean, habi kopuru baino uso gehiago egoten dira. Ondorioz, habietako batean (edo batzuetan) uso bat baino gehiago ipini beharko dira. Horri, Usategiaren printzipioa deritzogu. Matematikoki ere azaldu dezakegu: Izan bitez . Orduan, objektu multzotan banatzen baditugu eta * bada, orduan gutxienez bi objektu multzo berean egon beharko dira (printzipio arrunta). * existitzen bada zeinetarako den, orduan gutxienez objektu multzo berean egongo dira (printzipio orokortua). Printzipioa maiz erabiltzen matematikako frogapenetan, batik bat konbinatorian, eta informatikan. Lehenengo aldiz Dirichlet matematikariak 1834. urtean erabili zuela uste da, Schubfachprinzip edo kajoien printzipioa esapidea erabiliz. (eu) El principio del palomar, también llamado principio de Dirichlet o principio de las cajas, establece que si n palomas se distribuyen en m palomares, y si n > m, entonces al menos habrá un palomar con más de una paloma. Otra forma de decirlo es que m huecos pueden albergar como mucho m objetos si cada uno de los objetos está en un hueco distinto, así que el hecho de añadir otro objeto fuerza a volver a utilizar alguno de los huecos. A manera de ejemplo: si se toman trece personas, al menos dos habrán nacido el mismo mes. El primer enunciado del principio se cree que proviene de Dirichlet en 1834 con el nombre de Schubfachprinzip ("principio de los cajones"). No debe confundirse con otro principio sobre funciones armónicas, también con el nombre de este autor. (es) In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there must be at least two right-handed gloves, or at least two left-handed gloves, because there are three objects, but only two categories of handedness to put them into. This seemingly obvious statement, a type of counting argument, can be used to demonstrate possibly unexpected results. For example, given that the population of London is greater than the maximum number of hairs that can be present on a human's head, then the pigeonhole principle requires that there must be at least two people in London who have the same number of hairs on their heads. Although the pigeonhole principle appears as early as 1624 in a book attributed to Jean Leurechon, it is commonly called Dirichlet's box principle or Dirichlet's drawer principle after an 1834 treatment of the principle by Peter Gustav Lejeune Dirichlet under the name Schubfachprinzip ("drawer principle" or "shelf principle"). The principle has several generalizations and can be stated in various ways. In a more quantified version: for natural numbers k and m, if n = km + 1 objects are distributed among m sets, then the pigeonhole principle asserts that at least one of the sets will contain at least k + 1 objects. For arbitrary n and m, this generalizes to where and denote the floor and ceiling functions, respectively. Though the most straightforward application is to finite sets (such as pigeons and boxes), it is also used with infinite sets that cannot be put into one-to-one correspondence. To do so requires the formal statement of the pigeonhole principle, which is "there does not exist an injective function whose codomain is smaller than its domain". Advanced mathematical proofs like Siegel's lemma build upon this more general concept. (en) Prinsip rumah burung menyatakan bahwa untuk dua bilangan asli dan , , jika burung ditaruh di dalam rumah atau kotak, maka paling sedikit satu kotak berisi lebih dari satu burung. Secara lebih formal, dapat dikatakan bahwa tidak ada pada himpunan terhingga yang memiliki kodomain lebih kecil daripada domain. Prinsip ini pertama kali dinyatakan oleh Dirichlet pada 1834 dan diberi nama Schubfachprinzip (prinsip rak). Dalam beberapa bahasa, prinsip ini disebut prinsip Dirichlet. (in) En mathématiques, le principe des tiroirs de Dirichlet, affirme que si n chaussettes occupent m tiroirs, et si n > m, alors au moins un tiroir doit contenir strictement plus d'une chaussette. Une autre formulation serait que m tiroirs ne peuvent contenir strictement plus de m chaussettes avec une seule chaussette par tiroir ; ajouter une autre chaussette obligera à réutiliser l'un des tiroirs. Mathématiquement, le principe des tiroirs peut s'énoncer ainsi : Si E et F sont deux ensembles finis tels que card(E) > card(F) et si f : E → F est une application de E dans F, alors il existe un élément de F qui admet au moins deux antécédents par f ; autrement dit il n'existe pas d'application injective de E dans F. (fr) 鳩の巣原理（はとのすげんり、英: Pigeonhole principle）、またはディリクレの箱入れ原理（ディリクレのはこいれげんり、英: Dirichlet's box principle, Dirichlet's drawer principle）、あるいは部屋割り論法とは、n 個の物を m 個の箱に入れるとき、n > m であれば、少なくとも1個の箱には1個より多い物が中にある、という原理である。別の言い方をすれば、1つの箱に1つの物を入れるとき、m 個の箱には最大 m 個の物しか入れることができない（もう1つ物を入れたいなら、箱の1つを再利用しないといけないから）、ということである。 鳩の巣原理は数え上げ問題の例の一つで、一対一対応ができない無限集合など、多くの形式的問題に適用できる。 この原理に関する最初の記述は、ディリクレが1834年に "Schubfachprinzip"（「引き出し原理」）の名前で書いたものであると信じられている。また、ディリクレが発見したためディリクレの原理と呼ばれることもある（同名の、調和関数における最小原理と混同してはいけない）。日本語では、以上の「—原理」はすべて「—論法」と訳されることもある。 この原理は、ディオファントス近似において、小さな係数を持ち、なおかつ指定された解をもつ線形方程式系の存在を示すために応用される。この方法は、「ジーゲルの補題」という名前で知られる。発見者であるディリクレ自身、そのような高度な技巧を経由するものではないがディオファントス近似に関する彼の定理を証明するためにこの原理を用いている。また、さらに一般的な数学的構造においても類似の定理が数多く存在することが知られている。 (ja) 비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 서랍 원칙 또는 디리클레의 방 나누기 원칙이라고 부르기도 하며 구두 상자의 원리라고도 한다. (ko) Het duiventilprincipe, duivenhokprincipe of ladenprincipe van Dirichlet is een principe in de wiskunde dat stelt dat als duiven in een duiventil met hokjes geplaatst worden, waarbij dat er dan minstens één hokje is waar meer dan één duif in zit. Het duiventilprincipe werd waarschijnlijk voor het eerst geformuleerd door Johann Dirichlet in 1834. Een meer abstracte formulering van het principe luidt: als objecten verdeeld worden in verzamelingen waarbij , dan bevat minstens een van die verzamelingen ten minste 2 elementen. Een generalisatie van het ladenprincipe luidt als volgt: als minstens objecten verdeeld worden in verzamelingen, dan is er minstens één verzameling die ten minste elementen bevat. Een grappig gevolg van het duiventilprincipe is het "bewijs" dat er in de stad New York (of een willekeurige andere miljoenenstad) minstens twee mensen rondlopen met precies evenveel haren op hun hoofd. Dit loopt als volgt: een mens heeft gemiddeld zo'n 150.000 haren op zijn hoofd; het is dus redelijk om aan te nemen dat niemand meer dan een miljoen hoofdharen heeft. In New York wonen meer dan een miljoen mensen. Deze (meer dan een miljoen) mensen moeten dus verdeeld worden in (één miljoen of minder) verzamelingen; één verzameling per mogelijk aantal hoofdharen. Volgens het duiventilprincipe zitten er dus in minstens een van deze verzamelingen minstens twee mensen. (nl) Il principio dei cassetti, detto anche legge del buco della piccionaia, afferma che se n+k oggetti sono messi in n cassetti, allora almeno un cassetto deve contenere più di un oggetto. Un altro modo di vedere il principio è che una piccionaia con m caselle può contenere al più m piccioni, se non se ne vogliono mettere più di uno in nessuna casella: un ulteriore volatile dovrà necessariamente condividere la casella con un suo simile. Formalmente, il principio afferma che se A e B sono due insiemi finiti e B ha cardinalità strettamente minore di A, allora non esiste alcuna funzione iniettiva da A a B. Il principio dei cassetti è un esempio di un argomento combinatorio, che può essere applicato a molti problemi formali, compresi quelli relativi a insiemi infiniti che non possono essere messi in corrispondenza biunivoca. Nell'approssimazione diofantea l'applicazione quantitativa del principio all'esistenza di soluzioni intere di un sistema di equazioni lineari va sotto il nome di "lemma di Siegel". Si ritiene che il principio sia stato esplicitato per la prima volta da Dirichlet nel 1834 col nome Schubfachprinzip ("principio del cassetto"). In alcune lingue, (ad esempio il russo) questo principio è pertanto noto come il "principio di Dirichlet", da non confondersi con il principio dello stesso nome sulle funzioni armoniche. In inglese, invece, si parla di pigeonhole principle, dove il "pigeonhole" si riferisce alle cassette postali aperte in uso in alcuni uffici e università. (it) Zasada szufladkowa Dirichleta – twierdzenie matematyczne, mówiące: Jeżeli przedmiotów włoży się do różnych szufladek, gdzie to w co najmniej jednej szufladce znajdą się co najmniej dwa przedmioty. Formalna treść twierdzenia: * jeżeli zbiór liczy elementów, gdzie to któryś ze zbiorów musi zawierać co najmniej dwa elementy. Inna wersja formalna brzmi następująco: * Jeżeli moc zbioru wynosi a zbioru – i to nie istnieje funkcja różnowartościowa ze zbioru do zbioru . Wydaje się, że ta oczywista obserwacja nie może mieć poważnych zastosowań, ale jest dokładnie przeciwnie. Zasada szufladkowa bywa wykorzystywana w dowodach wielu głębokich twierdzeń matematycznych i często samo zauważenie, że można ją zastosować, jest kluczem do rozwiązania problemu. Sformułowanie zasady szufladkowej przypisuje się często Peterowi Dirichletowi w 1834 r., który nazwał ją Schubfachprinzip. Jednak w literaturze zasada ta pojawiała się znacznie wcześniej, pierwszy raz prawdopodobnie w książce Selectae propositiones in tota sparsim mathematica pulcherrimae z 1622 r. autorstwa francuskiego jezuity . (pl) O princípio do pombal ou princípio da casa dos pombos é a afirmação de que se n pombos devem ser postos em m casas, e se n > m, então pelo menos uma casa irá conter mais de um pombo. Matematicamente falando, isto quer dizer que se o número de elementos de um conjunto finito A é maior do que o número de elementos de um outro conjunto B, então uma função de A em B não pode ser injetiva. É também conhecido como teorema de Dirichlet ou princípio das gavetas de Dirichlet, pois supõe-se que o primeiro relato deste princípio tenha sido feito por Dirichlet em 1834, com o nome de Schubfachprinzip ("princípio das gavetas"). O princípio do pombal é um exemplo de um argumento de calcular que pode ser aplicado a muitos problemas formais, incluindo aqueles que envolvem um conjunto infinito. Embora se trate de uma evidência extremamente elementar, o princípio é útil para resolver problemas que, pelo menos à primeira vista, não são imediatos. Para aplicá-lo, devemos identificar, na situação dada, quem faz o papel dos objetos e quem faz o papel das gavetas. (pt) Dirichlets lådprincip, även kallad Postfacksprincipen eller duvslagsprincipen är ett resultat inom den diskreta matematiken och lyder som följer: Om man har fler brev än kommer något postfack att innehålla minst två brev, om man lägger varje brev i något av postfacken. Även om detta kan låta närmast självklart visar det sig mycket kraftfullt i många sammanhang.Dirichlets lådprincip blandas ofta samman med , ett begrepp som infördes av Bernhard Riemann inom potentialteorin. Den första formaliseringen av Dirichlets lådprincip tros ha gjorts av Peter Gustav Lejeune Dirichlet 1834. (sv) При́нцип Діріхле́ (також принцип коробок Діріхле, принцип голубів і кліток) — комбінаторне твердження, сформульоване німецьким математиком Петером Діріхле. (uk) При́нцип Дирихле́ — простой, интуитивно понятный и часто полезный метод для доказательства утверждений о конечном множестве. Этот принцип часто используется в дискретной математике, где устанавливает связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий. В английском и некоторых других языках данное утверждение известно как «принцип голубей и ящиков» (англ. pigeonhole principle), когда объектами являются голуби, а контейнерами — ящики. Наиболее распространена простейшая формулировка принципа Дирихле: Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика. Распространена также и парная к ней формулировка: Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста. Другие, более общие формулировки см. ниже. Первую формулировку данного принципа историки обнаружили в популярном сборнике «Занимательная математика» (фр. Récréations Mathématiques, 1624 год, под именем H. van Etten), который опубликовал (предположительно) французский математик . Широкое распространение этот принцип получил после его применения Дирихле (начиная с 1834 года) в области теории чисел. Принцип Дирихле в том или ином виде успешно применяется при доказательстве теорем, делая эти доказательства проще и понятнее. Среди его областей применения — дискретная математика, теория диофантовых приближений, анализ разрешимости систем линейных неравенств и т. п. Доказательства, использующие принцип Дирихле, относятся к числу неконструктивных, поскольку они носят косвенный характер, не позволяют сделать конкретные выводы о фактическом размещении объектов. (ru) 鴿巢原理，又名狄利克雷抽屜原理、鴿籠原理。 其中一種簡單的表述法為： * 若有n個籠子和n+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少2隻鴿子。 另一種為： * 若有n個籠子和kn+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少k+1隻鴿子。 集合论的表述如下： * 若A是n+1元集，B是n元集，則不存在從A到B的單射。 拉姆齐定理是此原理的推廣。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/TooManyPigeons.jpg?width=300 |
| dbo:wikiPageExternalLink | http://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle https://ghostarchive.org/varchive/youtube/20211211/HMpSKjK9clA%7C https://www.youtube.com/watch%3Fv=HMpSKjK9clA http://zimmer.csufresno.edu/~larryc/proofs/proofs.pigeonhole.html http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD980.html http://www.cut-the-knot.org/do_you_know/pigeon.shtml https://archive.org/details/discretecombinat00grim_1 |
| dbo:wikiPageID | 54217 (xsd:integer) |
| dbo:wikiPageLength | 29466 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123142085 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probability_distribution dbr:Quantum_mechanics dbr:Birthday_problem dbr:Hungarian_language dbr:Persian_language dbr:Peter_Gustav_Lejeune_Dirichlet dbr:Vietnamese_language dbr:Dedekind-infinite_set dbr:Degree_(graph_theory) dbr:Dovecote dbr:Infinite_set dbr:Interferometry dbr:Pochhammer_symbol dbr:Mathematical_analysis dbr:Mathematics dbr:Mean dbr:One-to-one_correspondence dbr:Siegel's_lemma dbr:Pumping_lemma_for_regular_languages dbr:Alexander_Bogomolny dbr:Graph_(discrete_mathematics) dbr:Multinomial_theorem dbr:Arabic_language dbr:London dbr:Lossless_compression dbr:Combinatorial_principles dbr:Combinatorial_proof dbr:Combinatorics dbr:Dense-in-itself dbr:Écu dbr:Bulgarian_language dbc:Mathematical_principles dbr:Ceiling_function dbr:Turkish_language dbr:Wave_function dbr:Domain_of_a_function dbr:Irrational_number dbr:Lingua_franca dbc:Combinatorics dbc:Theorems_in_discrete_mathematics dbr:Danish_language dbr:Dutch_language dbr:Edge_(graph) dbr:Finite_set dbr:Floor_function dbr:Cardinal_number dbr:Fractional_part dbr:Hilbert's_paradox_of_the_Grand_Hotel dbr:Random_variable dbr:Italian_language dbr:Japanese_language dbr:Tautology_(logic) dbr:Art_gallery_problem dbc:Ramsey_theory dbr:Chinese_language dbr:Blichfeldt's_theorem dbr:Swedish_language dbr:Codomain dbr:Jean_Leurechon dbr:Average dbr:Axiom_of_choice dbr:Polish_language dbr:Portuguese_language dbr:Injective_function dbr:Natural_number dbr:Ramsey's_theorem dbr:Yakir_Aharonov dbr:YouTube dbr:Interferometer dbr:Vertex_(graph_theory) dbr:Pigeon-hole_messagebox dbr:PBS_Infinite_Series dbr:Falling_factorial dbr:Edsger_Dijkstra dbr:Dedekind_finite dbr:Lattice_spacing dbr:Birthday_paradox dbr:File:Pigeon-hole_messagebox_3.jpg dbr:File:TooManyPigeons.jpg dbr:Wikt:drawer |
| dbp:id | p/d032800 (en) |
| dbp:title | Dirichlet box principle (en) |
| dbp:wikiPageUsesTemplate | dbt:Springer dbt:! dbt:= dbt:Cbignore dbt:Citation dbt:Cite_web dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Spoken_Wikipedia |
| dct:subject | dbc:Mathematical_principles dbc:Combinatorics dbc:Theorems_in_discrete_mathematics dbc:Ramsey_theory |
| rdf:type | yago:WikicatCryptographicHashFunctions yago:WikicatMathematicalPrinciples yago:WikicatMathematicalProofs yago:WikicatMathematicalTheorems yago:WikicatTheoremsInCombinatorics yago:WikicatTheoremsInDiscreteMathematics yago:Abstraction100002137 yago:Argument106648724 yago:Cognition100023271 yago:Communication100033020 yago:Content105809192 yago:Evidence106643408 yago:Function113783816 yago:Generalization105913275 yago:GrammaticalRelation113796779 yago:Idea105833840 yago:Indication106797169 yago:Inflection113803782 yago:LinguisticRelation113797142 yago:MathematicalProof106647864 yago:MathematicalRelation113783581 yago:Message106598915 yago:Paradigm113804375 yago:Principle105913538 yago:Proof106647614 yago:Proposition106750804 yago:PsychologicalFeature100023100 yago:Relation100031921 yago:Statement106722453 yago:Theorem106752293 yago:WikicatProgrammingParadigms |
| rdfs:comment | In der Mathematik ist das Schubfachprinzip (engl. pigeonhole principle, daher auch Taubenschlagprinzip) eine einfache, intuitive und oftmals hilfreiche Methode, um gewisse Aussagen über eine endliche Menge zu machen. Das Prinzip wird oft in der diskreten Mathematik verwendet. (de) Prinsip rumah burung menyatakan bahwa untuk dua bilangan asli dan , , jika burung ditaruh di dalam rumah atau kotak, maka paling sedikit satu kotak berisi lebih dari satu burung. Secara lebih formal, dapat dikatakan bahwa tidak ada pada himpunan terhingga yang memiliki kodomain lebih kecil daripada domain. Prinsip ini pertama kali dinyatakan oleh Dirichlet pada 1834 dan diberi nama Schubfachprinzip (prinsip rak). Dalam beberapa bahasa, prinsip ini disebut prinsip Dirichlet. (in) 비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 서랍 원칙 또는 디리클레의 방 나누기 원칙이라고 부르기도 하며 구두 상자의 원리라고도 한다. (ko) Dirichlets lådprincip, även kallad Postfacksprincipen eller duvslagsprincipen är ett resultat inom den diskreta matematiken och lyder som följer: Om man har fler brev än kommer något postfack att innehålla minst två brev, om man lägger varje brev i något av postfacken. Även om detta kan låta närmast självklart visar det sig mycket kraftfullt i många sammanhang.Dirichlets lådprincip blandas ofta samman med , ett begrepp som infördes av Bernhard Riemann inom potentialteorin. Den första formaliseringen av Dirichlets lådprincip tros ha gjorts av Peter Gustav Lejeune Dirichlet 1834. (sv) При́нцип Діріхле́ (також принцип коробок Діріхле, принцип голубів і кліток) — комбінаторне твердження, сформульоване німецьким математиком Петером Діріхле. (uk) 鴿巢原理，又名狄利克雷抽屜原理、鴿籠原理。 其中一種簡單的表述法為： * 若有n個籠子和n+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少2隻鴿子。 另一種為： * 若有n個籠子和kn+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少k+1隻鴿子。 集合论的表述如下： * 若A是n+1元集，B是n元集，則不存在從A到B的單射。 拉姆齐定理是此原理的推廣。 (zh) في الرياضيات وعلم الحاسوب، ينص مبدأ برج الحمام (بالإنجليزية: Pigeonhole principle) على أنه إذا تم وضع n عناصر في m خانات بحيث أن n > m، إذن هنالك على الأقل خانة واحدة تحتوي على أكثر من عنصر.يمكن تمثيل هذه المبرهنة ببديهيات من واقع الحياة مثل: «في صف مكون من 13 طالب يوجد على الأقل طالبين ولدوا في نفس الشهر».بالرغم من أن المبدأ يظهر بديهيا، إلا أنه بالإمكان استخدامه لإثبات نتائج ربما غير متوقعة; على سبيل المثال، بأنه هناك شخصين في القاهرة لديهم نفس عدد الشعر على رأسيهما.(انظر إلى الأسفل) (ar) El principi de les caselles, de Dirichlet o del colomar diu que si repartim n objectes en k caselles, i n és més gran que k, aleshores, necessàriament alguna de les caselles ha de rebre més d'un objecte. La idea en què es basa és molt senzilla: si s'han de col·locar tres coloms en dues gàbies, per força dos coloms han de compartir una mateixa gàbia. Encara que pugui semblar trivial, el principi de les caselles és molt eficaç per a demostrar, en un conjunt amb condicions que afecten només el nombre d'elements, l'existència d'alguns elements que comparteixen les mateixes propietats. (ca) Dirichletův princip (někdy také označovaný jako zásuvkový princip, přihrádkový princip nebo princip holubníku) je matematické tvrzení z teorie množin, případně nekonečné kombinatoriky. Nejjednodušší, „populární“ znění principu se dá formulovat například, že pokud umístíme m předmětů do n přihrádek (m, n jsou přirozená čísla), kde m > n, pak bude existovat alespoň jedna přihrádka ve které budou alespoň dva předměty. Umístíme-li tedy například deset holubů (m = 10) do devíti přihrádek v holubníku (n = 9), pak v alespoň jedné přihrádce musí být alespoň dva holubi. V jeho obecnější verzi pak lze říct, že pokud umístíme kn+1 předmětů do n přihrádek, pak v alespoň jedné přihrádce bude alespoň k+1 předmětů (pro 19 holubů a devět přihrádek bude existovat alespoň jedna, v které budou alespoň 3 holu (cs) El principio del palomar, también llamado principio de Dirichlet o principio de las cajas, establece que si n palomas se distribuyen en m palomares, y si n > m, entonces al menos habrá un palomar con más de una paloma. Otra forma de decirlo es que m huecos pueden albergar como mucho m objetos si cada uno de los objetos está en un hueco distinto, así que el hecho de añadir otro objeto fuerza a volver a utilizar alguno de los huecos. A manera de ejemplo: si se toman trece personas, al menos dos habrán nacido el mismo mes. (es) Matematikan, Usategi printzipioak izanik elementu kaxetan sartzen direnean kaxa batek gutxienez elementu bat baino gehiago izan behar duela ezartzen duen teorema edo printzipioa da. Teorema honen izena usategietan sarritan ikusten den kasuarengatik ezarrita dago. Askotan, habiko usategi batean, habi kopuru baino uso gehiago egoten dira. Ondorioz, habietako batean (edo batzuetan) uso bat baino gehiago ipini beharko dira. Horri, Usategiaren printzipioa deritzogu. Matematikoki ere azaldu dezakegu: Izan bitez . Orduan, objektu multzotan banatzen baditugu eta (eu) In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there must be at least two right-handed gloves, or at least two left-handed gloves, because there are three objects, but only two categories of handedness to put them into. This seemingly obvious statement, a type of counting argument, can be used to demonstrate possibly unexpected results. For example, given that the population of London is greater than the maximum number of hairs that can be present on a human's head, then the pigeonhole principle requires that there must be at least two people in London who have the same number of hairs on their (en) En mathématiques, le principe des tiroirs de Dirichlet, affirme que si n chaussettes occupent m tiroirs, et si n > m, alors au moins un tiroir doit contenir strictement plus d'une chaussette. Une autre formulation serait que m tiroirs ne peuvent contenir strictement plus de m chaussettes avec une seule chaussette par tiroir ; ajouter une autre chaussette obligera à réutiliser l'un des tiroirs. Mathématiquement, le principe des tiroirs peut s'énoncer ainsi : (fr) 鳩の巣原理（はとのすげんり、英: Pigeonhole principle）、またはディリクレの箱入れ原理（ディリクレのはこいれげんり、英: Dirichlet's box principle, Dirichlet's drawer principle）、あるいは部屋割り論法とは、n 個の物を m 個の箱に入れるとき、n > m であれば、少なくとも1個の箱には1個より多い物が中にある、という原理である。別の言い方をすれば、1つの箱に1つの物を入れるとき、m 個の箱には最大 m 個の物しか入れることができない（もう1つ物を入れたいなら、箱の1つを再利用しないといけないから）、ということである。 鳩の巣原理は数え上げ問題の例の一つで、一対一対応ができない無限集合など、多くの形式的問題に適用できる。 この原理に関する最初の記述は、ディリクレが1834年に "Schubfachprinzip"（「引き出し原理」）の名前で書いたものであると信じられている。また、ディリクレが発見したためディリクレの原理と呼ばれることもある（同名の、調和関数における最小原理と混同してはいけない）。日本語では、以上の「—原理」はすべて「—論法」と訳されることもある。 (ja) Il principio dei cassetti, detto anche legge del buco della piccionaia, afferma che se n+k oggetti sono messi in n cassetti, allora almeno un cassetto deve contenere più di un oggetto. Un altro modo di vedere il principio è che una piccionaia con m caselle può contenere al più m piccioni, se non se ne vogliono mettere più di uno in nessuna casella: un ulteriore volatile dovrà necessariamente condividere la casella con un suo simile. Formalmente, il principio afferma che se A e B sono due insiemi finiti e B ha cardinalità strettamente minore di A, allora non esiste alcuna funzione iniettiva da A a B. (it) Zasada szufladkowa Dirichleta – twierdzenie matematyczne, mówiące: Jeżeli przedmiotów włoży się do różnych szufladek, gdzie to w co najmniej jednej szufladce znajdą się co najmniej dwa przedmioty. Formalna treść twierdzenia: * jeżeli zbiór liczy elementów, gdzie to któryś ze zbiorów musi zawierać co najmniej dwa elementy. Inna wersja formalna brzmi następująco: * Jeżeli moc zbioru wynosi a zbioru – i to nie istnieje funkcja różnowartościowa ze zbioru do zbioru . (pl) Het duiventilprincipe, duivenhokprincipe of ladenprincipe van Dirichlet is een principe in de wiskunde dat stelt dat als duiven in een duiventil met hokjes geplaatst worden, waarbij dat er dan minstens één hokje is waar meer dan één duif in zit. Het duiventilprincipe werd waarschijnlijk voor het eerst geformuleerd door Johann Dirichlet in 1834. Een meer abstracte formulering van het principe luidt: als objecten verdeeld worden in verzamelingen waarbij , dan bevat minstens een van die verzamelingen ten minste 2 elementen. (nl) При́нцип Дирихле́ — простой, интуитивно понятный и часто полезный метод для доказательства утверждений о конечном множестве. Этот принцип часто используется в дискретной математике, где устанавливает связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий. В английском и некоторых других языках данное утверждение известно как «принцип голубей и ящиков» (англ. pigeonhole principle), когда объектами являются голуби, а контейнерами — ящики. Наиболее распространена простейшая формулировка принципа Дирихле: Распространена также и парная к ней формулировка: (ru) O princípio do pombal ou princípio da casa dos pombos é a afirmação de que se n pombos devem ser postos em m casas, e se n > m, então pelo menos uma casa irá conter mais de um pombo. Matematicamente falando, isto quer dizer que se o número de elementos de um conjunto finito A é maior do que o número de elementos de um outro conjunto B, então uma função de A em B não pode ser injetiva. O princípio do pombal é um exemplo de um argumento de calcular que pode ser aplicado a muitos problemas formais, incluindo aqueles que envolvem um conjunto infinito. (pt) |
| rdfs:label | مبدأ برج الحمام (ar) Principi de les caselles (ca) Dirichletův princip (cs) Schubfachprinzip (de) Principio del palomar (es) Usategi printzipio (eu) Prinsip rumah burung (in) Principe des tiroirs (fr) Principio dei cassetti (it) 鳩の巣原理 (ja) 비둘기집 원리 (ko) Duiventilprincipe (nl) Pigeonhole principle (en) Zasada szufladkowa Dirichleta (pl) Princípio da casa dos pombos (pt) Принцип Дирихле (комбинаторика) (ru) Dirichlets lådprincip (sv) 鴿巢原理 (zh) Принцип Діріхле (uk) |
| owl:sameAs | freebase:Pigeonhole principle yago-res:Pigeonhole principle wikidata:Pigeonhole principle http://am.dbpedia.org/resource/የደበኔ_ሳጥን_መርህ dbpedia-ar:Pigeonhole principle http://ast.dbpedia.org/resource/Principiu_del_palombar dbpedia-bg:Pigeonhole principle http://bs.dbpedia.org/resource/Princip_golubinjaka dbpedia-ca:Pigeonhole principle dbpedia-cs:Pigeonhole principle dbpedia-cy:Pigeonhole principle dbpedia-da:Pigeonhole principle dbpedia-de:Pigeonhole principle dbpedia-es:Pigeonhole principle dbpedia-eu:Pigeonhole principle dbpedia-fa:Pigeonhole principle dbpedia-fi:Pigeonhole principle dbpedia-fr:Pigeonhole principle dbpedia-he:Pigeonhole principle dbpedia-hr:Pigeonhole principle dbpedia-hu:Pigeonhole principle dbpedia-id:Pigeonhole principle dbpedia-is:Pigeonhole principle dbpedia-it:Pigeonhole principle dbpedia-ja:Pigeonhole principle dbpedia-kk:Pigeonhole principle dbpedia-ko:Pigeonhole principle http://lv.dbpedia.org/resource/Dirihlē_princips http://ml.dbpedia.org/resource/പ്രാവിൻപൊത്ത്_തത്വം http://mn.dbpedia.org/resource/Дирихлегийн_зарчим dbpedia-nl:Pigeonhole principle dbpedia-no:Pigeonhole principle dbpedia-pl:Pigeonhole principle dbpedia-pms:Pigeonhole principle dbpedia-pt:Pigeonhole principle dbpedia-ro:Pigeonhole principle dbpedia-ru:Pigeonhole principle dbpedia-simple:Pigeonhole principle dbpedia-sq:Pigeonhole principle dbpedia-sr:Pigeonhole principle dbpedia-sv:Pigeonhole principle dbpedia-th:Pigeonhole principle dbpedia-tr:Pigeonhole principle dbpedia-uk:Pigeonhole principle http://ur.dbpedia.org/resource/کبوترخانہ_اصول http://uz.dbpedia.org/resource/Dirixle_prinsipi dbpedia-vi:Pigeonhole principle dbpedia-zh:Pigeonhole principle https://global.dbpedia.org/id/oaLD |
| prov:wasDerivedFrom | wikipedia-en:Pigeonhole_principle?oldid=1123142085&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Pigeon-hole_messagebox_3.jpg wiki-commons:Special:FilePath/TooManyPigeons.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Pigeonhole_principle |
| is dbo:wikiPageDisambiguates of | dbr:Pigeonhole |
| is dbo:wikiPageRedirects of | dbr:Pigeonhole_Principle dbr:Pierre_Pigeonhole dbr:Drawer_principle dbr:Dirichlet's_Box_Principle dbr:Dirichlet's_box_principle dbr:Dirichlet's_drawer_principle dbr:Dirichlet_box_principle dbr:Dirichlet_drawer_principle dbr:Dirilecht's_Principle dbr:Pidgeonhole dbr:Pigeon-Hole_Principle dbr:Pigeon-hole_principle dbr:Pigeon_hole_principle dbr:Pigeonhole_argument dbr:Pigeonhole_principal dbr:Box_principle dbr:Example_of_pigeonhole_principle |
| is dbo:wikiPageWikiLink of | dbr:Principle dbr:Multiplicative_order dbr:Kinnim dbr:Birthday_problem dbr:Antichain dbr:Peter_Gustav_Lejeune_Dirichlet dbr:Repeating_decimal dbr:Charging_argument dbr:DSPACE dbr:Van_der_Waerden's_theorem dbr:Dovecote dbr:Incompressibility_method dbr:Kőnig's_lemma dbr:Propositional_proof_system dbr:Computability dbr:Maximum_disjoint_set dbr:Geometric_separator dbr:Siegel's_lemma dbr:Russell_Impagliazzo dbr:Pumping_lemma_for_regular_languages dbr:Entropy_(information_theory) dbr:Theorem dbr:Erdős–Szekeres_theorem dbr:Lossless_compression dbr:Magnetic-tape_data_storage dbr:Claw-free_graph dbr:Collision_problem dbr:Collision_resistance dbr:Combinatorial_principles dbr:Combinatorial_proof dbr:Combinatorics dbr:Hales–Jewett_theorem dbr:PHP_(disambiguation) dbr:PPP_(complexity) dbr:Pigeonhole dbr:Pigeonhole_sort dbr:Matroid_partitioning dbr:Thue's_lemma dbr:Triangle-free_graph dbr:Data_deduplication dbr:Wafer_(electronics) dbr:Counting_argument dbr:Hash_collision dbr:Lone_divider dbr:TFNP dbr:Toniann_Pitassi dbr:Theorem_on_friends_and_strangers dbr:Algebraic_number_theory dbr:Analytic_number_theory dbr:Finite_set dbr:No-three-in-line_problem dbr:Numbers_(season_6) dbr:Cardinality dbr:Cayley_table dbr:Diophantine_approximation dbr:Dirichlet's_approximation_theorem dbr:Dirichlet's_theorem dbr:Farthest-first_traversal dbr:Graphic_matroid dbr:Hilbert's_paradox_of_the_Grand_Hotel dbr:Kolmogorov_complexity dbr:List_of_Martin_Gardner_Mathematical_Games_columns dbr:List_of_things_named_after_Peter_Gustav_Lejeune_Dirichlet dbr:Partition_regularity dbr:Primitive_element_theorem dbr:Ramsey_theory dbr:Counting dbr:Chernoff_bound dbr:Lagrange's_four-square_theorem dbr:Birthday_attack dbr:Blichfeldt's_theorem dbr:Block_size_(cryptography) dbr:Jean_Leurechon dbr:Toffoli_gate dbr:Twelvefold_way dbr:Division_(mathematics) dbr:Pigeonhole_Principle dbr:Cirquent_calculus dbr:Frege_system dbr:Idina_Menzel dbr:Igor_Kluvánek dbr:Miklós_Ajtai dbr:Off-by-one_error dbr:Ramsey's_theorem dbr:Longest-processing-time-first_scheduling dbr:Look-and-say_sequence dbr:Without_loss_of_generality dbr:Law_of_small_numbers dbr:Strong_law_of_small_numbers dbr:Five_points_determine_a_conic dbr:Pigeonholing dbr:Subadditivity dbr:Padding_oracle_attack dbr:Zermelo's_theorem_(game_theory) dbr:Outline_of_combinatorics dbr:Outline_of_discrete_mathematics dbr:Pierre_Pigeonhole dbr:Truthful_job_scheduling dbr:Venti dbr:Drawer_principle dbr:Dirichlet's_Box_Principle dbr:Dirichlet's_box_principle dbr:Dirichlet's_drawer_principle dbr:Dirichlet_box_principle dbr:Dirichlet_drawer_principle dbr:Dirilecht's_Principle dbr:Pidgeonhole dbr:Pigeon-Hole_Principle dbr:Pigeon-hole_principle dbr:Pigeon_hole_principle dbr:Pigeonhole_argument dbr:Pigeonhole_principal dbr:Box_principle dbr:Example_of_pigeonhole_principle |
| is owl:differentFrom of | dbr:Dirichlet's_principle |
| is foaf:primaryTopic of | wikipedia-en:Pigeonhole_principle |
