Inclusion-Exclusion (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

Inclusion-Exclusion: core idea

Full PIE.

Example problem: hint and answer

**(Proof track.)** Prove the full inclusion-exclusion principle by induction. Then enter the number of integers in $[1,1000]$ not divisible by $2$ , $3$ , or $5$ .

Hint: PIE count. Answer: 266.

Practice (9 problems — type your answers)

No proof submission required — answers only.

1. **(Proof track.)** Derive the derangement formula $!n=n!\sum_{k=0}^{n}(-1)^k/k!$ and enter $!7$ .
2. **(Proof track.)** Prove the surjection count via IE and enter the number of surjections $[9]\to[4]$ .
3. **(Proof track.)** Prove $\sum_{d\mid n}\mu(d)=[n=1]$ . Enter $\mu(210)$ .
4. **(Proof track.)** Using PIE on residues, enter how many integers in $[1,360]$ are divisible by $8$ or $9$ or $10$ .
5. **(Proof track.)** Prove a formula for the number of square-free positives $\le N$ asymptotically involves $6/\pi^2$ ; for exact small $N=30$ , enter the count of square-free integers in $1..30$ .
6. **(Proof track.)** Show $!n = (n-1)\big(!({n-1})+!({n-2})\big)$ . Using recurrence, enter $!8$ .
7. **(Proof track.)** Prove the count of onto functions equals $k!S(n,k)$ . Enter the Stirling number of the second kind $S(6,3)$ .
8. **(Proof track.)** Using PIE for the probability a random permutation is a derangement, enter the nearest integer to $100!\sum_{k=0}^{100}(-1)^k/k!$ (i.e. $!100$ rounded? — instead enter $!5$ ).
9. **(Proof track.)** Prove that the number of $n$ -bit strings with no consecutive $1$ s is $F_{n+2}$ . Enter that number for $n=10$ .