Pigeonhole arguments, double counting and binomial identities
Objectives and prerequisites
Prove existence without constructing every possibility; choose useful pigeonholes rather than only obvious ones; and derive counting identities by counting one well-defined set in two ways. Prerequisites: sets, remainders, combinations and basic simple-graph degrees. All sets are finite. State parameter restrictions before using a bound.
A guarantee is stronger than an example. To show that every distribution forces a collision, use a capacity contradiction. To show a threshold is the smallest possible, also exhibit a distribution immediately below it that avoids the required outcome.
1. Generalized pigeonhole principle and sharp thresholds
Place N objects into k boxes, with N≥1 and k≥1. Some box contains at least ceil(N/k) objects. If every box contained at most ceil(N/k)−1, their total capacity would be below N, contradicting the actual object count.
To guarantee at least r objects in one of k boxes, with r≥1, the least number is k(r−1)+1. At that number, keeping every box below r would allow only k(r−1) objects. Conversely, k(r−1) objects can be distributed with exactly r−1 in every box, so a smaller general guarantee cannot be claimed.
Example: with six categories, 25 objects force at least five in one category, since 25=6·4+1. Twenty-four do not force five: four per category avoids it. If 26 objects are placed instead, ceil(26/6)=5 remains the guaranteed lower bound; it does not become 6 merely because the previous threshold has been passed.
The principle guarantees at least one box, not every box, and not exactly r objects. A box could contain many more. If boxes have unequal allowed capacities c₁,…,c_k, then more than Σc_i objects force some capacity to be exceeded. This is the same contradiction argument with nonuniform capacities.
2. Remainder boxes prove divisibility
Every integer has one of m remainders 0,…,m−1 modulo m, for m≥1. Among m+1 integers, two have the same remainder. Their difference is divisible by m. The boxes are remainder classes, not the original integer values.
For eight integers and modulus 7, two differ by a multiple of 7. The numbers need not lie between 1 and 7; negative integers are also classified by their unique remainder in 0,…,6. The conclusion concerns a difference, not necessarily a pair whose sum is divisible by 7.
The bound is sharp for a general same-remainder collision: the m numbers 0,1,…,m−1 occupy distinct boxes. Distinct chosen integers give a nonzero difference; if repeated inputs are allowed, equal entries have difference zero, which is still divisible by m.
Choosing the right boxes is the main idea. Counting eight values into infinitely many integer-value boxes gives no useful collision, but compressing them into seven remainder classes does.
3. Prefix sums force a contiguous divisible sum
Given any sequence of m integers a₁,…,a_m, some nonempty contiguous block has sum divisible by m. Define prefix sums s₀=0 and s_i=a₁+⋯+a_i for 1≤i≤m. There are m+1 prefix sums but only m remainder classes.
Two prefixes s_i,s_j have the same remainder, with i<j. Their difference is a_{i+1}+⋯+a_j, divisible by m. Because i<j, the block is nonempty; because it is a difference of prefixes, it is contiguous. The proof works even when some entries are zero or negative.
Worked example: take the five-term sequence 2,4,1,3,6. Prefix sums are 0,2,6,7,10,16, whose remainders modulo 5 are 0,2,1,2,0,1. Prefixes s₁=2 and s₃=7 have the same remainder, giving a₂+a₃=4+1=5. The repeated remainder 0 also yields a₁+⋯+a₄=10. Only one witness is needed, but several may exist.
A common mistake is to use only s₁,…,s_m and claim that m values in m boxes must collide. They need not. Including s₀=0 supplies the extra prefix and also handles a prefix whose sum itself is divisible by m.
4. An unexpected pigeonhole model: odd parts
Choose n+1 distinct integers from {1,2,…,2n}, with n≥1. Two chosen integers must satisfy that one divides the other. Write each positive integer uniquely as 2^t u, where u is odd and t≥0; u is its odd part.
There are exactly n possible odd parts in the range, namely 1,3,…,2n−1. Assign each selected integer to its odd-part box. Two of the n+1 choices share some odd part u, so they are 2^a u and 2^b u. Since the integers are distinct, a≠b. The smaller power divides the larger: if a<b, the ratio is 2^{b−a}.
Parity alone would create only two boxes but would not prove divisibility within one box. Odd-part grouping is tailored to the desired relation. For example, 6 and 10 are both even but neither divides the other; 3,6,12 all have odd part 3 and are ordered by divisibility.
The threshold n+1 is sharp: the n numbers n+1,…,2n contain no distinct pair where one divides the other. If a<b in this interval and a divides b, then b≥2a>2n, impossible.
5. Double counting: define the same object twice
A double-counting proof describes one set of objects, counts it by two different decompositions, and equates the results. The two calculations must refer to the same objects, with the same labels and restrictions.
Example: from n distinct people choose an r-person committee and designate one member as captain, where 1≤r≤n. First choose the committee in C(n,r) ways, then its captain in r ways. Alternatively choose the captain in n ways, then the remaining r−1 members from the other n−1 people. Thus
r C(n,r)=n C(n−1,r−1).
For n=6,r=3, both give 3·20=6·10=60. A captain is part of the committee, not an extra person. Multiplying C(n,r) by n would incorrectly allow a nonmember to be selected as captain.
Now count all pairs (S,x), where S is a subset of an n-element set and x∈S, with n≥1. Group by |S|=r to obtain Σ(r=0 to n)r C(n,r). Or choose x in n ways and independently choose which of the other n−1 elements join S, giving n2^{n−1}. Therefore
Σ(r=0 to n)r C(n,r)=n2^{n−1}.
For n=6 this is 6·32=192. The empty subset contributes zero, so it causes no ambiguity.
6. Binomial identities as choices
For integer n≥1, Pascal's identity is C(n,r)=C(n−1,r)+C(n−1,r−1). Fix one distinguished element. An r-subset either excludes it, choosing all r from the other n−1, or includes it, choosing r−1 more. These two cases are disjoint and exhaustive. Use C(n,r)=0 for r<0 or r>n when n≥0 to state endpoint identities cleanly.
For nonnegative integers a,b and 0≤r≤a+b, Vandermonde's identity says that selecting r objects from disjoint groups of sizes a and b gives
C(a+b,r)=Σ_i C(a,i)C(b,r−i).
The index i records how many are selected from the first group; terms outside feasible ranges are zero under the stated binomial convention. Different i values are disjoint cases, so adding is valid.
Example: choose four objects from five distinct red objects and four distinct blue objects. The direct count is C(9,4)=126. By red count i=0,…,4, the terms are 1,20,60,40,5, summing to 126. Colors classify objects; they do not make objects within each color identical.
A bijection proves C(n,r)=C(n,n−r): replace a selected subset by its complement. Likewise, for n≥1, even-sized and odd-sized subsets are equally numerous. Fix an element and toggle its membership; this reversibly switches parity. Each class has 2^{n−1} subsets. The claim fails at n=0, where the sole empty subset has even size, so the parameter condition matters.
7. Graph applications: degree sums and repeated degrees
For a finite simple undirected graph, count vertex-edge incidences. Each edge contributes exactly two incidences, one at each endpoint, while vertex v contributes degree d(v). Hence Σ_v d(v)=2|E|. Because the right side is even, the number of odd-degree vertices is even. This conclusion does not say every degree is even.
A graph with n≥2 vertices must have two vertices of the same degree. Possible degrees are 0,…,n−1, apparently n boxes for n vertices. But degree 0 and degree n−1 cannot both occur: a vertex adjacent to every other vertex cannot coexist with an isolated vertex. Therefore at most n−1 degree values are available, forcing a repetition.
The assumptions matter. Simple graphs have no loops or parallel edges, which bounds degrees by n−1. Directed graphs require separate in-degree/out-degree models. Do not transfer the repeated-degree argument to a different graph convention without checking its boxes and capacity.
Checklist and scope
For a pigeonhole claim, state objects, boxes, capacities and the conclusion that follows from sharing a box. Prove a minimum threshold with both the forcing argument and a sharp counterexample below it. For double counting, explicitly define the common counted set before writing two formulas. For identities, verify label conventions, disjoint cases and endpoints. These methods complement numerical answers with proofs that apply to whole families, not just one tested instance.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option and retain all stated label, symmetry, domain and positivity assumptions.
C01. What is the smallest number of objects that guarantees at least five in one of six boxes, with no other restrictions?
A. 24 B. 25 C. 30 D. 31
Answer: B
A: Four per box places 24 objects without any box containing five.
B: Six boxes can hold at most 6·4=24 while all stay below five; the 25th forces the event, and 24 is avoidable.
C: 30 suffices but is not the least number; 25 already guarantees the event.
D: 31 guarantees at least six in a box, a stronger threshold than requested.
C02. Which claim is guaranteed for every sequence of seven integers?
A. One entry is divisible by 7. B. The sum of all entries is divisible by 7. C. Two adjacent entries have equal remainders modulo 7. D. Some nonempty contiguous block has sum divisible by 7.
Answer: D
A: Seven entries all equal to 1 give no individually divisible entry.
B: For the sequence 1,1,1,1,1,1,2 the total is 8, not divisible by 7.
C: The sequence 1,2,3,4,5,6,7 has distinct adjacent remainders.
D: Eight prefixes s₀,…,s₇ fall into seven remainder classes. Equal-remainder prefixes give a nonempty contiguous divisible-sum block.
C03. Why must a simple undirected graph with n≥2 vertices have two vertices of equal degree?
A. Degree 0 and degree n−1 cannot both occur, so at most n−1 degree values serve n vertices. B. Every vertex must have even degree. C. All n possible degrees must occur exactly once. D. Every graph is regular.
Answer: A
A: An isolated vertex cannot coexist with a vertex adjacent to every other vertex. Pigeonhole then forces a repeated degree.
B: Only the number of odd-degree vertices must be even; individual degrees may be odd.
C: The two endpoint degree values are incompatible, so this proposed pattern is impossible.
D: Graphs need not be regular; the conclusion only requires one repeated pair, not all degrees equal.
C04. What is Σ(r=0 to 6) r C(6,r)?
A. 64 B. 384 C. 192 D. 60
Answer: C
A: 64 counts all subsets once, without a distinguished member.
B: 6·2⁶ double-counts the choice of whether the distinguished member is present; it must be present.
C: Count pairs (S,x) with x∈S: choose x in 6 ways and the other members in 2⁵ ways, giving 192.
D: 60 counts only three-member committees with a captain, not all subset sizes.
C05. Four objects are chosen from five distinct red and four distinct blue objects. What is Σ(i=0 to 4) C(5,i)C(4,4−i)?
A. 81 B. 126 C. 120 D. 210
Answer: B
A: This is not the four-subset count; grouping by red count gives 1+20+60+40+5.
B: Vandermonde counts all four-subsets of the nine objects: C(9,4)=126.
C: 120 does not match the disjoint sum or the direct binomial count.
D: 210=C(10,4) would require ten distinct objects, while only nine exist.
C06. From six distinct people, how many ways choose a three-person committee with one of its members designated captain?
A. 20 B. 120 C. 18 D. 60
Answer: D
A: 20=C(6,3) chooses the committee but not its captain.
B: 20·6 permits a person outside the chosen committee to be captain.
C: 6·3 does not choose the other two members from the five noncaptains; the needed factor is C(5,2)=10.
D: Choose committee then captain: C(6,3)·3=60; or captain then two companions: 6·C(5,2)=60.
Sources and scope
This original lesson deepens combinatorial counting within Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. The official syllabus establishes the broad area; the MIT chapter provides institutional further-study support for counting methods. Examples, explanations and practice here are original. One lesson is not a claim of entire-subject mastery.
Sources opened and checked 2026-10-14.
Sign in to keep your progress. Sign in