Difference between revisions of "2011 USAMO Problems/Problem 2"
(Zeroing adjacent vertices and looking at how the opposites become winnable solves the problem) |
m (Added footer) |
||
Line 44: | Line 44: | ||
</cmath> | </cmath> | ||
Now our chosen vertex 0 is the only vertex with a non-zero value, and since <math>s</math> is invariant, that value is <math>s</math> as required. Since a vertex <math>i</math> with <math>r_i \equiv 0 \pmod 5</math> is winnable, and with <math>s = 2011 \not\equiv 0 \pmod 5</math> we always have a unique such vertex, we are done. | Now our chosen vertex 0 is the only vertex with a non-zero value, and since <math>s</math> is invariant, that value is <math>s</math> as required. Since a vertex <math>i</math> with <math>r_i \equiv 0 \pmod 5</math> is winnable, and with <math>s = 2011 \not\equiv 0 \pmod 5</math> we always have a unique such vertex, we are done. | ||
+ | |||
+ | ==See also== | ||
+ | {{USAMO newbox|year=2011|num-b=1|num-a=3}} |
Revision as of 10:37, 29 April 2011
Problem
An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an integer from each of the integers at two neighboring vertices and adding 2m to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 2011 and the other four vertices have the number 0. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.
Solution
Let be the field of positive residues modulo 5. We label the vertices of the pentagon clockwise with the residues 0, 1, 2, 3 and 4. For each let be the integer at vertex and let be defined as: Let . A move in the game consists of for some vertex and integer . We immediately see that is an invariant of the game. After our move the new value of is decreased by as a result of the change in the and terms. So does not change after a move at vertex .
For all we have:
Therefore, the form an arithmetic progression in with a difference of . Since is unchanged by a move at vertex , so are all the remaining as the differences are constant.
Provided , we see that the mapping is a bijection and exactly one vertex will have . As is an invariant, a winning vertex must have , since in the final state each with is zero. So, for , if a winning vertex exists, it is the unique vertex with .
Without loss of generality, it remains to show that if , then 0 must be a winning vertex. To prove this, we perform the following moves: We designate the new state . Since is an invariant, and , we now have , for some integer . Our final set of moves is: Now our chosen vertex 0 is the only vertex with a non-zero value, and since is invariant, that value is as required. Since a vertex with is winnable, and with we always have a unique such vertex, we are done.
See also
2011 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |