Among any 5 integers, must two of them have the same remainder when divided by 4? Which answer best explains why?
ANo — there is no mathematical reason integers must share remainders
BNo — it depends on which specific integers are chosen; some sets of 5 integers have distinct remainders
CYes — there are only 4 possible remainders (0, 1, 2, 3) and 5 integers, so by the pigeonhole principle at least two must share a remainder
DYes — all integers eventually repeat their remainders when divided by 4, so coincidences are inevitable
The key insight is identifying the right 'holes': the 4 possible remainders mod 4 (0, 1, 2, 3). With 5 integers (pigeons) and only 4 remainder classes (holes), the pigeonhole principle guarantees a collision. Option B is wrong: it is impossible to choose 5 integers that all have distinct remainders mod 4 — there simply are not enough distinct remainders. This is not a probability claim but a certainty.
Question 2 Multiple Choice
A student says: 'The pigeonhole principle tells me that among 13 people, I can identify exactly which two share a birth month.' What is wrong with this claim?
AThe principle requires more than 13 people to guarantee a shared birth month
BThe principle only works when people are randomly selected, not in a fixed group
CThe principle guarantees that some two people share a birth month but gives no information about which two — it is a non-constructive existence result
DThe student is correct — with 13 people and 12 months, the shared month must be the most common month in that group
The pigeonhole principle is non-constructive: it proves existence without identifying a witness. It guarantees that a collision exists (some month is shared by at least two people) but says nothing about which month or which pair. This is what distinguishes it from constructive proofs that produce the actual colliding pair. Option D is especially tempting but wrong — we know some month is shared, but the principle does not tell us which one.
Question 3 True / False
The pigeonhole principle can be used to prove that a collision must exist without identifying which specific items collide.
TTrue
FFalse
Answer: True
Non-constructive existence proofs are a legitimate and powerful proof technique. The pigeonhole principle proves that some container must hold multiple items purely from a counting argument — without identifying the container or the items. This is a feature, not a limitation: in many applications (birthday attacks, graph theory, number theory), knowing that a collision must exist is all you need, even without knowing which one.
Question 4 True / False
The hardest part of applying the pigeonhole principle to a novel problem is the arithmetic — computing whether n+1 exceeds n.
TTrue
FFalse
Answer: False
The arithmetic is trivial once the setup is done. The hard part is creative setup: identifying what the 'pigeons' (objects) and 'holes' (categories) should be. For most non-trivial applications, this mapping is not given — you must invent it. The same collection of objects can be categorized in many different ways; only the right categorization makes the pigeonhole argument work. This creative identification step is what separates experienced problem-solvers from beginners.
Question 5 Short Answer
Why is the pigeonhole principle described as a 'non-constructive' existence proof, and why does that distinction matter in mathematics?
Think about your answer, then reveal below.
Model answer: A constructive proof exhibits the specific object claimed to exist — it builds or identifies the witness. A non-constructive proof like the pigeonhole principle proves existence by showing that non-existence leads to a contradiction (if every container had at most one item, there could be at most n items total — contradicting having n+1). The distinction matters because non-constructive proofs can establish facts about infinitely many cases at once, without being able to point to any specific case. In cryptography, complexity theory, and combinatorics, many impossibility results and existence theorems rely on non-constructive counting arguments precisely because no efficient construction of the witness is known.
The pigeonhole principle is the simplest and cleanest example of a non-constructive existence argument. Once internalized, it opens the door to more sophisticated non-constructive techniques in mathematics — Ramsey theory, probabilistic method, compactness arguments — all of which prove existence by ruling out universal non-existence.