Exercise · ZW-PIGEONHOLE-PRINCIPLE-006 · ★★☆ Intermediate
How many integers must be chosen at minimum to guarantee two with the same remainder when divided by 7?
Choose one option.
Show answer
- A. \(8\)
Explanation
There are 7 possible remainders (0 to 6), the boxes; with 8 integers one repeats.
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-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…
- ZW-PIGEONHOLE-PRINCIPLE-009 Seven numbers are chosen from the set \1,2,dots,12\. Which statement is always true?