1976 USAMO Problems/Problem 1
Problem
![[asy] void fillsq(int x, int y){ fill((x,y)--(x+1,y)--(x+1,y+1)--(x,y+1)--cycle, mediumgray); } int i; fillsq(1,0);fillsq(4,0);fillsq(6,0); fillsq(0,1);fillsq(1,1);fillsq(2,1);fillsq(4,1);fillsq(5,1); fillsq(0,2);fillsq(2,2);fillsq(4,2); fillsq(0,3);fillsq(1,3);fillsq(4,3);fillsq(5,3); for(i=0; i<=7; ++i){draw((i,0)--(i,4),black+0.5);} for(i=0; i<=4; ++i){draw((0,i)--(7,i),black+0.5);} draw((3,1)--(3,3)--(7,3)--(7,1)--cycle,black+1); [/asy]](http://latex.artofproblemsolving.com/b/b/0/bb023b115e30010d4f1daa300d792b67658733a4.png)
- (a) Suppose that each square of a
chessboard, as shown above, is colored either black or white. Prove that with any such coloring, the board must contain a rectangle (formed by the horizontal and vertical lines of the board such as the one outlined in the figure) whose four distinct unit corner squares are all of the same color. - (b) Exhibit a black-white coloring of a
board in which the four corner squares of every rectangle, as described above, are not all of the same color.
chessboard, as shown above, is colored either black or white. Prove that with any such coloring, the board must contain a rectangle (formed by the horizontal and vertical lines of the board such as the one outlined in the figure) whose four distinct unit corner squares are all of the same color.
board in which the four corner squares of every rectangle, as described above, are not all of the same color.Solution
There are many ways to prove the first part, we will show one.
Consider the first row. It contains at least four cells of the same color, say white. Pick any four such cells. Let's now consider these four columns only. If any of the remaining three rows contains two white cells in some of these columns, we are done. Otherwise, we have the following situation: three rows times four columns, and in each row there is at most one white cell. We can now pick any two rows and then find two columns such that all four cells where they intersect are black, and we are done. (Note that this proof in fact shows that already in a 
board there must be such a rectangle.)
For the second part, consider the board shown below. Its six columns contain the six different permutations of two white and two black squares. From this observation it is immediately obvious that no two columns agree on two cells of the same color.
![[asy] void fillsq(int x, int y){ fill((x,y)--(x+1,y)--(x+1,y+1)--(x,y+1)--cycle, mediumgray); } int i; fillsq(0,0);fillsq(0,1); fillsq(1,0);fillsq(1,2); fillsq(2,0);fillsq(2,3); fillsq(3,1);fillsq(3,2); fillsq(4,1);fillsq(4,3); fillsq(5,2);fillsq(5,3); for(i=0; i<=6; ++i){draw((i,0)--(i,4),black+0.5);} for(i=0; i<=4; ++i){draw((0,i)--(6,i),black+0.5);} [/asy]](http://latex.artofproblemsolving.com/a/c/a/acaf89391cebe9a1166f35b694b463cd00a719f8.png)
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
| 1976 USAMO (Problems • Resources) | ||
| Preceded by First Question |
Followed by Problem 2 | |
| 1 • 2 • 3 • 4 • 5 | ||
| All USAMO Problems and Solutions | ||
