Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2000 USAMO Problems/Problem 4"

(solution)
 
m
Line 18: Line 18:
 
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.  
 
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 ==
+
== See Also ==
 
{{USAMO newbox|year=2000|num-b=3|num-a=5}}
 
{{USAMO newbox|year=2000|num-b=3|num-a=5}}
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Revision as of 07:24, 16 September 2012

Problem

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$ is the smallest such number. For $n \le 1998$, we can simply color any of the $1998$ 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]

We now show that no configuration with no colored right triangles exists for $n = 1999$. We call a row or column filled if all $1000$ of its squares are colored. Then any of the remaining $999$ 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 $m$ be the number of columns with $1$ colored square. Then there are $1999-m$ colored squares in the remaining columns, and in each of these $< 1999-m$ 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 $1999-m$ colored squares must be placed in different rows, but as there are only $1000$ rows, the inequality $1999 - m \le 1000 \Longrightarrow m \ge 999$ holds. If $m = 1000$, then each column only has $1$ colored square, leaving no place for the remaining $999$, contradiction. If $m = 999$, then each of the $1000$ rows has $1$ black square, leaving no place for the other $999$, contradiction. Hence $n = \boxed{1999}$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_USAMO_Problems/Problem_4&oldid=48369"