Session 6C
Pigeonhole principle
45-75 min - work through lesson notes, practice, and the MCQ check.
In progress
Account sync
Sign in to keep this session synced across devices.
Account sync disabled
Add Supabase environment variables to enable account sync. Progress is saved locally in this browser for now.
Session tips
- Finish the MCQ before marking complete.
- Check the answer outlines after trying on paper.
- Mark complete to update your certificate progress.
Lesson notes
- The pigeonhole principle is a simple idea with strong consequences: if you place more than n objects into n boxes, then some box contains at least two objects. In proof form, you identify what counts as "objects" and what counts as "boxes." For example, if the objects are 13 people and the boxes are the 12 months, at least two people share a birth month. This works because every person must belong to exactly one month box.
- The principle generalizes: if you distribute N objects among n boxes, some box contains at least ceil(N/n) objects. Many problems become pigeonhole once you choose the right grouping. A common pattern in number theory is using remainders as boxes. For example, among n+1 integers, two have the same remainder mod n, because there are only n possible remainders. The main challenge is not the logic, it's modeling the situation correctly.
Practice
- 1Among 13 people, at least two share a birth month.
- 2In any set of n + 1 integers, two have the same remainder mod n.
- 3Any 6 people include 3 mutual acquaintances or 3 mutual strangers (optional).
MCQ
'Among 13 people, at least two share a birth month' uses: