Difference between revisions of "2000 USAMO Problems/Problem 4"
m |
|||
Line 22: | Line 22: | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 13:37, 4 July 2013
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.
![[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]](http://latex.artofproblemsolving.com/3/b/e/3be222417f4b1d5d32b8210ee0c3849714c5672a.png)
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
2000 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.