View source for पिजनहोल सिद्धांत

{{short description|If there are more items than boxes holding them, one box must contain at least two items}}
[[Image:TooManyPigeons.jpg|thumb|right|छिद्रों में कबूतर, यहाँ {{math|1=''m'' = 9}} छिद्र में {{math|1=''n'' = 10}} कबूतर हैं। यद्यपि 10, 9 से बड़ा है, पिजनहोल सिद्धांत कहता है कि कम से कम छिद्र में 1 से अधिक कबूतर हैं। (ऊपरी बाएँ छिद्र में 2 कबूतर हैं।)]]गणित में, '''पिजनहोल सिद्धांत''' कहता है कि यदि {{mvar|n}} वस्तु को {{math|''n'' > ''m''}} के साथ {{mvar|m}} कंटेनर में रखा जाता है, तो कम से कम प्रत्येक कंटेनर में अधिक वस्तुएँ होनी चाहिए।<ref name=Herstein64>{{harvnb|Herstein|1964|loc= p.&nbsp;90}}</ref> उदाहरण के लिए, यदि किसी के निकट तीन ग्लव्स हैं (और उनमें से कोई भी उभयलिंगी/प्रतिवर्ती नहीं है), तो कम से कम दो दाएं हाथ के ग्लव्स होने चाहिए, अथवा कम से कम दो बाएं हाथ के ग्लव्स होने चाहिए, क्योंकि वस्तुएं तीन हैं, किन्तु हाथ की केवल दो ही श्रेणियां हैं। यह प्रतीत होता है कि स्पष्ट कथन [[साहचर्य|गणना]] तर्क का प्रकार है, जिसका उपयोग संभवतः अप्रत्याशित परिणामों को प्रदर्शित करने के लिए किया जा सकता है। उदाहरण के लिए, यह देखते हुए कि [[लंदन की जनसांख्यिकी|लंदन की जनसंख्या]] किसी व्यक्ति के शीर्ष पर उपस्तिथ बालों की अधिकतम संख्या से भी अधिक है, तो पिजनहोल सिद्धांत के अनुसार लंदन में कम से कम दो व्यक्ति ऐसे होने चाहिए जिनके शीर्ष पर बालों की संख्या समान हो।

