Pigeonhole Principle and Invariants | Six Minutes: Waterloo Fermat Contest, Part 25

Six Minutes: Waterloo Fermat Contest, Part 25: Pigeonhole Principle and Invariants: Forced matches; then Invariants The pigeonhole principle forces a match whenever there are more items than boxes, and the contest skill is choosing the boxes to match the property you want. Build the worst case of one item per box, then one more item guarantees the pair. Then: An invariant is a quantity that no allowed move can change, and a goal that breaks one is impossible. This episode uses parity, coloring and remainders to settle reachability questions fast, including a full pile-of-stones worked example. Chapters 0:00 Introduction 0:20 The idea 1:05 How many to force it 1:29 Worked example 2:17 Trap 2:37 Recap 2:51 Invariants 3:04 What never changes 3:22 Parity and coloring 3:46 Remainders as invariants 4:06 Worked example 5:41 Trap 6:02 Recap 6:18 Thanks for watching Practice problems 1. From the integers 1 to 10, how many must you pick to be sure two of them differ by exactly 5? Answer: 6 (pairs 1–6, 2–7, 3–8, 4–9, 5–10 give 5 boxes; worst case 5, then one more). 2. A jar holds 20 candies in 6 flavors, and every flavor is present. How many candies must you take, without looking, to be sure two share a flavor? Answer: 7 (worst case one of each flavor, then one more). 3. A board starts with the number 4 written on it. Each move replaces the number n with either n + 6 or 3n. Can the number 2025 ever appear? Answer: No, because the number is always even (n + 6 and 3n both preserve evenness), and 2025 is odd. 4. Piles hold 9, 5 and 2 stones. A move takes one stone from each of two piles and adds two to the third. Can you reach 15, 1, 0? Answer: No. The total stays 16, which matches, but (a - b) mod 3 is invariant: start 9 - 5 = 4 = 1 mod 3, goal 15 - 1 = 14 = 2 mod 3. Different classes, so impossible. Six Minutes @SixMinuteClass: One technique, about six minutes. The narrator's voice is synthetic (computer-generated). Independent educational video. Not affiliated with or endorsed by the Centre for Education in Mathematics and Computing (CEMC) or the University of Waterloo. © 2026 Six Minutes · @SixMinuteClass