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 "1976 USAMO Problems/Problem 1"
(→‎Solution 2)
 
(One intermediate revision by the same user not shown)
Line 41: Line 41:
  
  
 +
 +
==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> 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>
  
  

Latest revision as of 19:21, 23 November 2016

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 $4\times 7$ 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 $4\times 6$ 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 $3\times 7$ 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]


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 ${4}\choose{2}$, or $6$ 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]


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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1976_USAMO_Problems/Problem_1&oldid=81549"