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

छिद्रों में पिजनहोल. यहाँ वहाँ हैं n = 10 पिजनहोल अंदर m = 9 छिद्र. चूँकि 10, 9 से बड़ा है, पिजनहोल सिद्धांत कहता है कि कम से कम होल में से अधिक पिजनहोल हैं। (ऊपरी बाएँ छिद्र में 2 पिजनहोल हैं।)

गणित में, पिजनहोल सिद्धांत कहता है कि यदि n आइटम को n > m के साथ m कंटेनर में रखा जाता है, तो कम से कम कंटेनर में अधिक आइटम होने चाहिए। उदाहरण के लिए, यदि किसी के पास तीन ग्लव्स हैं (और उनमें से कोई भी उभयलिंगी/प्रतिवर्ती नहीं है), तो कम से कम दो दाएं हाथ के ग्लव्स होने चाहिए, या कम से कम दो बाएं हाथ के ग्लव्स होने चाहिए, क्योंकि तीन वस्तुएं हैं, किन्तु हाथ की केवल दो श्रेणियां हैं यह प्रतीत होता है कि स्पष्ट कथन, प्रकार का गिनती तर्क, संभवतः अप्रत्याशित परिणामों को प्रदर्शित करने के लिए उपयोग किया जा सकता है। उदाहरण के लिए, यह देखते हुए कि लंदन की जनसांख्यिकी किसी इंसान के सिर पर उपस्तिथ बालों की अधिकतम संख्या से अधिक है, तो पिजनहोल सिद्धांत के अनुसार लंदन में कम से कम दो लोग ऐसे होने चाहिए जिनके सिर पर बालों की संख्या समान हो। .

चूँकि पिजनहोल सिद्धांत 1624 में जीन लेउरेचॉन की पुस्तक में दिखाई देता है, इसे सामान्यतः पीटर गुस्ताव लेज्यून डिरिचलेट द्वारा Schubfachprinzip ("ड्रावर सिद्धांत" या "शेल्फ सिद्धांत") नाम के अंतर्गत सिद्धांत के 1834 के उपचार के पश्चात डिरिचलेट का बॉक्स सिद्धांत या डिरिचलेट का ड्रावर सिद्धांत कहा जाता है।।

सिद्धांत के कई सामान्यीकरण हैं और इसे विभिन्न विधियों से कहा जा सकता है। अधिक परिमाणित संस्करण में: प्राकृतिक संख्या k और m के लिए, यदि n = km + 1 ऑब्जेक्ट को m समुच्चय के मध्य वितरित किया जाता है, तो पिजनहोल सिद्धांत का आशय है कि समुच्चय में से कम से कम k + 1 ऑब्जेक्ट होंगे। n और m, के लिए, यह सामान्यीकृत होता है$k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil ,$ जहाँ $\lfloor \cdots \rfloor$ और $\lceil \cdots \rceil$ क्रमशः फर्श और छत फलन को निरूपित करते है।

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

व्युत्पत्ति

स्टैनफोर्ड विश्वविद्यालय में पिजनहोल-छिद्र संदेशबॉक्स

डिरिचलेट ने जर्मन Schubfach या फ़्रेंच tiroir का उपयोग करते हुए फ्रेंच और जर्मन दोनों में अपने कार्य प्रकाशित किए। इन शब्दों का कठिन मूल अर्थ अंग्रेजी ड्रावर से युग्मित होता है, अर्थात, संवृत शीर्ष बॉक्स जिसे कैबिनेट के अंदर और बाहर स्लाइड किया जा सकता है। (डिरिचलेट ने ड्रावर के मध्य मोती बांटने के बारे में लिखा था।) इन शब्दों को डेस्क, कैबिनेट, या दीवार में पत्र या कागजात रखने के लिए छोटी सी संवृत स्थान के अर्थ में पिजनहोल शब्द में रूपांतरित किया गया था, जो रूपक रूप से उन संरचनाओं में निहित है जहां पिजनहोल रहते हैं।

क्योंकि पिजनहोल वाले फर्नीचर का उपयोग सामान्यतः चीजों को कई श्रेणियों में संग्रहित करने या क्रमबद्ध करने के लिए किया जाता है (जैसे कि पोस्ट ऑफिस में पत्र या होटल में कक्ष की चाबियाँ), अनुवाद पिजनहोल डिरिचलेट के मूल ड्रावर रूपक का उत्तम प्रतिपादन हो सकता है। फर्नीचर की कुछ विशेषताओं को संदर्भित करते हुए पिजनहोल शब्द की समझ कम हो रही है- विशेष रूप से उन लोगों के मध्य जो मूल रूप से अंग्रेजी नहीं बोलते हैं, किन्तु वैज्ञानिक संसार में सामान्य भाषा के रूप में अधिक सचित्र व्याख्या के पक्ष में, जिसमें वस्तुतः पिजनहोल और छिद्र सम्मिलित हैं। "पिजन के छिद्र" की "पिजन" के रूप में विचारोत्तेजक (चूँकि भ्रामक नहीं) व्याख्या वर्तमान में पिजनहोल सिद्धांत के जर्मन बैक-अनुवाद में वापस आ गई है।Taubenschlagprinzip . मूल शर्तों के अलावाSchubfachprinzip जर्मन में औरPrincipe des tiroirs फ्रेंच में, अन्य शाब्दिक अनुवाद अभी भी अरबी भाषा में उपयोग में हैं, बल्गेरियाई भाषा, चीनी भाषा, डेनिश भाषा (Skuffeprincippet ), हॉलैंड की भाषा (ladenprincipe ), हंगेरियन भाषा (skatulyaelv ), इतालवी भाषा (principio dei cassetti ), जापानी भाषा, फ़ारसी भाषा, पोलिश भाषा (zasada szufladkowa ), पुर्तगाली भाषा (Princípio das Gavetas ), स्वीडन की भाषा (Lådprincipen ), तुर्की भाषा (çekmece ilkesi ) और वियतनामी भाषा (nguyên lý hộp ).

उदाहरण

सोक पीकिंग

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

हैण्ड शेकिंग

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

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

हेयर काउंटिंग

कोई यह प्रदर्शित कर सकता है कि लंदन में कम से कम दो लोग ऐसे होने चाहिए जिनके सिर पर समान संख्या में हेयर हों। चूँकि सामान्य मानव सिर पर औसतन लगभग 150,000 हेयर होते हैं, इसलिए यह मान लेना उचित है (ऊपरी सीमा के रूप में) कि किसी के भी सिर पर 1,000,000 से अधिक हेयर नहीं होते हैं। (m = 1 million छिद्र) लंदन में 1,000,000 से अधिक लोग हैं (n 1 मिलियन वस्तुओं से बड़ा है)। किसी व्यक्ति के सिर पर प्रत्येक हेयर की संख्या के लिए पिजनहोल का छिद्र आवंटित करना, और लोगों को उनके सिर पर बालों की संख्या के अनुसार पिजनहोल का छिद्र प्रदान करना, 1,000,001 वें असाइनमेंट तक कम से कम दो लोगों को पिजनहोल का कार्य प्रदान करना जाना चाहिए (क्योंकि उनके सिर पर बालों की संख्या समान है) (या, n > m) यह मानते हुए कि लंदन में 9.002 मिलियन लोग हैं, कोई यह भी कह सकता है कि कम से कम दस लंदनवासियों के बालों की संख्या समान है, क्योंकि 10 लाख पिजनहोल में से प्रत्येक में नौ लंदनवासियों के बाल केवल 9 मिलियन होते हैं।

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

ए हिस्ट्री ऑफ द एथेनियन सोसाइटी में सिद्धांत के इस संस्करण के लिए अंग्रेजी में व्यंग्यपूर्ण संकेत है, जिसके उपसर्ग में "ए सप्लिमेंट टू द एथेनियन ओरेकल: बीइंग ए कलेक्शन ऑफ द रिमेनिंग क्वेश्चन एंड आंसर इन द ओल्ड एथेनियन मर्करीज" (एंड्रयू बेल, लंदन, 1710 के लिए मुद्रित) सम्मिलित है। सवाल यह उठता है कि क्या संसार में ऐसे भी दो व्यक्ति थे जिनके सिर पर समान संख्या में बाल हों? 1704 से पहले एथेनियन मर्करी में पाला गया था।

संभवतः पिजनहोल सिद्धांत का प्रथम लिखित संदर्भ 1622 में फ्रांसीसी जेसुइट जीन लेउरेचोन द्वारा लिखित लैटिन कार्य सिलेक्ट प्रोपोजीशन के छोटे वाक्य में दिखाई देता है,जहां उन्होंने लिखा कि यह आवश्यक है कि दो पुरुषों के बाल, ईकस या अन्य चीजें एक-दूसरे के समान संख्या में हों।" पूर्ण सिद्धांत को दो वर्षों पश्चात, अतिरिक्त उदाहरणों के साथ, अन्य पुस्तक में वर्णित किया गया था, जिसका श्रेय प्रायः लेउरेचॉन को दिया गया है, किन्तु हो सकता है कि इसे उनके किसी छात्र ने लिखा हो।

