Pigeonhole and inclusion-exclusion questions are rarely lost because the arithmetic is difficult. They are lost at setup: one missing +1 in a guarantee problem, or one wrong sign in a three-set count.
Both tools become reliable when you ask the right first question. For pigeonhole, identify the objects, boxes, and forced occupancy. For inclusion-exclusion, identify the sets and count every overlap before combining them.
Pigeonhole principle, simple and generalized
The simple pigeonhole principle says that if n objects are placed into k boxes and n>k, at least one box contains at least two objects. Put 13 people into 12 birth-month boxes, for example, and some month must contain at least two people.
The generalized form says that some box contains at least ceil(n/k) objects. Put 30 objects into 4 boxes, for instance, and some box must hold at least ceil(30/4) = 8. This form gives a lower bound on the largest occupancy even when the distribution is as even as possible.
GATE often asks the inverse question: how many objects guarantee at least r objects in one of k boxes? The answer is:
k(r-1)+1
Why? With k(r-1) objects, it is still possible to put exactly r-1 objects in every box. No box has reached r. The next object has nowhere safe to go, so some box must reach r.
Words such as at least, guarantee, must, and minimum number required are your signal. First construct the largest arrangement that avoids the target, then add one.
Worked pigeonhole problem: three people in one birth month
Question: What is the smallest number of people needed to guarantee that at least three share a birth month?
There are k=12 boxes, one for each month. The target is r=3 people in a box.
The largest avoiding arrangement puts r-1=2 people in every month:
12 x 2 = 24 people.
This is a valid counterexample to 24 being sufficient. Two people may have birthdays in January, two in February, and so on through December, with no month containing three.
Now add one person:
12(3-1)+1 = 12(2)+1 = 24+1 = 25.
The twenty-fifth person must enter one of the 12 month boxes, each of which could already hold two in the worst case. That forces at least one month to contain three. Therefore 25 is both sufficient and minimal.
The order of this proof matters. Show that 24 can fail, then show that 25 must work. That proves the minimum, not merely a number that happens to work.
Inclusion-exclusion for two and three sets
When two properties overlap, adding their counts directly counts the intersection twice. Inclusion-exclusion corrects that duplication:
|A union B| = |A| + |B| - |A intersection B|
For three sets, the correction has one more layer:
|A union B union C| = |A| + |B| + |C| - |A intersection B| - |A intersection C| - |B intersection C| + |A intersection B intersection C|
Read the signs as a rhythm: add the singles, subtract the pairs, add the triple. The triple was included three times in the single counts and then removed three times in the pair counts, so it must be added once.
If the question asks for objects satisfying none of the properties, first find the union, then subtract it from the size of the universe. The union, intersection and complement operations these signs act on are set out in Set Theory and Relations for GATE.
Worked inclusion-exclusion problem: divisibility from 1 to 100
Count the integers from 1 through 100 that are divisible by 2, 3, or 5.
Let A contain multiples of 2, B multiples of 3, and C multiples of 5. For a divisor d, the count up to 100 is floor(100/d).
The single-set counts are:
|A|=floor(100/2)=50;
|B|=floor(100/3)=33;
|C|=floor(100/5)=20.
For an intersection, use the least common multiple. A number in both A and B is divisible by lcm(2,3)=6, not by 2 x 3 as an unexplained shortcut. Here the values happen to agree because 2 and 3 are coprime.
|A intersection B|=floor(100/6)=16;
|A intersection C|=floor(100/10)=10;
|B intersection C|=floor(100/15)=6;
|A intersection B intersection C|=floor(100/30)=3.
Substitute every value with its sign visible:
Stage | Running count |
Substitute all seven counts | 50+33+20-16-10-6+3 |
Group singles, pairs, triple | 103-32+3 |
|A union B union C| | 74 |
So 74 integers are divisible by at least one of 2, 3, and 5. The count divisible by none is:
100-74 = 26.
The Venn regions give an independent check. The triple region has 3. The pair-only regions are 16-3=13, 10-3=7, and 6-3=3. The single-only regions are A: 50-13-7-3=27; B: 33-13-3-3=14; and C: 20-7-3-3=7. Their sum is 27+14+7+13+7+3+3=74, which matches the formula.
Surjections and derangements are inclusion-exclusion in disguise
Two formulas can look like separate facts until you see the same add-subtract pattern inside them.
The number of onto functions from an m-element domain to an n-element codomain is:
sum from i=0 to n of (-1)^i C(n,i)(n-i)^m
Start with all n^m functions. Subtract functions that miss at least one codomain element, add back those that miss at least two, and continue. That is inclusion-exclusion over the events "codomain value j is unused."
Check the formula on a case small enough to count by hand. For m=3 and n=2 the sum gives C(2,0)(2)^3 - C(2,1)(1)^3 + C(2,2)(0)^3 = 8 - 2 + 0 = 6. Counting directly agrees: of the 2^3 = 8 functions from a three-element set to {a, b}, only the two constant functions miss a value, which leaves 6 onto functions.
The number of derangements of n objects is:
D(n)=n![1-1/1!+1/2!-1/3!+...+(-1)^n/n!]
Here the excluded events are "object j remains in its original position." The alternating 1/i! terms are that same choice count: C(n,i) ways to pick the i objects that stay fixed, times (n-i)! arrangements of the rest, divided by n! gives exactly 1/i!.
Check n=3. D(3) = 3![1 - 1 + 1/2 - 1/6] = 6(1/3) = 2, and the only two derangements of (1, 2, 3) are (2, 3, 1) and (3, 1, 2).
Traps that break the count
Stopping at k(r-1). That is the largest arrangement that can avoid r, not the number that guarantees r. Add one.
Forgetting the triple term. For three sets, the final triple intersection has a plus sign.
Multiplying set counts. Divisibility intersections are counted using the LCM. For non-coprime divisors, blindly multiplying the divisors is wrong.
Confusing at least with exactly. Pigeonhole proves a forced lower bound. An exactly-r question usually needs case counting and subtraction.
Using pair-only values in the formula. The standard pair intersections include the triple region. Keep the definitions consistent.
How GATE tests these counting tools
Expect minimum-number-to-guarantee problems, counts of integers up to N satisfying several divisibility conditions, and short questions on onto functions or derangements. The arithmetic is usually compact enough for a one-mark or two-mark question, but the setup decides everything.
GATE publishes a subject syllabus but no topic-wise mark weightage, so confirm the current Discrete Mathematics syllabus in the information brochure on the organising IIT's GATE portal instead of assuming a fixed split. Use the GATE preparation category for the wider study sequence.
Short version and next step
To guarantee r objects in one of k boxes, use k(r-1)+1 and justify the +1 with the worst avoiding arrangement. For three-set inclusion-exclusion, add singles, subtract pairs, and add the triple. For none, subtract the resulting union from the universe.
Now solve both examples again without the displayed arithmetic. Use the GATE Test Series for timed application, then move to the Discrete Mathematics set theory and relations MCQs. KnowledgeGate's question bank carries about 1,300 Discrete Mathematics questions for building this counting reflex.
