Difference between revisions of "1976 USAMO Problems/Problem 1"
Line 17: | Line 17: | ||
* (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. | * (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 == | + | == Solution 1== |
There are many ways to prove the first part, we will show one. | There are many ways to prove the first part, we will show one. |
Revision as of 18:58, 23 November 2016
Problem
- (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.
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.
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.