View source

== Problem ==
Find the smallest positive [[integer]] <math>n</math> such that if <math>n</math> squares of a <math>1000 \times 1000</math> 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 <math>n = 1999</math> is the smallest such number. For <math>n \le 1998</math>, we can simply color any of the <math>1998</math> squares forming the top row and the left column, but excluding the top left corner square.

<center><asy>
for(int i = 0; i < 10; ++i){
 for(int j = 0; j < 10; ++j){
  if((i == 0 || j == 9) && !(j-i == 9)) fill(shift(i,j)*unitsquare,rgb(0.3,0.3,0.3));
  else draw(shift(i,j)*unitsquare);
 }
}
</asy></center>

We now show that no configuration with no colored right triangles exists for <math>n = 1999</math>. We call a row or column ''filled'' if all <math>1000</math> of its squares are colored. Then any of the remaining <math>999</math> 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 <math>m</math> be the number of columns with <math>1</math> colored square. Then there are <math>1999-m</math> colored squares in the remaining columns, and in each of these <math>< 1999-m</math> 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 <math>1999-m</math> colored squares must be placed in different rows, but as there are only <math>1000</math> rows, the inequality <math>1999 - m \le 1000 \Longrightarrow m \ge 999</math> holds. If <math>m = 1000</math>, then each column only has <math>1</math> colored square, leaving no place for the remaining <math>999</math>, contradiction. If <math>m = 999</math>, then each of the <math>1000</math> rows has <math>1</math> black square, leaving no place for the other <math>999</math>, contradiction. Hence <math>n = \boxed{1999}</math> is the minimal value. 

== See also ==
{{USAMO newbox|year=2000|num-b=3|num-a=5}}

[[Category:Olympiad Combinatorics Problems]]