Each of the 21 dots in the array below is to be colored with one of two colors. Prove that, no matter how the coloring is done, there will be four dots of the same color that form the vertices of a rectangle.
Solution 1 by David Burwell, Davison High School
A rectangle will appear any time any of the following patterns appear twice in the array, or appear along with the pattern that has three dots of the same color that it has two of.
After putting each of the above patterns only once, you have six columns. The seventh column will always form a rectangle, whichever pattern is chosen to fill it.
Solution 2 by David Zhang, Ann Arbor Huron High School
| Assume the 2 colors used are blue (b) and red (r). Then, there are 8 ways of assigning the 2 colors in a column. To satisfy NOT forming a rectangle, the first 6 columns must be used. For the 7th column, there are 3 choices: |  |
| Case 1: If an all blue column is used, 3 blue rectangles will be formed. |  |
| Case 2: If an all red column is used, 3 red rectangles will be formed. |  |
| Case 3: If a column is repeated, the 2 repeated columns will form a rectangle. |  |
In all three cases, there will be 4 vertices of the same color that form at least one rectangle.
Also proved by: Jeff Guo (Grosse Pointe South H.S.); Dana Harrison (Forest Hills Northern H. S.); Michael Vo (Midland H. S.); Ruvani Fonseka (Grosse Pointe North H.S.); Saranapoom Klomjit (Grand Rapids Ottawa Hills H.S.). A partial proof was submitted by Chase Schuler (Forest Hills Northern H.S.).