View source

== 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>

* (a) Suppose that each square of a <math>4\times 7</math> chessboard, as shown above, is colored either black or white. Prove that with <i>any</i> 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 <math>4\times 6</math> 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 <math>3\times 7</math> 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>

== See also ==
{{USAMO box|year=1976|before=First Question|num-a=2}}

[[Category:Olympiad Combinatorics Problems]]