2000 USAMO Problems/Problem 4

From AoPSWiki

Problem

Find the smallest positive integer such that if squares of a 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 is the smallest such number. For , we can simply color any of the squares forming the top row and the left column, but excluding the top left corner square.

We now show that no configuration with no colored right triangles exists for . We call a row or column filled if all of its squares are colored. Then any of the remaining colored squares must share a column or row, respectively, with one of the colored squares in a filled row or column. These two squares, and any other square in the filled row or column, form a colored right triangle, giving us a contradiction. Hence, no filled row or column may exist.

Let be the number of columns with colored square. Then there are colored squares in the remaining columns, and in each of these columns that have a colored square must have at least two colored squares in them. These two colored squares will form a triangle with any other colored square in either of the rows containing the colored squares. Hence, each of the colored squares must be placed in different rows, but as there are only rows, the inequality holds. If , then each column only has colored square, leaving no place for the remaining , contradiction. If , then each of the rows has black square, leaving no place for the other , contradiction. Hence is the minimal value.

See also