Exercise · ZW-PIGEONHOLE-PRINCIPLE-009 · ★★★ Advanced
Seven numbers are chosen from the set \(\{1,2,\dots,12\}\). Which statement is always true?
Choose one option.
Show answer
- C. Two of them add to 13
Explanation
The pairs \(\{1,12\},\{2,11\},\dots,\{6,7\}\) are 6 boxes; choosing 7 numbers puts two in the same box and they add to 13. The others can fail: \(\{1,\dots,7\}\) has no sum 14 or difference 7, and \(\{1,\dots,6,8\}\) has no multiple of 7.
Review the concept: Pigeonhole principle
If \(n\) objects are placed in \(k\) boxes, some box holds at least \(\lceil n/k\rceil\) objects, and in particular two when \(n>k\).
\[\left\lceil \dfrac{n}{k}\right\rceil\]
More practice problems: pigeonhole principle
- ZW-PIGEONHOLE-PRINCIPLE-001 A group has 13 people. What can be stated with certainty about their birth months?
- ZW-PIGEONHOLE-PRINCIPLE-002 30 marbles are distributed into 4 boxes. What is the largest number that is guaranteed to be in som…
- ZW-PIGEONHOLE-PRINCIPLE-003 How many cards from a 52-card deck (4 suits) must be drawn at minimum to guarantee two of the same…
- ZW-PIGEONHOLE-PRINCIPLE-004 How many people are needed at minimum to guarantee that at least 9 share a birth month, with 12 mon…
- ZW-PIGEONHOLE-PRINCIPLE-005 100 people are grouped by birth month (12 months). At least how many are certain to share some mont…
- ZW-PIGEONHOLE-PRINCIPLE-006 How many integers must be chosen at minimum to guarantee two with the same remainder when divided b…
- ZW-PIGEONHOLE-PRINCIPLE-007 A drawer holds loose socks of 3 colours. Without looking, how many must be taken at minimum to guar…
- ZW-PIGEONHOLE-PRINCIPLE-008 A list has 1000 distinct Spanish words. Using 26 initial letters, how many words with the same init…