Back to the full dot-point answer

NSWMaths Extension 1Quick questions

Combinatorics (ME-A1)

Quick questions on The pigeonhole principle: guaranteed coincidences in counting problems

14short Q&A pairs drawn directly from our worked dot-point answer. For full context and worked exam questions, read the parent dot-point page.

What is the pigeonhole principle (basic form)?
Show answer
If n+1n + 1 or more objects are placed into nn boxes, then at least one box contains at least 22 objects.
What is the generalised pigeonhole principle?
Show answer
If kn+1k n + 1 or more objects are placed into nn boxes, then at least one box contains at least k+1k + 1 objects.
What is strategy for applying it?
Show answer
1. Identify the objects (pigeons) and the categories (boxes). 2. Count the number of each.
What is limitations?
Show answer
The pigeonhole principle gives existence, not construction. You learn that two such objects exist, but not which ones.
What is with moderate numbers?
Show answer
Among any 367367 people, at least two share a birth date.
What is generalised form?
Show answer
Among any 2525 integers, at least 55 have the same remainder when divided by 66.
What is choosing boxes cleverly?
Show answer
Show that among any 55 integers, there must be two whose difference is divisible by 44.
What is sum identical?
Show answer
Show that among any 77 distinct integers from 11 to 1212, there are two whose difference is exactly 33 or whose sum is exactly 1515.
What is two values matching?
Show answer
Show that among any 1111 digits chosen from 00 to 99, two must be equal.
What is sums of subsets?
Show answer
Show that any set of 1010 distinct two-digit numbers contains two disjoint subsets with the same sum.
What is off-by-one in the bound?
Show answer
"n+1n + 1 or more" pigeons gives one box with ≥2\ge 2. "nn pigeons" does not.
What is generalised form sign confusion?
Show answer
kn+1k n + 1 pigeons gives ≥k+1\ge k + 1 in some box. knk n pigeons is not enough.
What is trying to construct?
Show answer
The principle is existence-only. Do not try to identify which box has the extras.
What is confusing pigeonhole with counting?
Show answer
Pigeonhole proves "at least one box has ≥k\ge k"; it does not count exactly how many. :::

All Maths Extension 1Q&A pages