Pigeonhole तर्क, double counting और binomial identities
उद्देश्य और पूर्वज्ञान
हर संभावना बनाए बिना existence सिद्ध करना, उपयोगी pigeonholes चुनना और एक ही स्पष्ट set को दो तरीकों से गिनकर identities निकालना सीखें। पूर्वज्ञान: sets, remainders, combinations और simple-graph degrees। सभी sets finite हैं। Bound लगाने से पहले parameters की शर्तें बताएँ।
Guarantee, एक उदाहरण से अधिक मजबूत दावा है। हर distribution में collision सिद्ध करने को capacity contradiction लें। Threshold सबसे छोटा है यह दिखाने के लिए उसके ठीक नीचे ऐसी distribution भी दें जो माँगे outcome को टालती हो।
1. Generalized pigeonhole principle और sharp thresholds
N≥1 objects को k≥1 boxes में रखें। किसी box में कम-से-कम ceil(N/k) objects होंगे। यदि हर box में अधिकतम ceil(N/k)−1 हों, तो कुल capacity N से कम होगी, जो वास्तविक count के विरुद्ध है।
k boxes में किसी एक में कम-से-कम r≥1 objects की guarantee के लिए न्यूनतम संख्या k(r−1)+1। इतने objects पर हर box को r से नीचे रखने से केवल k(r−1) समाएँगे। उलटे, k(r−1) objects को हर box में ठीक r−1 देकर outcome टाल सकते हैं। इसलिए छोटा general threshold नहीं।
छह categories में 25 objects कम-से-कम एक category में पाँच force करते हैं, क्योंकि 25=6·4+1। चौबीस से पाँच forced नहीं: हर category में चार रख दें। 26 objects होने पर भी guaranteed lower bound ceil(26/6)=5 है; पिछला threshold पार होने मात्र से 6 नहीं हो जाता।
Principle कम-से-कम एक box की बात करता है, हर box की नहीं और ठीक r की नहीं। किसी box में बहुत अधिक भी हो सकते हैं। Unequal capacities c₁,…,c_k हों तो Σc_i से अधिक objects किसी capacity को exceed करेंगे। वही contradiction argument nonuniform capacities पर लागू है।
2. Remainder boxes से divisibility
हर integer का modulo m, m≥1, में remainder 0,…,m−1 में से एक है। m+1 integers में दो का remainder समान होगा। उनका difference m से divisible है। Boxes remainder classes हैं, original integer values नहीं।
आठ integers और modulus 7 में दो का difference 7 का multiple होगा। Numbers का 1 से 7 के बीच होना जरूरी नहीं; negative integers भी 0,…,6 में unique remainder से वर्गीकृत होते हैं। निष्कर्ष difference का है, यह जरूरी नहीं कि किसी pair का sum 7 से divisible हो।
General same-remainder collision के लिए bound sharp है: m numbers 0,1,…,m−1 अलग boxes लेते हैं। Chosen integers distinct हों तो difference nonzero है; repeated inputs allowed हों तो equal entries का difference zero भी 7 या सामान्य m से divisible है।
सही boxes चुनना मुख्य विचार है। आठ values को अनंत integer-value boxes में रखने से उपयोगी collision नहीं मिलता; सात remainder classes में compress करने से मिलता है।
3. Prefix sums से contiguous divisible sum
किसी भी m integers की sequence a₁,…,a_m में कोई nonempty contiguous block है जिसका sum m से divisible है। Prefix sums s₀=0 और s_i=a₁+⋯+a_i,1≤i≤m परिभाषित करें। m+1 prefix sums और केवल m remainder classes हैं।
दो prefixes s_i,s_j का remainder समान होगा, i<j। उनका difference a_{i+1}+⋯+a_j, m से divisible है। i<j से block nonempty; prefixes के difference से contiguous। कुछ entries zero या negative होने पर भी proof सही।
Worked example: पाँच-term sequence 2,4,1,3,6। Prefix sums 0,2,6,7,10,16 और modulo 5 remainders 0,2,1,2,0,1। s₁=2 और s₃=7 के समान remainder से a₂+a₃=4+1=5। Repeated remainder 0 से a₁+⋯+a₄=10 भी मिलता है। एक witness पर्याप्त है, लेकिन कई हो सकते हैं।
आम गलती: केवल s₁,…,s_m लेकर कहना कि m values और m boxes में collision जरूरी है। जरूरी नहीं। s₀=0 extra prefix देता है और उस prefix को भी संभालता है जिसका sum स्वयं m से divisible हो।
4. अलग pigeonhole model: odd parts
{1,2,…,2n} से n+1 distinct integers चुनें, n≥1। दो chosen integers में एक दूसरे को divide करेगा। हर positive integer को uniquely 2^t u लिखें, जहाँ u odd और t≥0; u उसका odd part है।
Range में ठीक n संभावित odd parts हैं: 1,3,…,2n−1। हर selected integer को उसके odd-part box में रखें। n+1 choices में दो का odd part u समान; वे 2^a u और 2^b u हैं। Integers distinct हैं, इसलिए a≠b। छोटी power, बड़ी को divide करती है: a<b में ratio 2^{b−a}।
केवल parity से दो boxes बनेंगे, लेकिन समान box के भीतर divisibility सिद्ध नहीं होगी। Odd-part grouping माँगे relation के लिए चुनी गई है। उदाहरण: 6 और 10 दोनों even हैं लेकिन कोई दूसरे को divide नहीं करता; 3,6,12 का odd part 3 है और वे divisibility में ordered हैं।
n+1 threshold sharp है: n numbers n+1,…,2n में कोई distinct divisibility pair नहीं। इस interval में a<b और a|b हो तो b≥2a>2n, असंभव।
5. Double counting: एक ही object की दो गिनतियाँ
Double-counting proof एक objects-set तय करता है, फिर उसे दो decompositions से गिनकर counts बराबर रखता है। दोनों calculations के objects, labels और restrictions समान होने चाहिए।
n distinct people से r-person committee चुनें और उसके एक member को captain बनाएँ, 1≤r≤n। पहले committee C(n,r) तरीकों से, फिर captain r तरीकों से। दूसरे तरीके में captain n तरीकों से, फिर बाकी n−1 में से r−1 members। इसलिए
r C(n,r)=n C(n−1,r−1)।
n=6,r=3 में दोनों 3·20=6·10=60। Captain committee का member है, extra person नहीं। C(n,r) को n से multiply करने पर nonmember को captain चुनने की गलत अनुमति मिलती है।
अब सभी pairs (S,x) गिनें जहाँ S, n-element set का subset है और x∈S, n≥1। |S|=r के अनुसार गिनने पर Σ(r=0 से n)r C(n,r)। या पहले x को n तरीकों से चुनें और बाकी n−1 elements में से हर एक का S में शामिल होना स्वतंत्र तय करें: n2^{n−1}। इसलिए
Σ(r=0 से n)r C(n,r)=n2^{n−1}।
n=6 में 6·32=192। Empty subset का योगदान zero है, इसलिए ambiguity नहीं।
6. Binomial identities को choices से समझें
Integer n≥1 के लिए Pascal identity: C(n,r)=C(n−1,r)+C(n−1,r−1)। एक distinguished element तय करें। r-subset या उसे छोड़ता है और बाकी n−1 में से r चुनता है, या उसे शामिल कर r−1 और चुनता है। Cases disjoint और exhaustive हैं। n≥0 के लिए r<0 या r>n में C(n,r)=0 convention लेकर endpoints साफ रखें।
Nonnegative integers a,b तथा 0≤r≤a+b के लिए Vandermonde identity में a और b आकार के disjoint groups से r objects चुनना है:
C(a+b,r)=Σ_i C(a,i)C(b,r−i)।
i, पहले group से चुनी संख्या है; feasible range के बाहर terms बताए binomial convention से zero हैं। अलग i disjoint cases हैं, इसलिए addition सही।
पाँच distinct red और चार distinct blue objects में से चार चुनें। Direct count C(9,4)=126। Red count i=0,…,4 के अनुसार terms 1,20,60,40,5 हैं, sum 126। Colors, objects की categories हैं; same-color objects को identical नहीं बनाते।
Bijection से C(n,r)=C(n,n−r): चुने subset को उसके complement से बदलें। n≥1 में even-size और odd-size subsets भी बराबर संख्या में हैं। Fixed element की membership toggle करें; यह reversible तरीके से parity बदलता है। हर class में 2^{n−1} subsets। n=0 में दावा गलत: अकेला empty subset even है; parameter condition जरूरी।
7. Graph applications: degree sum और repeated degrees
Finite simple undirected graph में vertex-edge incidences गिनें। हर edge दो incidences देती है, हर endpoint पर एक; vertex v कुल d(v) देती है। इसलिए Σ_v d(v)=2|E|। Right side even है, इसलिए odd-degree vertices की संख्या even होगी। इसका अर्थ हर degree even होना नहीं।
n≥2 vertices वाले graph में दो vertices की degree समान होगी। संभावित degrees 0,…,n−1, ऊपर से n vertices के लिए n boxes लगते हैं। लेकिन degree 0 और degree n−1 साथ नहीं हो सकते: सभी अन्य vertices से adjacent vertex के साथ isolated vertex नहीं। इसलिए अधिकतम n−1 degree values उपलब्ध हैं और repetition forced है।
Assumptions जरूरी हैं। Simple graph में loops या parallel edges नहीं, इसलिए degree≤n−1। Directed graphs में in-degree/out-degree अलग model हैं। Boxes और capacities जाँचे बिना repeated-degree argument दूसरे convention पर न ले जाएँ।
जाँच-सूची और दायरा
Pigeonhole claim में objects, boxes, capacities और same-box से निकलने वाला निष्कर्ष बताएँ। Minimum threshold के लिए forcing proof और उससे नीचे sharp counterexample दोनों दें। Double counting में दो formulas से पहले common counted set तय करें। Identities में labels, disjoint cases और endpoints जाँचें। ये तरीके numerical उत्तर के साथ पूरे families का proof देते हैं, केवल एक tested instance का नहीं।
मौलिक अभ्यास: छह single-correct MCQ
मौलिक प्रश्न हैं, पिछले वर्षों के नहीं। हर प्रश्न में ठीक एक विकल्प चुनें और labels, symmetry, domain तथा positivity की दी शर्तें रखें।
C01. बिना अन्य restrictions, छह boxes में किसी एक में कम-से-कम पाँच objects की guarantee के लिए न्यूनतम कुल संख्या क्या है?
A. 24 B. 25 C. 30 D. 31
उत्तर: B
A: हर box में चार रखकर 24 में किसी को पाँच न दें।
B: सभी boxes पाँच से नीचे हों तो maximum 6·4=24; 25वाँ force करता है और 24 में टाल सकते हैं।
C: 30 पर्याप्त लेकिन minimum नहीं; 25 से ही guarantee।
D: 31 किसी box में कम-से-कम छह force करता है, जो माँग से अधिक है।
C02. सात integers की हर sequence के लिए कौन-सा दावा निश्चित है?
A. कोई एक entry, 7 से divisible। B. सभी entries का sum, 7 से divisible। C. दो adjacent entries के modulo 7 remainders समान। D. किसी nonempty contiguous block का sum, 7 से divisible।
उत्तर: D
A: सातों entries 1 हों तो कोई अकेली entry divisible नहीं।
B: 1,1,1,1,1,1,2 का total 8 है, 7 से divisible नहीं।
C: 1,2,3,4,5,6,7 में adjacent remainders अलग हैं।
D: आठ prefixes s₀,…,s₇ सात remainder classes में हैं। Equal-remainder prefixes से nonempty contiguous divisible-sum block मिलता है।
C03. n≥2 vertices वाले simple undirected graph में दो vertices की degree समान क्यों होनी चाहिए?
A. Degree 0 और n−1 साथ नहीं, इसलिए n vertices के लिए अधिकतम n−1 degree values। B. हर vertex की degree even होना जरूरी। C. सभी n संभावित degrees ठीक एक बार होना जरूरी। D. हर graph regular है।
उत्तर: A
A: Isolated vertex और सभी अन्य vertices से adjacent vertex साथ नहीं। फिर pigeonhole से degree दोहरती है।
B: केवल odd-degree vertices की संख्या even जरूरी; individual degrees odd हो सकती हैं।
C: दो endpoint degree values साथ नहीं, इसलिए यह pattern असंभव।
D: हर graph regular नहीं; निष्कर्ष एक repeated pair का है, सभी degrees समान का नहीं।
C04. Σ(r=0 से 6) r C(6,r) का मान क्या है?
A. 64 B. 384 C. 192 D. 60
उत्तर: C
A: 64 सभी subsets को एक बार गिनता है, distinguished member के बिना।
B: 6·2⁶ में distinguished member की presence को भी choice बना दिया; वह मौजूद होना जरूरी।
C: x∈S वाले pairs (S,x): x के 6 और बाकी members के 2⁵ choices, total 192।
D: 60 केवल तीन-member committee और captain गिनता है, सभी subset sizes नहीं।
C05. पाँच distinct red और चार distinct blue objects में से चार चुनते हैं। Σ(i=0 से 4) C(5,i)C(4,4−i) क्या है?
A. 81 B. 126 C. 120 D. 210
उत्तर: B
A: यह four-subset count नहीं; red count से terms 1+20+60+40+5।
B: Vandermonde नौ objects के सभी four-subsets गिनता है: C(9,4)=126।
C: 120 न disjoint sum से, न direct binomial count से मिलता है।
D: 210=C(10,4) के लिए दस distinct objects चाहिए, जबकि नौ हैं।
C06. छह distinct people में से तीन-person committee और उसी के एक member को captain कितने तरीकों से चुनें?
A. 20 B. 120 C. 18 D. 60
उत्तर: D
A: 20=C(6,3) committee चुनता है, captain नहीं।
B: 20·6 में committee के बाहर के व्यक्ति को captain की गलत अनुमति।
C: 6·3 में पाँच noncaptains से बाकी दो members नहीं चुने जाते; सही factor C(5,2)=10 है।
D: पहले committee फिर captain: C(6,3)·3=60; या captain फिर दो companions: 6·C(5,2)=60।
स्रोत और दायरा
यह मौलिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 में Discrete Mathematics के combinatorial counting भाग को गहरा करता है। आधिकारिक syllabus व्यापक विषय बताता है; MIT chapter counting methods का संस्थागत further-study स्रोत है। यहाँ examples, व्याख्या और अभ्यास मौलिक हैं। एक पाठ से पूरे subject में mastery का दावा नहीं।
स्रोत खोले और जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन