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

छिद्रों में पिजनहोल. यहाँ वहाँ हैं 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 लाख पिजनहोलखानों में से प्रत्येक में नौ लंदनवासियों के बाल केवल 90 लाख लोगों के होते हैं।

औसत मामले के लिए (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 से कम लंबाई के सभी अनुक्रमों के (बहुत) छोटे समुच्चय पर मैप किया जा सकता है 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),$

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

$(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]}. फिर कोई इस तथ्य का उपयोग मामले को साबित करने के लिए कर सकता है p में (0, 1]: पाना 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, तो किसी स्थान पर कम से कम दो वस्तुएँ प्राप्त होती हैं।#(1 के समतुल्य सूत्रीकरण) यदि n वस्तुएं वितरित की जाती हैं n स्थानों को इस प्रकार रखें कि किसी भी स्थान को एक से अधिक वस्तुएँ प्राप्त न हों, तो प्रत्येक स्थान को छिद्र्कुल एक वस्तु प्राप्त होती है।#अगर n वस्तुएं वितरित की जाती हैं m स्थान, और यदि n < m, तो किसी स्थान को कोई वस्तु प्राप्त नहीं होती है।
2. (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पिजनहोलों को बेतरतीब ढंग से डाला जाता है m समान संभावना वाले पिजनहोलखाने 1/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), तो संभावना शून्य नहीं है X से अधिक या बराबर है E(X), और इसी तरह संभावना शून्य नहीं है 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.