Big Board. Topic: Combinatorics. Level: Olympiad.

Problem: (2000 USAMO - #4) Find the smallest positive integer n such that if n squares of a $1000 \times 1000$ chessboard are colored, then there will exist three colored squares whose centers form a right triangle with sides parallel to the edges of the board.

Solution: We claim that $n = 1999$.

Suppose there are $1999$ colored squares on the board. On each row, let the colored square furthest to the left be the "main" square of the row. Let any other colored squares be "repeat" squares. If $x$ rows have colored squares, then there are $x$ main squares and $1999-x$ repeat squares.

Let the colored square furthest to the left be in the $y$th row. Then all repeat squares must exist in the columns to the right of $y$, of which there are $1000-y$.

Let $z$ be the number of columns with repeat squares. If $ z < 1999-x$, by the Pigeonhole Principle we must have at least two repeat squares $A$ and $B$ in the same column. But take a main square $C$ in the same row as $A$ or $B$ and we have $ABC$ a triangle. Contradiction.

Therefore $z \ge 1999-x$. But we also have $z \le 1000-y \le 999 \le 1999-x$, so the only case we have left is $z = 999 = 1999-x$. Then all rows have colored squares, the first column has a main square, and all of the other $999$ columns have repeat squares. If all the main squares are in the first column, we make a triangle with any of the repeat squares. So we must have some main squares in the $999$ remaining rows. Let $A$ be a main square not in the first column. We know there exists a repeat square $B$ in the same column as $A$. But then there is a main square $C$ in the same row as $B$, which means $ABC$ again forms a triangle. Contradiction.

Therefore $n = 1999$ has no coloring. The coloring for $n = 1998$ is the lower $999$ squares in the first column and the rightmost $999$ squares in the first row. Hence our answer is $n = 1999$. QED.