जन्मदिन की समस्या

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

टीम टूर्नामेंट

सात लोगों की कल्पना करें जो टीमों (n = 7 आइटम), के टूर्नामेंट में खेलना चाहते हैं जिसमें से चयन के लिए केवल चार टीमों (m = 4 छिद्र) की सीमा है। पिजनहोल सिद्धांत हमें बताता है कि वे सभी भिन्न-भिन्न टीमों के लिए नहीं खेल सकते हैं; कम से कम टीम में सात में से कम से कम दो खिलाड़ी होने चाहिए:

$$\left\lfloor {\frac {n-1}{m}}\right\rfloor +1=\left\lfloor {\frac {7-1}{4}}\right\rfloor +1=\left\lfloor {\frac {6}{4}}\right\rfloor +1=1+1=2$$

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

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

उपयोग और अनुप्रयोग

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

पिजनहोल सिद्धांत ऊपरी सीमा देता है 2n नो-थ्री-इन-लाइन समस्या में उन बिंदुओं की संख्या के लिए जिन्हें पर रखा जा सकता है n × n बिना किसी तीन के रेखीय जाली - इस मामले में, नियमित शतरंज की बिसात पर 16 प्यादे

गणितीय विश्लेषण में उल्लेखनीय समस्या निश्चित अपरिमेय संख्या a, के लिए, यह दर्शाना है कि समुच्चय {{tmath|\{[na]: n \in \Z \} }भिन्नात्मक भागों का} [0, 1] में सघन होता है। कोई यह प्राप्त करता है कि पूर्णांक n, m को स्पष्ट रूप से परिक्षण करना सरल' नहीं है ऐसा है कि $|na-m|<e,$ जहाँ e > 0 छोटी धनात्मक संख्या है और a अपरिमेय संख्या है। किन्तु यदि कोई M को ऐसे लेता है ${\tfrac {1}{M}}<e,$ पिजनहोल सिद्धांत के अनुसार अवश्य होना चाहिए $n_{1},n_{2}\in \{1,2,\ldots ,M+1\}$ जैसे कि n₁a और n₂a आकार के एक ही पूर्णांक उपखंड में हैं ${\tfrac {1}{M}}$ (क्रमागत पूर्णांकों के M ऐसे उपविभाजन होते हैं)। विशेष रूप से, n₁, n₂ ऐसे पा सकता है:

$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),$

{0, 1, ..., M − 1} में कुछ p, q पूर्णांकों और k के लिए फिर कोई भी इसे सरलता से सत्यापित कर सकता है:

$(n_{2}-n_{1})a\in \left(q-p-{\frac {1}{M}},q-p+{\frac {1}{M}}\right).$

इसका अर्थ यह है कि $[na]<{\tfrac {1}{M}}<e,$ जहाँ n = n₂ − n₁ या n = n₁ − n₂ इससे ज्ञात होता है कि 0 {[na]} का सीमा बिंदु है। फिर कोई इस तथ्य का उपयोग (0, 1] में p की स्तिथि को सिद्ध करने के लिए कर सकता है: n ऐसा है कि $[na]<{\tfrac {1}{M}}<e;$ तो यदि $p\in {\bigl (}0,{\tfrac {1}{M}}{\bigr ]},$ प्रमाण पूर्ण है। अन्यथा

$p\in \left({\frac {j}{M}},{\frac {j+1}{M}}\right],$

और समुच्चय द्वारा

$k=\sup \left\{r\in N:r[na]<{\frac {j}{M}}\right\},$ प्राप्त होता है

${\Bigl |}{\bigl [}(k+1)na{\bigr ]}-p{\Bigr |}<{\frac {1}{M}}<e.$

अनेक प्रमाणों में भिन्नताएँ पाई जाती हैं। नियमित भाषाओं के लिए पंपिंग लेम्मा के प्रमाण में, संस्करण जो परिमित और अनंत समुच्चयों को मिश्रित करता है, यदि अनंत रूप से कई वस्तुओं को सीमित रूप से कई बक्से में रखा जाता है, तो दो वस्तुएं उपस्तिथ होती हैं जो बॉक्स को भागित करती हैं।आर्ट गैलरी समस्या के फिस्क के समाधान में विशेष प्रकार का व्युत्क्रम प्रयोग किया जाता है: यदि n वस्तुओं को k बक्से में रखा जाता है, तो वहां बॉक्स होता है जिसमें अधिकतम ${\tfrac {n}{k}}$ वस्तुएं होती है।