यद्यपि पिजनहोल सिद्धांत 1624 में जीन लेउरेचॉन की पुस्तक में दिखाई देता है,<ref name=leurechon>{{cite journal|last1=Rittaud|first1=Benoît|last2=Heeffer|first2=Albrecht|doi=10.1007/s00283-013-9389-1|issue=2|journal=The Mathematical Intelligencer|mr=3207654|pages=27–29|title=पिजनहोल सिद्धांत, डिरिचलेट से दो शताब्दी पहले|volume=36|year=2014|hdl=1854/LU-4115264|s2cid=44193229|url=https://biblio.ugent.be/publication/4115264|hdl-access=free}}</ref> इसे सामान्यतः [[पीटर गुस्ताव लेज्यून डिरिचलेट]] द्वारा {{lang|de|Schubfachprinzip}} ("ड्रावर सिद्धांत" अथवा "शेल्फ सिद्धांत") नाम के अंतर्गत सिद्धांत के 1834 के उपचार के पश्चात डिरिचलेट का बॉक्स सिद्धांत अथवा डिरिचलेट का ड्रावर सिद्धांत कहा जाता है।।<ref>Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "[http://jeff560.tripod.com/p.html Pigeonhole principle]". In Jeff Miller (ed.) ''[http://jeff560.tripod.com/mathword.html Earliest Known Uses of Some of the Words of Mathematics]''. Electronic document, retrieved November 11, 2006</ref>

सिद्धांत के कई सामान्यीकरण हैं और इसे विभिन्न विधियों से कहा जा सकता है। अधिक परिमाणित संस्करण में: [[प्राकृतिक संख्या]] {{mvar|k}} और {{mvar|m}} के लिए, यदि {{math|1=''n'' = ''km'' + 1}}, वस्तु को {{mvar|m}} समुच्चय के मध्य वितरित किया जाता है, तो पिजनहोल सिद्धांत का आशय है कि समुच्चय में कम से कम {{math|''k'' + 1}} वस्तुएँ होंगी।<ref>{{harvnb|Fletcher|Patty|1987|loc=p. 27}}</ref> {{mvar|n}} और {{mvar|m}}, के लिए, यह <math>k + 1 = \lfloor(n - 1)/m \rfloor + 1 = \lceil n/m\rceil,</math> तक सामान्यीकृत होता है, जहाँ <math>\lfloor\cdots\rfloor</math> और <math>\lceil\cdots\rceil</math> क्रमशः [[फर्श का कार्य|फ़्लोर]] और सीलिंग फलन को दर्शाते हैं।

यद्यपि सबसे प्रत्यक्ष अनुप्रयोग [[परिमित सेट|परिमित समुच्चयों]] (जैसे पिजनहोल और बॉक्स) के लिए होता है, इसका उपयोग [[अनंत सेट|अपरिमित]] [[परिमित सेट|समुच्चयों]] के साथ भी किया जाता है जिन्हें पत्राचार में नहीं रखा जा सकता है। ऐसा करने के लिए पिजनहोल सिद्धांत के औपचारिक कथन की आवश्यकता होती है, जिसमें [[इंजेक्शन समारोह|इंजेक्शन फलन]] उपस्तिथ नहीं है जिसका [[कोडोमेन]] किसी फलन के डोमेन से छोटा होता है। सीगल के लेम्मा जैसे उन्नत गणितीय प्रमाण इस अधिक सामान्य अवधारणा पर आधारित हैं।

==व्युत्पत्ति==
[[Image:Pigeon-hole messagebox 3.jpg|thumb|[[स्टैनफोर्ड विश्वविद्यालय]] में पिजनहोल संदेशबॉक्स]]डिरिचलेट ने जर्मन {{lang|de|Schubfach}} अथवा फ़्रेंच {{lang|fr|[[wikt:tiroir|tiroir]]}} का उपयोग करते हुए फ्रेंच और जर्मन दोनों में अपने कार्य प्रकाशित किए। इन शब्दों का मूल अर्थ अंग्रेजी ड्रावर से युग्मित होता है, अर्थात, संवृत शीर्ष बॉक्स जिसे कैबिनेट के भीतर और बाहर स्लाइड किया जा सकता है (डिरिचलेट ने ड्रावर के मध्य मोती वितरित करने के सम्बन्ध में लिखा था)। इन शब्दों को डेस्क, कैबिनेट, अथवा दीवार में छोटी सी संवृत स्थान के अर्थ में [[कबूतर-छेद संदेशबॉक्स|पिजनहोल]] शब्द में रूपांतरित किया गया था, जो रूपक रूप से उन संरचनाओं में निहित है जहां कबूतर रहते हैं।

क्योंकि पिजनहोल वाले फर्नीचर का उपयोग सामान्यतः वस्तुओं को कई श्रेणियों में संग्रहित करने अथवा क्रमबद्ध करने के लिए किया जाता है (जैसे कि पोस्ट ऑफिस में पत्र अथवा होटल में कक्ष की कुंजियाँ), जिसका अनुवाद पिजनहोल डिरिचलेट के मूल ड्रावर रूपक का उत्तम प्रतिपादन हो सकता है। फर्नीचर की कुछ विशेषताओं को संदर्भित करते हुए पिजनहोल शब्द का अध्ययन कम हो रहा है- विशेष रूप से उन व्यक्तियों के मध्य जो मूल रूप से अंग्रेजी नहीं बोलते हैं, किन्तु अधिक सचित्र व्याख्या के पक्ष में वैज्ञानिक संसार में [[सामान्य भाषा]] के रूप में, जिसमें वस्तुतः कबूतर और बिल सम्मिलित हैं। "पिजनहोल" की "पिजन" के रूप में विचारोत्तेजक (यद्यपि भ्रामक नहीं) व्याख्या वर्तमान में पिजनहोल सिद्धांत के जर्मन बैक-अनुवाद में {{lang|de|Taubenschlagprinzip}} के रूप में पुनः आ गई है।<ref>{{cite book|page= 367|url=https://books.google.com/books?id=I-r1ywhuy0YC | title=गणित पृथक करें| isbn=9783833455292 | last1=Zimmermann | first1=Karl-Heinz | year=2006 }}</ref>

जर्मन में मूल शब्द {{lang|de|शुबफैचप्रिनज़िप}}<ref>{{cite book|page=13 |url=https://books.google.com/books?id=FculDgAAQBAJ | title=इंडक्शन बुक| isbn=9780486811994 | last1=Weintraub | first1=Steven H. | date=17 May 2017 }}</ref> और फ़्रेंच में {{lang|fr|प्रिंसिपे डेस टिरोइर्स}} के अतिरिक्त,<ref>{{cite book|page=490 |url=https://books.google.com/books?id=UyIfgBIwLMQC 
| title=गणित शब्दकोश| isbn=9780412990410 | last1=James | first1=R. C. | date=31 July 1992 }}</ref> अन्य शाब्दिक अनुवाद अभी भी [[अरबी भाषा]], [[बल्गेरियाई भाषा]], [[चीनी भाषा]], [[डेनिश भाषा]] ({{lang|da|Skuffeprincippet}} ), [[हॉलैंड की भाषा]] ({{lang|nl|ladenprincipe}} ), [[हंगेरियन भाषा]] ({{lang|hu|skatulyaelv}} ), [[इतालवी भाषा]] ({{lang|it|principio dei cassetti}} ), [[जापानी भाषा]], [[फ़ारसी भाषा]], [[पोलिश भाषा]] ({{lang|pl|zasada szufladkowa}} ), [[पुर्तगाली भाषा]] ({{lang|pt|Princípio das Gavetas}} ), [[स्वीडन की भाषा]] ({{lang|sv|Lådprincipen}} ), [[तुर्की भाषा]] ({{lang|tr|çekmece ilkesi}} ) और [[वियतनामी भाषा]] ({{lang|vi|nguyên lý hộp}}) में उपयोग में हैं।

== उदाहरण ==

=== सोक पीकिंग ===
मान लें कि ड्रावर में ब्लैक सॉक्स और नीले सॉक्स का मिश्रण है, जिनमें से प्रत्येक को किसी भी पैर पर पहना जा सकता है, और आप बिना देखे ड्रावर से कई सॉक्स निकाल रहे हैं। समान रंग के जोड़े के आश्वासन के लिए निकाले गए सॉक्स की न्यूनतम संख्या कितनी होनी चाहिए? पिजनहोल सिद्धांत {{math|(''m'' {{=}} 2}} सॉक्स, प्रति रंग पिजनहोल का उपयोग करके), का उपयोग करते हुए, आपको ड्रावर से केवल तीन सॉक्स {{math|(''n'' {{=}} 3}} आइटम) निकालने की आवश्यकता है। या तो आपके निकट समान रंग के तीन हैं, या आपके निकट समान रंग के दो हैं और दूसरे रंग का एक है।

=== हैण्ड शेकिंग ===
यदि ऐसे {{math|''n''}} व्यक्ति हैं जो एक दूसरे से हैण्ड शेक कर सकते हैं (जहां {{math|''n'' > 1}}), पिजनहोल सिद्धांत से ज्ञात होता है कि सदैव ऐसे व्यक्तियों का जोड़ा होता है जो समान संख्या में व्यक्तियों से हैण्ड शेक करते है। सिद्धांत के इस अनुप्रयोग में, जिस 'छिद्र' को व्यक्ति प्रदान किया गया है वह उस व्यक्ति द्वारा शेक हैण्ड की संख्या है। यद्यपि प्रत्येक व्यक्ति 0 से {{math|''n'' &minus; 1}} तक कुछ संख्या में व्यक्तियों से हैण्ड शेक करता है, इसलिए {{math|''n''}} संभावित छिद्र हैं। दूसरी ओर, या तो '0' छिद्र अथवा {{math|'''n'' &minus; 1'}} छिद्र अथवा दोनों रिक्त होने चाहिए, क्योंकि किसी व्यक्ति के लिए सभी के लिए हैण्ड शेक करना असंभव है (यदि {{math|''n'' > 1}}), जबकि कोई व्यक्ति किसी से हैण्ड शेक नहीं करता है। इससे {{math|''n''}} व्यक्तियों को अधिकतम {{math|''n'' &minus; 1}} अरिक्त छिद्रों में रखा जा सकता है, जिससे सिद्धांत प्रारम्भ हो।

हैण्ड शेकिंग का यह उदाहरण इस कथन के समतुल्य है कि अधिक [[वर्टेक्स (ग्राफ़ सिद्धांत)|शीर्षों (ग्राफ़ सिद्धांत)]] वाले किसी भी ग्राफ़ (भिन्न-भिन्न गणित) में, कम से कम एक जोड़ी शीर्षों की डिग्री समान होती है। इसे प्रत्येक व्यक्ति को शीर्ष के साथ और प्रत्येक शीर्ष को हैण्ड शेक के साथ संयोजित करके देखा जा सकता है।

===हेयर काउंटिंग ===
कोई यह प्रदर्शित कर सकता है कि [[लंडन|लंदन]] में कम से कम दो व्यक्ति ऐसे होने चाहिए जिनके शीर्ष पर समान संख्या में बाल हों।<ref>{{cite book|title=तर्क का मनोविज्ञान|first=Eugenio|last=Rignano|translator-first=Winifred A.|translator-last=Holl|publisher=K. Paul, Trench, Trubner & Company, Limited|year=1923|page=72|isbn=9780415191326 |url=https://books.google.com/books?id=1i9VAAAAMAAJ&pg=PA72}}</ref><ref>To avoid a slightly messier presentation, this example only refers to people who are not bald.</ref> यद्यपि सामान्य मानव शीर्ष पर [[औसत|औसतन]] लगभग 150,000 बाल होते हैं, इसलिए यह मान लेना उचित है (ऊपरी सीमा के रूप में) कि किसी के भी शीर्ष पर 1,000,000 से अधिक बाल {{math|(''m'' {{=}} 1 million}} होल्स) नहीं होते हैं। लंदन में 1,000,000 से अधिक व्यक्ति हैं ({{math|''n''}}, 1 मिलियन वस्तुओं से बड़ा है)। किसी व्यक्ति के शीर्ष पर प्रत्येक बाल की संख्या के लिए पिजनहोल का छिद्र आवंटित करना, और व्यक्तियों को उनके शीर्ष पर बालों की संख्या के अनुसार पिजनहोल का छिद्र प्रदान करना, 1,000,001 वें असाइनमेंट तक कम से कम दो व्यक्तियों को पिजनहोल का कार्य प्रदान किया जाना चाहिए (क्योंकि उनके शीर्ष पर बालों की संख्या समान है) (या, {{math|''n'' > ''m''}}) यह मानते हुए कि लंदन में 9.002 मिलियन व्यक्ति हैं,<ref>{{Cite web|url=http://data.london.gov.uk/dataset/londons-population|title=London's Population / Greater London Authority (GLA)|website=data.london.gov.uk}}</ref> कोई यह भी कह सकता है कि कम से कम दस लंदनवासियों के बालों की संख्या समान है, क्योंकि 10 लाख पिजनहोल में से प्रत्येक में नौ लंदनवासियों के बाल केवल 9 मिलियन होते हैं।

औसत स्तिथि के लिए ({{math|1=''m'' = 150,000}}) बाधा के साथ: सबसे कम ओवरलैप, प्रत्येक पिजनहोल के लिए अधिकतम व्यक्ति को नियुक्त किया जाएगा और 150,001वें व्यक्ति को किसी अन्य व्यक्ति के समान उसी पिजनहोल के लिए प्रदान किया जाएगा। इस बाधा के अभाव में, रिक्त पिजनहोल हो सकते हैं क्योंकि विखंडन 150,001वें व्यक्ति से पूर्व होता है। सिद्धांत केवल ओवरलैप के अस्तित्व को सिद्ध करता है; इसमें ओवरलैप्स की संख्या (जो प्रायिकता वितरण के अंतर्गत आती है) के सम्बन्ध में कुछ नहीं कहा गया है।

ए हिस्ट्री ऑफ द एथेनियन सोसाइटी में सिद्धांत के इस संस्करण के लिए अंग्रेजी में व्यंग्यपूर्ण संकेत है, जिसके उपसर्ग में "ए सप्लिमेंट टू द एथेनियन ओरेकल: बीइंग ए कलेक्शन ऑफ द रिमेनिंग क्वेश्चन एंड आंसर इन द ओल्ड एथेनियन मर्करीज" (एंड्रयू बेल, लंदन, 1710 के लिए मुद्रित) सम्मिलित है।<ref>{{Cite web|url=https://books.google.com/books?id=JCwUAAAAQAAJ&q=mean+hairs|title = A Supplement to the Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries. ... To which is Prefix'd the History of the Athenian Society, ... By a Member of the Athenian Society|year = 1710}}</ref> ऐसा लगता है कि यह प्रश्न कि क्या संसार में ऐसे भी दो व्यक्ति थे जिनके शीर्ष पर समान संख्या में बाल हों? 1704 से पूर्व एथेनियन मर्करी में किया गया था।<ref>{{Cite web|url=https://books.google.com/books?id=4QsUAAAAQAAJ&q=sent+quarters|title = एथेनियन ओरेकल सभी मूल्यवान प्रश्नों और उत्तरों का एक संपूर्ण संग्रह है|year = 1704}}</ref><ref>{{Cite web|url=https://books.google.com/books?id=GG0PAAAAQAAJ&q=town+eternity|title = The Athenian Oracle: Being an Entire Collection of All the Valuable Questions and Answers in the Old Athenian Mercuries. ... By a Member of the Athenian Society|year = 1704}}</ref>

संभवतः पिजनहोल सिद्धांत का प्रथम लिखित संदर्भ 1622 में फ्रांसीसी जेसुइट जीन लेउरेचोन द्वारा लिखित लैटिन कार्य सिलेक्ट प्रोपोजीशन के छोटे वाक्य में दिखाई देता है,<ref name="leurechon" /> जहां उन्होंने लिखा कि यह आवश्यक है कि दो पुरुषों के बाल, ईकस या अन्य वस्तुएँ एक-दूसरे के समान संख्या में हों।"<ref>{{citation|first=Jean|last=Leurechon|title=Selecæe Propositiones in Tota Sparsim Mathematica Pulcherrimæ|year=1622|publisher=Gasparem Bernardum|page=2}}</ref> पूर्ण सिद्धांत को दो वर्षों पश्चात, अतिरिक्त उदाहरणों के साथ, अन्य पुस्तक में वर्णित किया गया था, जिसका श्रेय प्रायः लेउरेचॉन को दिया गया है, किन्तु हो सकता है कि इसे उनके किसी छात्र ने लिखा हो।<ref name="leurechon" />

[[जन्मदिन की समस्या|'''जन्मदिन की समस्या''']]

जन्मदिन की समस्या समुच्चय के लिए पूछती है यादृच्छिक रूप से चयन किये गए {{math|''n''}} व्यक्तियों के समूह के लिए, क्या संभावना है कि उनमें से कुछ जोड़े का समान जन्मदिन होगा? समस्या स्वयं मुख्य रूप से प्रति-सहज ज्ञान युक्त संभावनाओं से संबंधित है; यद्यपि, हम पिजनहोल सिद्धांत द्वारा यह भी बता सकते हैं कि, यदि कक्ष में 367 व्यक्ति हैं, तो 100% संभावना के साथ कम से कम 1 जोड़ी व्यक्तियों का जन्मदिन समान है, क्योंकि चयन करने के लिए केवल 366 संभावित जन्मदिन हैं (29 फरवरी सहित, यदि उपस्तिथ हो)।

=== टीम टूर्नामेंट ===
सात व्यक्तियों की कल्पना करें जो टीमों {{math|(''n'' {{=}} 7}} आइटम), के टूर्नामेंट में खेलना चाहते हैं जिसमें से चयन के लिए केवल चार टीमों {{math|(''m'' {{=}} 4}} छिद्र) की सीमा है। पिजनहोल सिद्धांत हमें बताता है कि वे सभी भिन्न-भिन्न टीमों के लिए नहीं खेल सकते हैं; कम से कम 1 टीम में सात में से कम से कम दो खिलाड़ी होने चाहिए:
: <math display=block> \left\lfloor \frac{n-1}{m} \right\rfloor + 1 = \left\lfloor \frac{7-1}{4} \right\rfloor + 1 = \left\lfloor \frac64 \right\rfloor + 1 = 1 + 1 = 2 </math>

'''उपसमुच्चय योग'''

समुच्चय {{math|''S''}} = {1,2,3,...,9} से आकार छह के किसी भी उपसमुच्चय में दो तत्व होने चाहिए जिनका योग 10 है। पिजनहोल को दो तत्व उपसमुच्चय {1,9}, {2,8}, {3,7) {4,6} और सिंगलटन {5}, कुल मिलाकर पांच पिजनहोल द्वारा लेबल किया जाएगा। जब छह पिजनहोलों (आकार छह उपसमुच्चय के तत्व) को इन पिजनहोल में रखा जाता है, तो प्रत्येक कबूतर उस पिजनहोल में जाता है जिसके लेबल में यह समाहित होता है, दो-तत्व उपसमूह के साथ लेबल किए गए पिजनहोल में से कम से कम दो कबूतर होंगे।<ref>{{harvnb|Grimaldi|1994|page=277}}</ref>

== उपयोग और अनुप्रयोग ==
सिद्धांत का उपयोग यह सिद्ध करने के लिए किया जा सकता है कि कोई भी [[दोषरहित संपीड़न]] एल्गोरिथ्म, नियमानुसार कि यह कुछ इनपुट को छोटा बनाता है (जैसा कि नाम संपीड़न से ज्ञात होता है), कुछ अन्य इनपुट को भी बड़ा बना देगा। अन्यथा, किसी दी गई लंबाई {{mvar|L}} तक सभी इनपुट अनुक्रमों के समुच्चय को {{mvar|L}} से कम लंबाई के सभी अनुक्रमों के (अधिक) छोटे समुच्चय पर मैप किया जा सकता है (क्योंकि संपीड़न दोषरहित है), यह संभावना जिसे पिजनहोल सिद्धांत बाहर रखता है।

[[File:Dudeney_no_3_pawns_in_line.svg|thumb|पिजनहोल सिद्धांत [[नो-थ्री-इन-लाइन समस्या]] में उन बिंदुओं की संख्या के लिए {{math|2''n''}}  की ऊपरी सीमा देता है, जिन्हें {{math|''n'' &times; ''n''}} लैटिस पर बिना किसी तीन के कॉलिनियर के रखा जा सकता है-   इस प्रकार इस स्तिथि में, नियमित चेस्बोर्ड पर 16 प्यादे होते हैं।<ref>{{cite magazine
 | last = Gardner | first = Martin | author-link = Martin Gardner
 | date = October 1976
 | department = Mathematical Games
 | issue = 4
 | magazine = [[Scientific American]]
 | jstor = 24950467
 | pages = 131–137
 | title = Combinatorial problems, some old, some new and all newly attacked by computer
 | volume = 235}}</ref>]][[गणितीय विश्लेषण]] में उल्लेखनीय समस्या निश्चित [[अपरिमेय संख्या]] {{mvar|a}}, के लिए, यह दर्शाना है कि भिन्नात्मक भागों का समुच्चय <nowiki>{{tmath|\{[na]: n \in \Z \}}</nowiki> {{math|[0, 1]}} [[अपने आप में सघन|में सघन]] होता है। किसी को यह ज्ञात होता है कि पूर्णांक {{mvar|n, m}} को स्पष्ट रूप से अन्वेषित करना सरल नहीं है ऐसा है कि <math>|na-m| < e,</math> जहाँ {{math|''e'' > 0}}  छोटी धनात्मक संख्या है और {{mvar|a}} अपरिमेय संख्या है। किन्तु यदि कोई {{mvar|M}} को ऐसे लेता है कि {{tmath|\tfrac 1 M < e,}} पिजनहोल सिद्धांत के अनुसार <math>n_1, n_2 \in \{1, 2, \ldots, M+1\}</math> अवश्य होना चाहिए, जैसे कि {{math|''n''<sub>1</sub>''a''}} और {{math|''n''<sub>2</sub>''a''}} आकार {{tmath|\tfrac 1 M}} के समान पूर्णांक उपविभाजन में हैं (क्रमागत पूर्णांकों के मध्य {{mvar|M}} ऐसे उपविभाजन होते हैं)। विशेष रूप से, {{math|''n''<sub>1</sub>, ''n''<sub>2</sub>}} को इस प्रकार प्राप्त किया जा सकता है:
:<math>n_1 a \in \left(p+\frac k M,\ p + \frac{k+1}{M}\right), \quad n_2 a \in \left(q+ \frac k M,\ q+\frac{k+1}{M}\right),</math>
{{math|{0, 1, ..., ''M'' &minus; 1}}} में कुछ {{mvar|p, q}} पूर्णांकों और {{mvar|k}} के लिए, तब कोई भी इसे सरलता से सत्यापित कर सकता है:
:<math>(n_2 - n_1)a \in \left(q-p-\frac 1 M, q-p+\frac 1 M \right).</math>
इसका अर्थ यह है कि {{tmath|[na] < \tfrac 1 M < e,}} जहाँ {{math|1=''n'' = ''n''<sub>2</sub> &minus; ''n''<sub>1</sub>}} अथवा {{math|1=''n'' = ''n''<sub>1</sub> &minus; ''n''<sub>2</sub>}} है। इससे ज्ञात होता है कि 0, {[{{math|''na''}}]} का सीमा बिंदु है। तब कोई इस तथ्य का उपयोग {{math|(0, 1]}} में {{mvar|p}} की स्तिथि को सिद्ध करने के लिए कर सकता है: {{mvar|n}} को इस प्रकार अन्वेषित करें कि {{tmath|[na] < \tfrac 1 M < e;}} तो यदि {{tmath|p \in \bigl(0, \tfrac 1 M \bigr],}} है, तो प्रमाण पूर्ण है। अन्यथा
:<math>p \in \left(\frac j M, \frac{j+1}{M}\right],</math>
और समुच्चय द्वारा
:<math>k = \sup \left\{r \in N : r[na] < \frac j M \right\},</math>  प्राप्त होता है
:<math>\Bigl| \bigl[ (k+1)na \bigr] - p \Bigr| < \frac 1 M < e.</math>
अनेक प्रमाणों में भिन्नताएँ पाई जाती हैं। [[नियमित भाषाओं के लिए पंपिंग लेम्मा]] के प्रमाण में, संस्करण जो परिमित और अपरिमित समुच्चयों को मिश्रित करता है, यदि परिमित रूप से कई वस्तुओं को सीमित रूप से कई बॉक्स में रखा जाता है, तो दो वस्तुएं उपस्तिथ होती हैं जो बॉक्स की भागीदारी करती हैं।<ref>''Introduction to Formal Languages and Automata'', Peter Linz, pp.&nbsp;115–116, Jones and Bartlett Learning, 2006</ref> [[आर्ट गैलरी समस्या]] के फिस्क के समाधान में विशेष प्रकार का व्युत्क्रम प्रयोग किया जाता है: यदि {{mvar|n}} वस्तुओं को {{mvar|k}} बॉक्स में रखा जाता है, तो वहां बॉक्स होता है जिसमें अधिकतम {{tmath|\tfrac n k}} वस्तुएं होती है।<ref>''Computational Geometry in C'',  Cambridge Tracts in Theoretical Computer Science, 2nd Edition, Joseph O'Rourke, page 9.</ref>

== वैकल्पिक सूत्रीकरण ==
पिजनहोल सिद्धांत के वैकल्पिक सूत्रीकरण निम्नलिखित हैं।

#यदि {{math|''n''}} वस्तुएं {{math|''m''}} स्थानों पर वितरित की जाती हैं, और यदि {{math|''n'' > ''m''}}, तो किसी स्थान को कम से कम दो वस्तुएँ प्राप्त होती हैं।<ref name=Herstein64 />
#(1 के समतुल्य सूत्रीकरण) यदि {{math|''n''}} को {{math|''n''}} स्थानों पर इस प्रकार वितरित किया जाता है कि किसी भी स्थान को अधिक वस्तुएँ प्राप्त नहीं होती हैं, तो प्रत्येक स्थान को 1 वस्तु प्राप्त होती है।<ref name="Herstein64" />
#यदि {{math|''n''}} वस्तुओं को {{math|''m''}} स्थानों पर वितरित किया जाता है, और यदि {{math|''n'' < ''m''}}, तो किसी स्थान को कोई वस्तु नहीं मिलती है।
#(3 के समतुल्य सूत्रीकरण) यदि {{math|''n''}} वस्तुओं को {{math|''n''}} स्थानों पर इस प्रकार वितरित किया जाता है कि किसी भी स्थान को कोई वस्तु प्राप्त नहीं होती है, तो प्रत्येक स्थान को 1 वस्तु प्राप्त होती है।<ref>{{harvnb|Brualdi|2010|page=70}}</ref>

== स्थिर रूप ==
मान लीजिये {{math|''q''<sub>1</sub>, ''q''<sub>2</sub>, ..., ''q''<sub>''n''</sub>}} धनात्मक पूर्णांक हैं। यदि
:<math>q_1 + q_2 + \cdots + q_n - n + 1</math>
वस्तु को {{math|''n''}} बॉक्स में वितरित किया जाता है, तत्पश्चात या तो प्रथम बॉक्स में कम से कम {{math|''q''<sub>1</sub>}} वस्तु होती हैं, अथवा द्वितीय बॉक्स में कम से कम {{math|''q''<sub>2</sub>}} वस्तु होती हैं, ..., या nवें बॉक्स में कम से कम {{math|''q''<sub>''n''</sub>}} वस्तुएँ होती हैं।<ref>{{harvnb|Brualdi|2010|page=74 Theorem 3.2.1}}</ref>

इससे {{math|1=''q''<sub>1</sub> = ''q''<sub>2</sub> = ... = ''q''<sub>''n''</sub> = 2}}, लेकर सरल रूप प्राप्त किया जाता है, जिससे {{math|''n'' + 1}} वस्तुएं प्राप्त होती हैं। {{math|1=''q''<sub>1</sub> = ''q''<sub>2</sub> = ... = ''q''<sub>''n''</sub> = ''r''}} लेने से सिद्धांत का अधिक मात्रात्मक संस्करण प्राप्त होता है, अर्थात्:

मान लीजिए {{math|''n''}} और {{math|''r''}} धनात्मक पूर्णांक हैं। यदि {{math|''n''(''r'' - 1) + 1}} वस्तु को {{math|''n''}} बॉक्स में वितरित किया जाता है, तो कम से कम बॉक्स में {{math|''r''}} अथवा अधिक वस्तुएँ होती हैं।<ref>In the lead section this was presented with the substitutions {{math|1=''m'' = ''n''}} and {{math|1=''k'' = ''r'' − 1}}.</ref>

इसे इस प्रकार भी कहा जा सकता है, यदि {{math|''k''}} असतत वस्तुओं को {{math|''n''}} कंटेनरों को आवंटित किया जाना है तो कम से कम कंटेनर में <math>\lceil k/n \rceil</math> वस्तु होनी चाहिए, जहां <math>\lceil x\rceil</math> सीलिंग फलन है, जो {{math|''x''}} से बड़ा अथवा उसके समान सबसे छोटे पूर्णांक को दर्शाता है। इसी प्रकार, कम से कम कंटेनर में <math>\lfloor k/n \rfloor</math> से अधिक वस्तु नहीं होनी चाहिए, जहां <math>\lfloor x \rfloor</math> फ़्लोर फलन है, जो {{math|''x''}} से छोटे अथवा उसके समान सबसे बड़े पूर्णांक को दर्शाता है।

== पिजनहोल सिद्धांत का सामान्यीकरण ==

पिजनहोल सिद्धांत का संभाव्य सामान्यीकरण बताता है कि यदि {{math|''n''}} कबूतरों को समान संभावना {{math|1/''m''}} के साथ {{math|''m''}} पिजनहोल में यादृच्छिक रूप से रखा जाता है, तो कम से कम पिजनहोल में प्रायिकता वाले 1 से अधिक कबूतर होंगे।

:<math>1 - \frac{(m)_n}{m^n}, </math>
जहाँ {{math|(''m'')<sub>''n''</sub>}} [[गिरता हुआ भाज्य|न्यूतम भाज्य]] {{math|''m''(''m'' &minus; 1)(''m'' &minus; 2)...(''m'' &minus; ''n'' + 1)}} है। {{math|1=''n'' = 0}} के लिए और {{math|1=''n'' = 1}} (और {{math|''m'' > 0}}), के लिए, वह संभावना शून्य है; दूसरे शब्दों में, यदि केवल 1 कबूतर है, तो कोई संघर्ष नहीं हो सकता। {{math|''n'' > ''m''}} (पिजनहोल के छिद्र से अधिक कबूतर) के लिए यह है, इस स्तिथि में यह सामान्य पिजनहोल के सिद्धांत से युग्मित होता है। यदि कबूतरों की संख्या पिजनहोल की संख्या ({{math|''n'' ≤ ''m''}}) से अधिक न हो, किन्तु पिजनहोल में पिजन को नियुक्त करने की यादृच्छिक प्रकृति के कारण प्रायः होने की पर्याप्त संभावना होती है। उदाहरण के लिए, यदि 2 कबूतरों को अव्यवस्थित रूप से 4 पिजनहोल प्रदान किये गए है, तो 25% संभावना है कि कम से कम 1 पिजनहोल में अधिक कबूतर होंगे; 5 कबूतरों और 10 छिद्रों के लिए, यह संभावना 69.76% है; और 10 कबूतरों और 20 छिद्रों के लिए यह लगभग 93.45% है। यदि छिद्रों की संख्या निश्चित रहती है, तो अधिक पिजनहोल जोड़ने पर जोड़े की संभावना सदैव अधिक होती है। [[जन्मदिन विरोधाभास]] में इस समस्या का अधिक विस्तार से समाधान किया जाता है।

संभाव्य सामान्यीकरण यह है कि जब वास्तविक-मान वाले यादृच्छिक चर {{math|''X''}} का सीमित माध्य {{math|''E''(''X'')}} है, तो संभावना शून्य नहीं होती है कि यह देखने के लिए कि यह मानक पिजनहोल सिद्धांत का तात्पर्य है, n कबूतरों की किसी भी निश्चित व्यवस्था को m होल में लें और {{math|''X''}} को यादृच्छिक रूप से समान रूप से चयन किये गए होल में पिजनहोल की संख्या दें। {{math|''X''}} का माध्य {{math|''n''/''m''}} है, इसलिए यदि छिद्रों से अधिक कबूतर हैं तो माध्य 1 से अधिक है। इसलिए, {{math|''X''}}  कभी-कभी कम से कम 2 होता है। 

== अपरिमित समुच्चय ==
पिजनहोल सिद्धांत को कार्डिनल संख्याओं के संदर्भ में वाक्यांशित करके अपरिमित समुच्चयों तक विस्तारित किया जा सकता है: यदि समुच्चय {{mvar|A}} की कार्डिनैलिटी समुच्चय {{mvar|B}} की कार्डिनैलिटी से अधिक है, तो {{mvar|A}} से {{mvar|B}} तक कोई इंजेक्शन नहीं है। यद्यपि, इस रूप में सिद्धांत [[टॉटोलॉजी (तर्क)]] है, क्योंकि कथन का अर्थ यह है कि समुच्चय {{mvar|A}} की कार्डिनैलिटी समुच्चय {{mvar|B}} की कार्डिनैलिटी से अधिक है, {{mvar|A}} से {{mvar|B}}  तक कोई इंजेक्टिव मैप नहीं है। यद्यपि, सीमित समुच्चय में कम से कम 1 तत्व जोड़ना यह सुनिश्चित करने के लिए पर्याप्त है कि कार्डिनैलिटी में वृद्धि होती है।

परिमित समुच्चयों के लिए पिजनहोल सिद्धांत को वाक्यांशबद्ध करने की दूसरी विधि इस सिद्धांत के समान है कि परिमित समुच्चय [[डेडेकाइंड परिमित]] हैं: मान लीजिए कि {{mvar|A}} और {{mvar|B}} परिमित समुच्चय हैं। यदि {{mvar|A}} से {{mvar|B}} तक कोई प्रक्षेप है जो कि निक्षेपण नहीं है, तो {{mvar|A}} से {{mvar|B}} तक कोई भी प्रक्षेप निक्षेपण नहीं है। वस्तुतः {{mvar|A}} से {{mvar|B}} तक किसी भी प्रकार का कोई भी फलन क्रियावाचक नहीं है। यह अपरिमित समुच्चयों के लिए सत्य नहीं है: प्राकृतिक संख्याओं के फलन पर विचार करें जो 1 और 2 को 1, 3 और 4 से 2, 5 और 6 को 3 भेजता है।

अपरिमित समुच्चयों के लिए समान सिद्धांत है: यदि अनगिनत कबूतरों को अनगिनत पिजनहोलों में रख दिया जाता है, तो कम से कम 1 पिजनहोल में अनगिनत कबूतरों को रखा जाएगा।

यद्यपि, यह सिद्धांत परिमित समुच्चयों के लिए पिजनहोल सिद्धांत का सामान्यीकरण नहीं है: यह परिमित समुच्चयों के लिए सामान्य रूप से त्रुटिपूर्ण है। तकनीकी शब्दों में यह कहता है कि यदि {{mvar|A}} और {{mvar|B}} परिमित समुच्चय हैं जैसे कि {{mvar|A}} से {{mvar|B}} तक कोई विशेषण फलन इंजेक्शन नहीं है, तो {{mvar|b}} का {{mvar|B}} तत्व उपस्तिथ है जैसे कि {{mvar|b}} और {{mvar|A}} की प्रीइमेज के मध्य पूर्वाग्रह उपस्थित है। यह भिन्न कथन है, और बड़ी परिमित कार्डिनैलिटी के लिए निरर्थक है।

==[[क्वांटम यांत्रिकी]]==
[[याकिर अहरोनोव]] एट अल तर्क प्रस्तुत किए हैं कि क्वांटम यांत्रिकी में पिजनहोल सिद्धांत का उल्लंघन किया जा सकता है, और क्वांटम यांत्रिकी में पिजनहोल सिद्धांत का परीक्षण करने के लिए [[इंटरफेरोमेट्री]] प्रयोगों का प्रस्ताव रखा गया है।<ref>{{Cite journal | doi=10.1073/pnas.1522411112| pmid=26729862| pmc=4725468|title = पिजनहोल सिद्धांत का क्वांटम उल्लंघन और क्वांटम सहसंबंधों की प्रकृति| journal=Proceedings of the National Academy of Sciences| volume=113| issue=3| pages=532–535|year = 2016|last1 = Aharonov|first1 = Yakir| last2=Colombo| first2=Fabrizio| last3=Popescu| first3=Sandu| last4=Sabadini| first4=Irene|author4-link=Irene Sabadini| last5=Struppa| first5=Daniele C.| last6=Tollaksen| first6=Jeff| bibcode=2016PNAS..113..532A| doi-access=free}}</ref> यद्यपि, पश्चात के शोध ने इस निष्कर्ष पर प्रश्न चिह्न लगा दिया है।<ref>{{Cite web | url=https://physicsworld.com/a/quantum-pigeonholes-are-not-paradoxical-after-all-say-physicists/ |title = भौतिकविदों का कहना है कि क्वांटम कबूतर-छिद्र आख़िरकार विरोधाभासी नहीं हैं|date = 8 January 2015}}</ref><ref name="Rae Forgan 2014">{{cite arXiv | last1=Rae | first1=Alastair | last2=Forgan | first2=Ted | title=क्वांटम-पिजनहोल प्रभाव के निहितार्थ पर| date=2014-12-03 | class=quant-ph | eprint=1412.1333 }}</ref> जनवरी 2015 के arXiv प्रीप्रिंट में, बर्मिंघम विश्वविद्यालय के शोधकर्ताओं एलेस्टेयर राय और टेड फोर्गन ने [[इंटरफेरोमीटर]] के माध्यम से विभिन्न ऊर्जाओं पर इलेक्ट्रॉनों की उड़ान पर मानक पिजनहोल सिद्धांत को नियोजित करते हुए सैद्धांतिक तरंग फलन विश्लेषण किया। यदि इलेक्ट्रॉनों में परस्पर क्रिया शक्ति नहीं होती, तो वे प्रत्येक एकल, पूर्णतः वृत्ताकार शिखर उत्पन्न करते है। उच्च अंतःक्रिया शक्ति पर, प्रत्येक इलेक्ट्रॉन डिटेक्टर पर कुल 12 शिखरों के लिए चार भिन्न-भिन्न शिखरों को उत्पन्न करता है; ये शिखर चार संभावित अंतःक्रियाओं का परिणाम हैं जिन्हें प्रत्येक इलेक्ट्रॉन (केवल प्रथम अन्य कण के साथ, केवल दूसरे अन्य कण के साथ, अथवा तीनों के साथ) अनुभव कर सकता है। यदि अंतःक्रिया की स्थिरता कम थी, जैसा कि कई वास्तविक प्रयोगों में होता है, तो शून्य-अंतःक्रिया प्रारूप से विचलन लगभग अदृश्य होगा, जो ठोस पदार्थों में परमाणुओं के लैटिस अंतर से अधिक छोटा होगा, जैसे कि इन प्रारूप को देखने के लिए उपयोग किए जाने वाले डिटेक्टर इससे स्थिर किन्तु अशून्य अंतःक्रिया शक्ति को बिना किसी अंतःक्रिया से भिन्न करना अधिक कठिन या असंभव हो जाएगा, और इस प्रकार तीन इलेक्ट्रॉनों का भ्रम उत्पन्न होगा जो तीनों के दो पथों से निकलने के अतिरिक्त परस्पर क्रिया नहीं करते हैं।

== यह भी देखें ==
* [[पसंद का सिद्धांत|एक्सिओम का सिद्धांत]]
* ब्लिचफेल्ट का प्रमेय
* [[संयुक्त सिद्धांत]]
* [[संयुक्त प्रमाण]]
* डेडेकाइंड-अपरिमित समुच्चय
* डिरिचलेट का सन्निकटन प्रमेय
* हिल्बर्ट का ग्रैंड होटल का विरोधाभास
* [[बहुपद प्रमेय]]
* पोचहैमर प्रतीक
* रैमसे का प्रमेय

==टिप्पणियाँ==
{{reflist}}


== संदर्भ ==
* {{citation|first=Richard A.|last=Brualdi|title=Introductory Combinatorics|edition=5th|year=2010|publisher=Pentice Hall|isbn=978-0-13-602040-0}}
* {{citation|first1=Peter|last1=Fletcher|first2=C.Wayne|last2=Patty|title=Foundations of Higher Mathematics|year=1987|publisher=PWS-Kent|isbn=978-0-87150-164-6}}
* {{citation|first=Ralph P.|last=Grimaldi|author-link=Ralph Grimaldi|title=Discrete and Combinatorial Mathematics: An Applied Introduction|edition=3rd|year=1994|publisher=Addison-Wesley|isbn=978-0-201-54983-6|url-access=registration|url=https://archive.org/details/discretecombinat00grim_1}}
* {{ citation | first1 = I. N. | last1 = Herstein | year = 1964 | isbn = 978-1114541016 | title = Topics In Algebra | publisher = Blaisdell Publishing Company | location = Waltham }}


== बाहरी संबंध ==
{{Spoken Wikipedia|date=2021-06-05|En-Pigeonhole_principle-article.ogg}}
* {{springer|title=Dirichlet box principle|id=p/d032800}}
* "[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD980.html The strange case of The Pigeon-hole Principle]"; [[Edsger Dijkstra]] investigates interpretations and reformulations of the principle.
* "[http://zimmer.csufresno.edu/~larryc/proofs/proofs.pigeonhole.html The Pigeon Hole Principle]"; Elementary examples of the principle in use by Larry Cusick.
* "[http://www.cut-the-knot.org/do_you_know/pigeon.shtml Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles]"; basic Pigeonhole Principle analysis and examples by [[Alexander Bogomolny]].
* "[http://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle 16 fun applications of the pigeonhole principle]"; Interesting facts derived by the principle.
* {{cite web |title=How Many Humans Have the Same Number of Body Hairs? |work=[[PBS Infinite Series]] |date=December 1, 2016 |url=https://www.youtube.com/watch?v=HMpSKjK9clA | archive-url=https://ghostarchive.org/varchive/youtube/20211211/HMpSKjK9clA| archive-date=2021-12-11 | url-status=live|via=[[YouTube]] }}{{cbignore}}

{{DEFAULTSORT:Pigeonhole Principle}}

[[Category:Articles containing Danish-language text|Pigeonhole Principle]]
[[Category:Articles containing Dutch-language text|Pigeonhole Principle]]
[[Category:Articles containing French-language text|Pigeonhole Principle]]
[[Category:Articles containing German-language text|Pigeonhole Principle]]
[[Category:Articles containing Hungarian-language text|Pigeonhole Principle]]
[[Category:Articles containing Italian-language text|Pigeonhole Principle]]
[[Category:Articles containing Polish-language text|Pigeonhole Principle]]
[[Category:Articles containing Portuguese-language text|Pigeonhole Principle]]
[[Category:Articles containing Swedish-language text|Pigeonhole Principle]]
[[Category:Articles containing Turkish-language text|Pigeonhole Principle]]
[[Category:Articles containing Vietnamese-language text|Pigeonhole Principle]]
[[Category:Articles with hAudio microformats|Pigeonhole Principle]]
[[Category:Citation Style 1 templates|M]]
[[Category:Collapse templates]]
[[Category:Created On 20/07/2023|Pigeonhole Principle]]
[[Category:Lua-based templates|Pigeonhole Principle]]
[[Category:Machine Translated Page|Pigeonhole Principle]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors|Pigeonhole Principle]]
[[Category:Short description with empty Wikidata description|Pigeonhole Principle]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Spoken articles|Pigeonhole Principle]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready|Pigeonhole Principle]]
[[Category:Templates based on the Citation/CS1 Lua module]]
[[Category:Templates generating COinS|Cite magazine]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category|Pigeonhole Principle]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions|Pigeonhole Principle]]
[[Category:Templates using TemplateData|Pigeonhole Principle]]
[[Category:Wikipedia fully protected templates|Cite magazine]]
[[Category:Wikipedia metatemplates]]
[[Category:असतत गणित में प्रमेय|Pigeonhole Principle]]
[[Category:गणितीय सिद्धांत|Pigeonhole Principle]]
[[Category:रैमसे सिद्धांत|Pigeonhole Principle]]
[[Category:साहचर्य|Pigeonhole Principle]]