Pigeonhole Principle

• The simple but powerful idea: if you place more items into fewer boxes than items, at least one box must hold more than one item.
• The generalised pigeonhole principle: with n items in k boxes, some box holds at least ⌈n/k⌉ items (ceiling of n/k).
• How to spot a "hidden pigeonhole" in a problem that doesn't look like a counting problem at all (a classic olympiad move).

1. Basic pigeonhole — if n+1 or more objects are placed into n boxes, at least one box contains 2 or more objects.
2. Generalised pigeonhole — if n objects go into k boxes, some box has at least ⌈n/k⌉ objects. For example, 25 objects into 4 boxes forces some box to hold at least ⌈25/4⌉ = 7.
3. Choosing the "boxes" cleverly — the hard part is rarely the principle itself; it's deciding what to call a "box". Remainders mod n, sums of pairs, or coordinates on a grid are common disguises.
4. Existence, not identity — pigeonhole only proves that some box must be crowded — it never tells you which one. That's fine for existence proofs.

Show that among any 13 people, at least two share the same birth month.

Step 1 — the "boxes" are the 12 months of the year
Step 2 — the "objects" are the 13 people, each placed into the box matching their birth month
Step 3 — 13 objects into 12 boxes means 13 > 12, so by pigeonhole at least one box has ≥ 2 people
Answer — yes, at least two of the 13 people must share a birth month

• Confusing "at least one box has 2+" with "every box has 2+" — pigeonhole guarantees only that some box is crowded.
• Forgetting to use the ceiling in the generalised version — ⌈n/k⌉ rounds up, so 25 objects in 4 boxes gives 7, not 6.25 rounded down.
• Not identifying the right "boxes" — many problems require creativity (e.g. remainders mod n as boxes) before pigeonhole becomes obvious.

• Among any 5 integers, show that at least two have the same remainder when divided by 4. (5 integers, 4 possible remainders (0,1,2,3) → pigeonhole with n=5, k=4.)
• If 100 pigeons are placed in 9 pigeonholes, what is the minimum number that must be in the most crowded hole? (⌈100/9⌉ = 12.)
• Among any 3 integers chosen from 1 to 6, must two of them differ by at most 2? Explain using boxes {1,2,3} and {4,5,6}. (Not necessarily two boxes forces this directly — try boxes {1,2},{3,4},{5,6}: 3 integers into 3 boxes doesn't force a repeat; the useful pigeonhole here needs a sharper box choice — this is a great discussion/AI Mentor question rather than a one-line answer.)

Open the Practice tab for graded questions on the Pigeonhole Principle.

• Box-and-ball simulator: drag a variable number of balls into a variable number of boxes and watch the "forced crowding" appear live as the ball count crosses the box count.
• Mirror / body / home activity: with family or classmates, test the birthday-month pigeonhole claim for real — collect birth months of 13+ people and check.
• Voice or text reflection with AI Mentor: explain why, in any group of 367 people, at least two must share a birthday (including leap years).

• "Explain the pigeonhole principle to a Class 6 student using socks in a drawer or pencils in pencil boxes."
• "What is one common mistake students make when they can't find the right 'boxes' in a pigeonhole problem, and how would you catch yourself making it?"
• Stretch: "How does this connect to hashing collisions in computer science or seat allocation in a packed train compartment?"

• Complete the core practice + one extension activity (photo, table, short reflection, or mini-project) for base XP + topic badge.
• 5-7 day streak or family discussion note = multiplier + visible artifact in parent/principal dashboard.
• Best real-world application stories (anonymised) featured on class or national leaderboard.

• One hands-on project or measurement using the Drishti kit or household items that makes the concept physical.
• Direct link to at least one Future Skill track (Money Management, Green Tech, Cyber Defenders, Micro-Entrepreneurship, AI Mastery, Sustainable Living, Personality Development).
• Coding extension where relevant (simple script, simulation, or data logging).

This material emphasises experiential "learning by doing", competency (apply/create/analyse), vocational exposure, critical thinking, and multidisciplinary connections. Designed to feed live worlds, AI Mentor (with memory), gamification, robotics, parent analytics, and future skills — not just exam prep.

Portfolio Evidence Idea: Your photo/table/reflection/project + one sentence on "How this helps me in real life or a possible future path."

Open the Practice tab for aligned questions (easy/medium/hard + case-based) with full AI scaffolding.

See curriculum for cross-links and the full future-skills/robotics chapters.