Difference between revisions of "1976 USAMO Problems/Problem 1"
(→Solution 2) |
|||
| Line 44: | Line 44: | ||
==Solution 2== | ==Solution 2== | ||
| − | We will prove the first part by the pigeonhole principle. To form a rectangle, two squares have in one column have to be colored the same color as the corresponding squares in another column. In the example given, the two second and third squares of the fourth and seventh columns are all white. When coloring this rectangle, every column can be entirely one color, have 3 squares be of one color, or have 2 squares be of one color. Coloring each column with two white squares and two black squares will minimize the number of squares, since a smaller fraction of the column is one color (if more than 2 squares in the same column are the same color, then there is more than one coloring in another column that can create a rectangle). There are <math>{4}\choose{2}</math>, or <math>6</math> | + | We will prove the first part by the pigeonhole principle. To form a rectangle, two squares have in one column have to be colored the same color as the corresponding squares in another column. In the example given, the two second and third squares of the fourth and seventh columns are all white. When coloring this rectangle, every column can be entirely one color, have 3 squares be of one color, or have 2 squares be of one color. Coloring each column with two white squares and two black squares will minimize the number of squares, since a smaller fraction of the column is one color (if more than 2 squares in the same column are the same color, then there is more than one coloring in another column that can create a rectangle). There are <math>{4}\choose{2}</math>, or <math>6</math> different ways a column can be colored with two white and two black squares. We need the same coloring in two different columns to create a rectangle, and this is guaranteed with 7 columns by the pigeonhole principle. |
For the second part, we can draw a rectangle with each column having a different coloring with 2 black and 2 white squares. One such rectangle is shown below: | For the second part, we can draw a rectangle with each column having a different coloring with 2 black and 2 white squares. One such rectangle is shown below: | ||
Latest revision as of 18:21, 23 November 2016
Contents
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 1
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)
Solution 2
We will prove the first part by the pigeonhole principle. To form a rectangle, two squares have in one column have to be colored the same color as the corresponding squares in another column. In the example given, the two second and third squares of the fourth and seventh columns are all white. When coloring this rectangle, every column can be entirely one color, have 3 squares be of one color, or have 2 squares be of one color. Coloring each column with two white squares and two black squares will minimize the number of squares, since a smaller fraction of the column is one color (if more than 2 squares in the same column are the same color, then there is more than one coloring in another column that can create a rectangle). There are 
, or 
different ways a column can be colored with two white and two black squares. We need the same coloring in two different columns to create a rectangle, and this is guaranteed with 7 columns by the pigeonhole principle.
For the second part, we can draw a rectangle with each column having a different coloring with 2 black and 2 white squares. One such rectangle is shown below:
![[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,3);fillsq(0,2); fillsq(1,3);fillsq(1,1); fillsq(2,3);fillsq(2,0); fillsq(3,2);fillsq(3,1); fillsq(4,2);fillsq(4,0); fillsq(5,1);fillsq(5,0); 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/8/b/a8bf55ca85cf9caaf58d74aa66809a1427fafbb5.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 | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
