Pigeonhole Principle (AIME / USAJMO / AMO)

Proof-style AIME / USAJMO / AMO statements — develop a full argument; type only the final answer.

Proof track: treat each problem as a full olympiad writeup on paper. Here you only enter the final answer (integer or short expression).

Easy Medium Hard AIME / USAJMO / AMO

Pigeonhole Principle: core idea

Extremal writeups.

Example problem: hint and answer

**(Proof track.)** Prove the strong pigeonhole principle, then enter the minimal $n$ guaranteeing $5$ people share a birth month.

Hint: $4\cdot12+1$ . Answer: 49.

Practice (9 problems — type your answers)

No proof submission required — answers only.

1. **(Proof track.)** Prove Erdős–Szekeres: any sequence of more than $ab$ distinct numbers has an increasing subseq. of length $a+1$ or decreasing of length $b+1$ . Enter the guaranteed mono length for a sequence of $17$ distinct numbers (take $a=b=4$ ).
2. **(Proof track.)** Prove $R(3,3)=6$ with both upper and lower bounds. Enter $R(3,3)$ .
3. **(Proof track.)** Prove that any $(n+1)$ -subset of $\{1,\ldots,2n\}$ contains two coprime integers — or the multiple variant: any $(n+1)$ -subset contains one dividing another. For $n=8$ , enter the critical subset size $n+1$ .
4. **(Proof track.)** Using pigeonhole on residues, prove that among any $n$ integers there are two whose difference is divisible by $n-1$ under suitable hypotheses — concrete: among $11$ integers, enter the minimal guarantee for two congruent mod $10$ (how many needed?).
5. **(Proof track.)** Prove Dirichlet’s approximation theorem idea via pigeons: among $N+1$ multiples, enter how many fractional parts in $[0,1)$ force two within $1/N$ (the pigeon count is $N$ ). For $N=7$ , enter $N+1$ .
6. **(Proof track.)** Show that in any group of $6$ people, $3$ mutual acquaintances or $3$ mutual strangers. Enter the graph-theoretic Ramsey number used.
7. **(Proof track.)** Prove a canonical pigeon argument for the claim: any set of $n$ integers has a nonempty subset with sum divisible by $n$ . Enter the size of the partial-sum pigeon set used in the usual proof when $n=9$ (number of partial sums).
8. **(Proof track.)** Using pairs $\{k,n+1-k\}$ , prove the minimal size forcing two that sum to $n+1$ in $\{1,\ldots,n\}$ . For $n=10$ (sum to $11$ ), enter that minimal size.
9. **(Proof track.)** Prove the monochromatic Schur-type toy: among any $9$ two-colorings of edges of $K_6$ … skip — enter instead the minimal number of 2-colored edges of $K_5$ that still avoids mono triangles sometimes: the fact $R(3,3)>5$ means there exists a coloring on how many vertices?