Numbers and arithmetic · 4 of 4 Advanced
Pigeonhole principle
Use the pigeonhole principle to show that a value must repeat, to bound how long a loop can run before it does, and to find the repeat.
- Pigeonhole principle The general and strong forms, with classic examples such as shared birthdays and hair counts, and the infinite version. en.wikipedia.org (opens in a new tab)
- Introduction to Functional Graphs Processes where each state has exactly one next state: why they always end in a cycle, and how to find the cycle and skip ahead many steps. usaco.guide (opens in a new tab)
- Tortoise and Hare Algorithm (Linked List cycle detection) Floyd’s cycle detection, the linear-time method with constant memory that also solves Find the Duplicate Number. cp-algorithms.com (opens in a new tab)