वैकल्पिक सूत्रीकरण

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

1. यदि n वस्तुएं m स्थानों पर वितरित की जाती हैं, और यदि n > m, तो किसी स्थान को कम से कम दो वस्तुएँ प्राप्त होती हैं।
2. (1 के समतुल्य सूत्रीकरण) यदि n को n स्थानों पर इस प्रकार वितरित किया जाता है कि किसी भी स्थान को एक से अधिक वस्तुएँ प्राप्त नहीं होती हैं, तो प्रत्येक स्थान को वस्तु प्राप्त होती है।
3. यदि n वस्तुओं को m स्थानों पर वितरित किया जाता है, और यदि n < m, तो किसी स्थान को कोई वस्तु नहीं मिलती है।
4. (3 के समतुल्य सूत्रीकरण) यदि n वस्तुओं को n स्थानों पर इस प्रकार वितरित किया जाता है कि किसी भी स्थान को कोई वस्तु प्राप्त नहीं होती है, तो प्रत्येक स्थान को वस्तु प्राप्त होती है।

स्थिर रूप

मान लीजिये q₁, q₂, ..., q_n धनात्मक पूर्णांक हैं। यदि

$q_{1}+q_{2}+\cdots +q_{n}-n+1$

ऑब्जेक्ट को n बॉक्स में वितरित किया जाता है, फिर या तो पहले बॉक्स में कम से कम q₁ ऑब्जेक्ट होते हैं, या दूसरे बॉक्स में कम से कम q₂ ऑब्जेक्ट होते हैं, ..., या nवें बॉक्स में कम से कम q_n ऑब्जेक्ट होते हैं।

इससे q₁ = q₂ = ... = q_n = 2, लेकर सरल रूप प्राप्त किया जाता है, जिससे n + 1 वस्तुएं प्राप्त होती हैं। q₁ = q₂ = ... = q_n = r लेने से सिद्धांत का अधिक मात्रात्मक संस्करण मिलता है, अर्थात्:

मान लीजिए n और r धनात्मक पूर्णांक हैं। यदि n(r - 1) + 1 ऑब्जेक्ट को n बॉक्स में वितरित किया जाता है, तो कम से कम बॉक्स में r या अधिक ऑब्जेक्ट होते हैं।

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

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

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

$1-{\frac {(m)_{n}}{m^{n}}},$

जहाँ (m)_n न्यूतम भाज्य m(m − 1)(m − 2)...(m − n + 1) है। n = 0 के लिए और n = 1 (और m > 0), के लिए, वह संभावना शून्य है; दूसरे शब्दों में, यदि केवल पिजनहोल है, तो कोई संघर्ष नहीं हो सकता। n > m (पिजनहोल के छिद्र से अधिक पिजनहोल) के लिए यह है, इस स्तिथि में यह सामान्य पिजनहोल के छिद्र के सिद्धांत से युग्मित होता है। किन्तु पिजन की संख्या पिजनहोल की संख्या (n ≤ m) से अधिक न हो, किन्तु पिजनहोल में पिजन को नियुक्त करने की यादृच्छिक प्रकृति के कारण प्रायः होने की पर्याप्त संभावना होती है। उदाहरण के लिए, यदि 2 पिजनहोलों को अव्यवस्थित रूप से 4 पिजनहोल को प्रदान किया गया है, तो 25% संभावना है कि कम से कम पिजनहोल में अधिक पिजनहोल होंगे; 5 पिजनहोलों और 10 छिद्रों के लिए, यह संभावना 69.76% है; और 10 पिजनहोलों और 20 छिद्रों के लिए यह लगभग 93.45% है। यदि छिद्रों की संख्या निश्चित रहती है, तो अधिक पिजनहोल जोड़ने पर एक जोड़े की संभावना सदैव अधिक होती है। जन्मदिन विरोधाभास में इस समस्या का अधिक विस्तार से प्रतिक्रिया की जाती है।

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

अनंत समुच्चय

