Pigeonhole Principle
1.कपोत कोष्ठ सिद्धान्त (Pigeonhole Principle),विविक्त गणित में कपोत कोष्ठ सिद्धान्त (Pigeonhole Principle in Discrete Mathematics):
कपोत कोष्ठ सिद्धान्त (Pigeonhole Principle) के इस आर्टिकल में कपोत कोष्ठ सिद्धान्त पर आधारित सवालों को हल करके समझने का प्रयास करेंगे।
आपको यह जानकारी रोचक व ज्ञानवर्धक लगे तो अपने मित्रों के साथ इस गणित के आर्टिकल को शेयर करें।यदि आप इस वेबसाइट पर पहली बार आए हैं तो वेबसाइट को फॉलो करें और ईमेल सब्सक्रिप्शन को भी फॉलो करें।जिससे नए आर्टिकल का नोटिफिकेशन आपको मिल सके।यदि आर्टिकल पसन्द आए तो अपने मित्रों के साथ शेयर और लाईक करें जिससे वे भी लाभ उठाए।आपकी कोई समस्या हो या कोई सुझाव देना चाहते हैं तो कमेंट करके बताएं।इस आर्टिकल को पूरा पढ़ें।
Also Read This Article:- Functions in Discrete Mathematics
2.कपोत कोष्ठ सिद्धान्त के साधित उदाहरण (Pigeonhole Principle Solved Examples):
Example:1.एक मरीज को 30 दिनों के लिए किसी दवा की गोलियाँ,प्रतिदिन कम से कम एक गोली लेने के अनुदेश के साथ दी जाती है सिद्ध कीजिए कि लगातार कुछ दिनों का एक अन्तराल ऐसा अवश्य है जिसमें मरीज यथार्थतः 14 गोलियाँ लेता है?
(A patient is given a prescription of 45 tablets with the instructions to take at least one tablet per day for 30 days.Prove that there must be a period of consecutive days during which the patient takes a total of exactly 14 tablets?):
Solution:माना कि mवें (m^{th}) दिन के अन्त तक मरीज द्वारा ली गई गोलियों की संख्या a_m है।चूँकि मरीज प्रतिदिन कम से कम एक गोली तथा ज्यादा से ज्यादा 45 गोलियाँ 30 दिनों में लेता है,अतः
1 \leq a_1 < a_2 < \ldots \ldots < a_{30} \leq 45 \ldots(1)
प्रत्येक असमिका में 14 का योग करने पर,
a_1+14<a_2+14< \ldots \ldots < a_{30}+14 \leq 45+14=59 \cdots(2)
(1) तथा (2) को मिलाने पर हमें a_1, a_2, \ldots, a_{30}, a_1+14, a_2+14, \ldots, a_{30}+14
कुल 60 पूर्णांक प्राप्त होते हैं,जो सभी 1 तथा 59 के मध्य स्थित हैं।अतएव हमारे पास 60 कपोत (पूर्णांक) 59 कपोत कोष्ठों में है।स्पष्टतः दो पूर्णांक ऐसे अवश्य हैं जो परस्पर बराबर हैं।अब चूँकि (1) के सभी पूर्णांक भिन्न-भिन्न है;इसी प्रकार (2) के भी सभी पूर्णांक भिन्न-भिन्न हैं;अतः (1) में निरूपित कोई पूर्णांक a_m , (2) में निरूपित किसी पूर्णांक a_n+14 के बराबर है।
अर्थात् a_m=a_n+14 \\ \Rightarrow a_m-a_n=14
अतएव mवें तथा nवें दिनों के मध्य मरीज यथार्थतः (exactly) 14 गोलियाँ लेता है।
Example:2.किसी तालिका में 72 वस्तुओं की सूची है तथा प्रत्येक के सम्मुख “प्राप्य” या “अप्राप्य” अंकित है।कुल 40 वस्तुएँ प्राप्य हैं (उपलब्ध हैं।) सिद्ध कीजिए कि सूची में कम से कम दो प्राप्य वस्तुओं में एक यदि mवें स्थान पर है तो दूसरी (m+7)वें स्थान पर (i.e.,17वें तथा 24वें स्थान पर) होगी।
(An inventory consists of 72 items,each marked “available” or “unavailable”. There are 40 available items. Prove that there are at least two available items if one is at mth place then the other is at (m+1)th place (e.g. at position 17 and 24)?
Solution:माना,mवें उपलब्ध वस्तु (item) की स्थिति है।हमें प्रदर्शित करना है कि किसी m तथा n के लिए a_m-a_n=7
तब 1 \leq a_1<a_2<a_3<\cdots<a_{40} \leq 72 \cdots(1)
अतः a_1+7< a_2+7<a_3+7< \ldots \ldots <a_{40}+7 \leq 72+7=79 \cdots(2)
(1) तथा (2) के सम्मिलन से हमें a_1, a_2, \ldots \ldots, a_{40}, a_1+7, a_2+7, \ldots, a_{40}+7 ,कुल 80 पूर्णांक प्राप्त होते हैं,जो सभी 1 तथा 79 के मध्य स्थित हैं।
अतः कपोत कोष्ठ सिद्धान्त के अनुसार कम से कम दो संख्याओं (पूर्णांकों) को समान होना चाहिए।
परन्तु (1) में निरूपित सभी पूर्णांक तथा (2) में निरूपित सभी पूर्णांक भिन्न-भिन्न है।अतः (1) में कोई पूर्णांक a_m, (2) में स्थित किसी पूर्णांक a_n+7 के बराबर होना चाहिए।
अर्थात् a_m=a_n+7 \Rightarrow a_m=a_n+7 \Rightarrow a_m-a_n=7
Example:3.किसी प्रतियोगी परीक्षा में 45 प्रतियोगी बैठते हैं।सिद्ध कीजिए कि कम से कम दो विद्यार्थी ऐसे हैं जिनके अनुक्रमांकों का अन्तर 44 का गुणक है।
(45 candidates appear in a competitive examination. Prove that there are at least two candidates whose roll numbers differ by a multiple of 44.)
Solution:माना X सभी 45 प्रतियोगियों के अनुक्रमांको का समुच्चय है तथा माना कि किसी भी पूर्णांक x को 44 से विभाजित करने पर प्राप्त शेष पदों (remainders) का समुच्चय Y है,तब
Y={0,1,2,……,43}
माना f: X \rightarrow Y इस प्रकार है कि (s.t.) f(x)=शेष पद,जब पूर्णांक x,44 से विभाजित किया जाता है।
चूँकि |X|=45 तथा |Y|=44
इसलिए |X|>|Y|
अतः कपोत कोष्ठ के सिद्धान्त के अनुसार दो भिन्न-भिन्न अनुक्रमांक x_1 और x_2 इस प्रकार अवश्य हैं कि f\left(x_1\right)=f\left(x_2\right)
अब x_1=44 \cdot r+f\left(x_1\right)
तथा x_2=44 \cdot s+f\left(x_2\right)
जहाँ r तथा s धनात्मक पूर्णांक हैं।
तब x_1-x_2 =44 r-44 s \quad\left[\because f\left(x_1\right)=f\left(x_2\right)\right] \\ =44(r-s)
परन्तु r-s एक पूर्णांक है।
अतः x_1-x_2 ,44 का गुणक है।
Example:4.6 व्यक्तियों के किसी समूह में कम से कम 3 व्यक्ति परस्पर मित्र अथवा कम से कम 3 व्यक्ति परस्पर अपरिचित होने चाहिए।
(In a group of 6 people, at least three must be mutual friends or at least three must be mutual strangers.)
Solution:माना “A” 6 व्यक्तियों में से एक है।तब शेष n=5 व्यक्तियों को m=2 के दो कोष्ठों (boxes) में रखा तथा उन कोष्ठों को “A के मित्र” तथा “A के अपरिचित” चिन्हों से चिन्हित किया।चूँकि \left[\frac{n}{m}\right]=\left[\frac{5}{2}\right]=3 ,अतः कपोत कोष्ठ सिद्धान्त के अनुसार इन कोष्ठों में से कम से कम एक कोष्ठ में तीन व्यक्ति होने चाहिए।माना ये तीन व्यक्ति “A” के मित्र हैं ;यदि इनमें से कोई भी दो व्यक्ति मित्र हैं तब “A” को इनके साथ मिलाने पर हमें परस्पर तीन मित्रों का एक समूह प्राप्त होता है।किसी भी स्थिति में हमें अभीष्ट निष्कर्षों में से एक की प्राप्ति होती है।दूसरी सम्भावना है कि 5 में से तीन व्यक्ति “A” के अपरिचित हैं,पूर्व तर्क की ही तरह पुनः अभीष्ट निष्कर्ष की ओर इंगित करता है।
उपर्युक्त उदाहरणों के द्वारा कपोत कोष्ठ सिद्धान्त (Pigeonhole Principle),विविक्त गणित में कपोत कोष्ठ सिद्धान्त (Pigeonhole Principle in Discrete Mathematics) को समझ सकते हैं।
Also Read This Article:- Theorems on Composition of Functions
3.कपोत कोष्ठ सिद्धान्त (Frequently Asked Questions Related to Pigeonhole Principle),विविक्त गणित में कपोत कोष्ठ सिद्धान्त (Pigeonhole Principle in Discrete Mathematics) से सम्बन्धित अक्सर पूछे जाने वाले प्रश्न:
प्रश्न:1.कपोत कोष्ठ सिद्धान्त का कथन लिखिए। (Write the Statement of the Pigeonhole Principle):
उत्तर:इस सिद्धान्त के अनुसार यदि “n कपोतों (pigeons) को k कपोत कोष्ठों (pigeonholes) में रखा जाये जहाँ,तब एक कपोत कोष्ठ इस प्रकार अवश्य है,जिसमें दो या अधिक हैं।”
प्रश्न:2.कपोत कोष्ठ सिद्धान्त में क्या ध्यान रखें? (What to Keep in Mind in the Pigeonhole Principle?):
उत्तर:कपोत कोष्ठ सिद्धान्त से यह नहीं बताया जा सकता है कि किस कपोत कोष्ठ में दो या अधिक कपोत हैं।यह केवल किसी कोष्ठ में दो या अधिक कपोतों के विद्यमान होने की बात निश्चयात्मक रूप से बताता है।पुनः कपोत कोष्ठ सिद्धान्त की अनुपालना करते समय यह निश्चित कर लेना आवश्यक है कि कौन-सी वस्तुएँ (objects) कपोतों के रूप में तथा कौन-सी वस्तुएँ कपोत कोष्ठों के रूप में ली जाती हैं।
प्रश्न:3.कपोत कोष्ठ सिद्धान्त को प्रमाणित कीजिए। (Prove the Pigeonhole Principle):
उत्तर:कपोत कोष्ठ सिद्धान्त को प्रमाणित करने के लिए माना कि सिद्धान्त सत्य नहीं है।अर्थात् यदि n कपोतों को k कोष्ठों में (k<n) रखा जाये तो माना कि प्रत्येक कोष्ठ में अधिक से अधिक एक कपोत है।तब ज्यादा से ज्यादा k कपोत ही k कपोत कोष्ठों में रह सकते हैं जबकि कुल n कपोत हैं तथा n>k . यह एक विरोधाभास है।अतः “कपोत कोष्ठ सिद्धान्त” सत्य है।
प्रश्न:4.कपोत कोष्ठ सिद्धान्त को फलन की भाषा में व्यक्त करो। (Convey the Pigeonhole Principle in the Language of Function):
उत्तर:यदि X तथा Y कोई दो परिमित समुच्चय हैं जहाँ |x|>|Y| तथा यदि f: X \rightarrow Y समुच्चय X से समुच्चय Y में कोई फलन है तब कम से कम दो अवयव x_1, x_2 \in X इस प्रकार हैं कि
(s.t.) x_1 \neq x_2 \Rightarrow f(x_1)=f(x_2)
उपर्युक्त प्रश्नों के उत्तर द्वारा कपोत कोष्ठ सिद्धान्त (Pigeonhole Principle),विविक्त गणित में कपोत कोष्ठ सिद्धान्त (Pigeonhole Principle in Discrete Mathematics) के बारे में और अधिक जानकारी प्राप्त कर सकते हैं।
| No. | Social Media | Url |
|---|---|---|
| 1. | click here | |
| 2. | you tube | click here |
| 3. | click here | |
| 4. | click here | |
| 5. | Facebook Page | click here |
| 6. | click here | |
| 7. | click here |
Pigeonhole Principle
कपोत कोष्ठ सिद्धान्त
(Pigeonhole Principle)
Pigeonhole Principle
कपोत कोष्ठ सिद्धान्त (Pigeonhole Principle) के इस आर्टिकल में कपोत
कोष्ठ सिद्धान्त पर आधारित सवालों को हल करके समझने का प्रयास करेंगे।
About Author
Satyam
About my self I am owner of Mathematics Satyam website.I am satya narain kumawat from manoharpur district-jaipur (Rajasthan) India pin code-303104.My qualification -B.SC. B.ed. I have read about m.sc. books,psychology,philosophy,spiritual, vedic,religious,yoga,health and different many knowledgeable books.I have about 15 years teaching experience upto M.sc. ,M.com.,English and science.
