पिजनहोल (कपोत कोठरी) सिद्धांत कैलकुलेटर
सामान्यीकृत सूत्र · चरण-दर-चरण प्रमाण · क्लासिक उदाहरण
न्यूनतम वस्तुओं की संख्या ज्ञात करें जो यह गारंटी दे कि कम से कम m वस्तुएँ एक ही कंटेनर साझा करें। सामान्यीकृत पिजनहोल सूत्र k(m−1)+1 या सीलिंग ⌈n/k⌉ का उपयोग करता है।
गणना मोड चुनें
मोड 1: कंटेनरों की संख्या (k) और गारंटी सीमा (m) दिए जाने पर, आवश्यक कुल वस्तुओं की संख्या ज्ञात करें ताकि कम से कम एक कंटेनर में m या अधिक वस्तुएँ हों। सूत्र: k(m−1) + 1
त्वरित उदाहरण (Quick Examples)
चरण-दर-चरण प्रमाण (Step-by-Step Proof)
दृश्य आरेख (Visual Diagram)
बायें: सबसे खराब स्थिति का वितरण (प्रति बॉक्स m-1 — कोई गारंटी नहीं)। दायें: एक अतिरिक्त वस्तु किसी एक बॉक्स को m वस्तुओं तक पहुँचा देती है।
वितरण सत्यापन (Distribution Verification)
पिजनहोल सिद्धांत का उपयोग करके विस्तृत समाधान देखने के लिए किसी भी परिदृश्य पर क्लिक करें।
कितने लोग गारंटी देते हैं कि 2 लोगों का जन्मदिन एक ही दिन हो? 3 लोगों के लिए क्या होगा?
एक जोड़ी मोज़े मिलने की गारंटी के लिए बिना देखे न्यूनतम कितने मोज़े निकालें?
समान जन्म के महीने या सप्ताह के एक ही दिन जन्मे दो लोगों की गारंटी।
एक ही रंग (suit) के दो पत्तों की गारंटी के लिए न्यूनतम ड्रा।
{1…10} में से कोई भी 6 पूर्णांक योग 11 वाले एक जोड़े की गारंटी देते हैं।
1×1 वर्ग में 5 बिंदु दूरी ≤ 1/√2 के साथ 2 बिंदुओं की गारंटी देते हैं।
समाधान
त्वरित संदर्भ — क्लासिक पिजनहोल उदाहरण
कैलकुलेटर को उस परिदृश्य के साथ स्वचालित रूप से भरने के लिए किसी भी कार्ड पर क्लिक करें।
पिजनहोल सिद्धांत (Pigeonhole Principle) क्या है?
पिजनहोल सिद्धांत — जिसे डिरिश्लेट का बॉक्स सिद्धांत या दराज सिद्धांत (drawer principle) भी कहा जाता है — संयोजन विज्ञान (combinatorics) और असंतत गणित में सबसे सरल लेकिन सबसे शक्तिशाली प्रमेयों में से एक है। अपने सबसे बुनियादी रूप में यह बताता है: यदि n वस्तुओं को k कंटेनरों में रखा जाता है और n > k है, तो कम से कम एक कंटेनर में एक से अधिक वस्तुएँ होनी चाहिए।
इसका नाम कपोत कोठरी (pigeonholes) से आता है: यदि आपके पास 10 कबूतर हैं और केवल 9 कोठरियाँ हैं, तो कम से कम एक कोठरी में 2 या अधिक कबूतर अवश्य बैठेंगे। भले ही यह बहुत स्पष्ट और सीधा लगता हो, लेकिन इसका उपयोग संख्या सिद्धांत, ग्राफ सिद्धांत और कंप्यूटर विज्ञान में बहुत गहरे परिणामों को साबित करने के लिए किया जाता है।
सामान्यीकृत पिजनहोल सिद्धांत
सामान्यीकृत पिजनहोल सिद्धांत बुनियादी कथन को किसी भी सीमा m तक विस्तारित करता है। यदि n वस्तुओं को k कंटेनरों में वितरित किया जाता है, तो कम से कम एक कंटेनर में कम से कम ⌈n/k⌉ वस्तुएँ होंगी (जहाँ ⌈ ⌉ सीलिंग फ़ंक्शन को दर्शाता है, जो निकटतम बड़े पूर्णांक तक पूर्णांकित करता है)।
इसके समान, यह गारंटी देने के लिए कि कम से कम एक कंटेनर में m या अधिक वस्तुएँ हों, आपको न्यूनतम वस्तुओं की आवश्यकता होगी:
N = k(m − 1) + 1
इसके पीछे का तर्क बिल्कुल स्पष्ट है: यदि आपके पास केवल k(m-1) वस्तुएँ होतीं, तो आप हर बॉक्स में ठीक m-1 वस्तुएँ रख सकते थे, और किसी भी बॉक्स में m वस्तुएँ नहीं पहुँचतीं। लेकिन जैसे ही आप 1 और वस्तु जोड़ते हैं (यानी k(m-1)+1-वीं वस्तु), उसे किसी न किसी बॉक्स में जाना ही होगा, जिससे उस बॉक्स में वस्तुओं की संख्या m हो जाएगी।
ऐतिहासिक पृष्ठभूमि — डिरिश्लेट का दराज सिद्धांत
इस सिद्धांत को जर्मन गणितज्ञ पीटर गुस्ताव लेज्यून डिरिश्लेट द्वारा 1834 के आसपास औपचारिक रूप दिया गया था, जिन्होंने इसे Schubfachprinzip (दराज सिद्धांत) कहा था। डिरिश्लेट ने इसका उपयोग डायोफैंटाइन सन्निकटन (Diophantine approximation) में गहन परिणामों को साबित करने के लिए किया था।
कंप्यूटर विज्ञान में अनुप्रयोग
- हैश टकराव (Hash Collisions): कोई भी हैश फ़ंक्शन जो बड़े इनपुट डेटा को छोटे आकार के हैश मानों (जैसे 32-बिट मान) में मैप करता है, उसमें टकराव होना निश्चित है। यदि आपके पास 2³² से अधिक विशिष्ट फ़ाइलें हैं, तो पिजनहोल सिद्धांत के अनुसार, कम से कम दो फ़ाइलों का हैश मान समान होगा।
- lossless संपीड़न की सीमाएं (Lossless Compression Limits): कोई भी दोषरहित संपीड़न एल्गोरिदम सभी संभावित इनपुट फ़ाइलों को छोटा नहीं कर सकता है। पिजनहोल सिद्धांत यह साबित करता है कि यदि कुछ फ़ाइलें छोटी की जाती हैं, तो अन्य फ़ाइलों का आकार बड़ा होना ही चाहिए।
- सॉर्टिंग एल्गोरिदम की निचली सीमा (Sorting Lower Bounds): तुलना-आधारित सॉर्टिंग एल्गोरिदम को सबसे खराब स्थिति में कम से कम ⌈log₂(n!)⌉ तुलनाओं की आवश्यकता होती है। यह तर्क निर्णय पेड़ (decision tree) पर पिजनहोल सिद्धांत का उपयोग करके सिद्ध किया गया है।
बर्थडे पैराडॉक्स से संबंध
पिजनहोल सिद्धांत बताता है कि एक कमरे में 367 लोग होने पर 100% गारंटी है कि कम से कम दो लोगों का जन्मदिन एक ही दिन हो (क्योंकि अधिकतम 366 अलग-अलग जन्मदिन हो सकते हैं)। यह निश्चितता की एक अटूट सीमा है।
इसके विपरीत, प्रसिद्ध बर्थडे पैराडॉक्स (birthday paradox) एक प्रायिकता सिद्धांत है: केवल 23 लोगों के साथ, दो लोगों के जन्मदिन साझा करने की संभावना 50% से अधिक हो जाती है। यह इसलिए है क्योंकि जन्मदिन साझा करने के लिए संभावित जोड़ों (pairs) की संख्या तेजी से बढ़ती है। दोनों अलग-अलग प्रश्नों का उत्तर देते हैं: पिजनहोल सिद्धांत सबसे खराब स्थिति की गारंटी देता है, जबकि बर्थडे पैराडॉक्स औसत-मामले की संभावना को मापता है।
अक्सर पूछे जाने वाले प्रश्न
पिजनहोल सिद्धांत क्या है?
सामान्यीकृत पिजनहोल सिद्धांत क्या है?
क्या 5 मोज़े के रंगों के साथ, 6 मोज़े निकालने पर एक जोड़ी की गारंटी है?
सिद्धांत के मूल सूत्र
न्यूनतम वस्तुएँ (गारंटी m के लिए):
N = k(m-1) + 1
गारंटीकृत ओवरलैप m (n वस्तुओं के लिए):
m = ⌈n / k⌉