Pigeonhole Principle (Hard)

Pigeonhole Principle: core idea

• 1. Among $5$ holes, pigeons to guarantee $4$ in one hole?

  Check

• 2. To ensure $4$ people with same residue mod $7$?

  Check

• 3. $R(3,3)=$?

  Check

• 4. Subset of $\{1,\ldots,10\}$ of size forcing a multiple pair — size?

  Check

• 5. Socks: $10$ black $+10$ white. Guarantee a pair?

  Check

• 6. Erdős–Szekeres: $n^2+1$ distinct numbers force mono subsequence length $n+1$. For $n=3$?

  Check

• 7. From $\{1..9\}$, size guaranteeing $x+y=10$?

  Check

• 8. Guarantee two with difference divisible by $5$ among $\{1..20\}$ — how many?

  Check

• 9. Any $2$-coloring of $K_6$ has mono triangle — this uses $R(3,3)=$?

  Check