पिजनहोल सिद्धांत को कार्डिनल संख्याओं के संदर्भ में वाक्यांशित करके अनंत समुच्चयों तक बढ़ाया जा सकता है: यदि समुच्चय A की कार्डिनैलिटी समुच्चय B की कार्डिनैलिटी से अधिक है, तो A से B तक कोई इंजेक्शन नहीं है। चूँकि, इस रूप में सिद्धांत टॉटोलॉजी (तर्क) है, क्योंकि कथन का अर्थ यह है कि समुच्चय A की कार्डिनैलिटी समुच्चय B की कार्डिनैलिटी से अधिक है, A से B तक कोई इंजेक्टिव मैप नहीं है। चूँकि, सीमित समुच्चय में कम से कम तत्व जोड़ना यह सुनिश्चित करने के लिए पर्याप्त है कि कार्डिनैलिटी बढ़ती है।

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

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

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

क्वांटम यांत्रिकी

याकिर अहरोनोव एट अल तर्क प्रस्तुत किए हैं कि क्वांटम यांत्रिकी में पिजनहोल सिद्धांत का उल्लंघन किया जा सकता है, और क्वांटम यांत्रिकी में पिजनहोल सिद्धांत का परीक्षण करने के लिए इंटरफेरोमेट्री प्रयोगों का प्रस्ताव रखा है। चूँकि, पश्चात के शोध ने इस निष्कर्ष पर प्रश्न चिह्न लगा दिया है। जनवरी 2015 के arXiv प्रीप्रिंट में, बर्मिंघम विश्वविद्यालय के शोधकर्ताओं एलेस्टेयर राय और टेड फोर्गन ने इंटरफेरोमीटर के माध्यम से विभिन्न ऊर्जाओं पर इलेक्ट्रॉनों की उड़ान पर मानक पिजनहोल सिद्धांत को नियोजित करते हुए सैद्धांतिक तरंग फलन विश्लेषण किया। यदि इलेक्ट्रॉनों में परस्पर क्रिया शक्ति नहीं होती, तो वे प्रत्येक एकल, पूर्णतः वृत्ताकार शिखर उत्पन्न करते है। उच्च अंतःक्रिया शक्ति पर, प्रत्येक इलेक्ट्रॉन डिटेक्टर पर कुल 12 चोटियों के लिए चार भिन्न-भिन्न चोटियाँ उत्पन्न करता है; ये शिखर चार संभावित अंतःक्रियाओं का परिणाम हैं जिन्हें प्रत्येक इलेक्ट्रॉन अनुभव कर सकता है (अकेले, केवल पहले अन्य कण के साथ, केवल दूसरे अन्य कण के साथ, या तीनों साथ)। यदि अंतःक्रिया की स्थिरता अधिक कम थी, जैसा कि कई वास्तविक प्रयोगों में होता है, तो शून्य-अंतःक्रिया प्रारूप से विचलन लगभग अदृश्य होगा, जो ठोस पदार्थों में परमाणुओं के लैटिस अंतर से अधिक छोटा होगा, जैसे कि इन प्रारूप को देखने के लिए उपयोग किए जाने वाले डिटेक्टर इससे स्थिर किन्तु अशून्य अंतःक्रिया शक्ति को बिना किसी अंतःक्रिया से भिन्न करना अधिक कठिन या असंभव हो जाएगा, और इस प्रकार तीन इलेक्ट्रॉनों का भ्रम उत्पन्न होगा जो तीनों के दो पथों से निकलने के अतिरिक्त परस्पर क्रिया नहीं करते हैं।

यह भी देखें

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

संदर्भ

• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pentice Hall, ISBN 978-0-13-602040-0
• Fletcher, Peter; Patty, C.Wayne (1987), Foundations of Higher Mathematics, PWS-Kent, ISBN 978-0-87150-164-6
• Grimaldi, Ralph P. (1994), Discrete and Combinatorial Mathematics: An Applied Introduction (3rd ed.), Addison-Wesley, ISBN 978-0-201-54983-6
• Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016

बाहरी संबंध

• "Dirichlet box principle", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• "The strange case of The Pigeon-hole Principle"; Edsger Dijkstra investigates interpretations and reformulations of the principle.
• "The Pigeon Hole Principle"; Elementary examples of the principle in use by Larry Cusick.
• "Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles"; basic Pigeonhole Principle analysis and examples by Alexander Bogomolny.
• "16 fun applications of the pigeonhole principle"; Interesting facts derived by the principle.
• "How Many Humans Have the Same Number of Body Hairs?". PBS Infinite Series. December 1, 2016. Archived from the original on 2021-12-11 – via YouTube.