Prove that among any 51 integers chosen from {1, 2, ..., 100}, there exist two that are coprime.

Answer: यह सिद्ध होता है कि $\{1, 2, ..., 100\}$ से चुने गए किसी भी 51 पूर्णांकों में से कम से कम दो सहअभाज्य होंगे।

Step-by-step solution

Step 1: कबूतर-छेद सिद्धांत का उपयोग

हमें यह सिद्ध करना है कि समुच्चय $S = \{1, 2, ..., 100\}$ से चुने गए किसी भी 51 पूर्णांकों में से कम से कम दो सहअभाज्य होंगे। इस समस्या को हल करने के लिए हम कबूतर-छेद सिद्धांत (Pigeonhole Principle) का उपयोग करेंगे।

Step 2: कबूतर-छेद बनाना

हम 1 से 100 तक के पूर्णांकों को कबूतर-छेद में विभाजित करते हैं। हम 50 जोड़े बनाते हैं: $(2{,}3), (4{,}5), ..., (98{,}99)$ । इसके अलावा, हम संख्या 1 को एक अलग कबूतर-छेद के रूप में लेते हैं। इस प्रकार, हमारे पास कुल $50 + 1 = 51$ कबूतर-छेद हैं।

Step 3: कबूतर-छेद सिद्धांत लागू करना

यदि हम 1 से 100 तक के समुच्चय से 51 संख्याएँ चुनते हैं, और हमारे पास 51 कबूतर-छेद हैं, तो कबूतर-छेद सिद्धांत के अनुसार, कम से कम दो संख्याएँ एक ही कबूतर-छेद से होनी चाहिए।

Step 4: सहअभाज्य संख्याओं का निर्धारण

यदि चुनी गई दो संख्याएँ एक ही कबूतर-छेद से हैं, तो वे या तो $\{1\}$ से 1 होंगी, या वे एक जोड़े $\{n, n+1\}$ से होंगी। 1. यदि एक संख्या 1 है, तो 1 किसी भी पूर्णांक के साथ सहअभाज्य होता है। 2. यदि दो संख्याएँ $\{n, n+1\}$ के रूप में हैं, तो वे लगातार पूर्णांक हैं। लगातार पूर्णांक हमेशा सहअभाज्य होते हैं, अर्थात $\text{gcd}(n, n+1) = 1$ । इसलिए, किसी भी स्थिति में, चुनी गई दो संख्याएँ सहअभाज्य होंगी।

Solve your own maths question free →