1994 USAMO Problems/Problem 2
Problem
The sides of a 
-gon are initially colored so that consecutive sides are red, blue, red, blue,..., red, blue, yellow. We make a sequence of modifications in the coloring, changing the color of one side at a time to one of the three given colors (red, blue, yellow), under the constraint that no two adjacent sides may be the same color. By making a sequence of such modifications, is it possible to arrive at the coloring in which consecutive sides
are red, blue, red, blue, red, blue,..., red, yellow, blue?
Solution
We proceed by representing the colors as numbers, i.e. Red = 0, Blue = 1, Yellow = 2. Thus, we start with some sequence 0101...012 and are trying to end up with the sequence 1010...0102. Generate a second sequence of terms by subtracting each term by the following term and taking it modulus 3, i.e. (1-0, 0-1, 1-0, 0-1, ... 0-1, 1-0, 0-2, 2-1) = 1212...2111 is the sequence generated using the start sequence. The sequence generated using the end sequence is (0-1, 1-0, 0-1, 1-0, ... 1-0, 0-1, 1-2, 2-0) = 2121...2122. Observe that the sum of terms generated by the start sequence is different from the sum of terms generated by the end sequence.
We must now prove that changing the color of a side does not change the sum of the generated sequence. We do this by noting that we can only change the color of a side if its adjacent sides have the same color as each other. Thus, changing a side does not change the sum of terms in the generated sequence, as the term generated by the changing side and the side to its left is simply the "negative" of the term generated by the changing side and the side to its right (i.e. 212 to 202 changes 12 to 21).
Since it is impossible to change the sum of terms in the generated sequence, and the sequences generated by the start and end sequences have two different sums, it is impossible to perform a series of such modifications that change the start sequence to the end sequence.
See Also
| 1994 USAMO (Problems • Resources) | ||
| Preceded by Problem 1 |
Followed by Problem 3 | |
| 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. 
