USAMO 2011 Problem #2
by KingSmasher3, Apr 3, 2013, 3:33 AM
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
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.
_______
Note that interchanging the order of the turns does not affect anything. Thus we can consider just the 5 distinct possible moves. Let
be the initial values of the 5 vertices, and let
be the total values of
directed at the five vertices. Consider the case where
is the vertex that reaches
We then get the equations,
![\[\begin{cases} 2m_2-m_1-m_3=-x_2 \\ 2m_3-m_2-m_4=-x_3 \\ 2m_4-m_3-m_5=-x_4 \\ 2m_5-m_4-m_1=-x_5\end{cases}\]](//latex.artofproblemsolving.com/2/4/4/2442db9c1eae03876c039e431386292ec31b4f59.png)
We have
is a multiple of
This means that for a set of
to exist,
must be a multiple of
Now note that
Therefore, all the
are different values mod 5, so there can be at most 1 vertex that reaches
for each arrangement.
Now it remains to prove that there always exists a set of
Without loss of generality let
be the vertex that reaches
Consider the following values of 
![\[\begin{cases}m_5=\frac{x_2+2x_3+3x_4-x_5}{5} \\ m_4=0 \\ m_3=\frac{-x_2-2x_3+2x_4+x_5}{5}\\ m_2=\frac{-2x_2+x_3+4x_4+2x_5}{5}\\ m_1=\frac{2x_2+4x_3+6x_4+3x_5}{5}\end{cases}\]](//latex.artofproblemsolving.com/7/6/d/76d903d5d250bd34ac122d5180593f301c784801.png)
There values are all integers considering
is. They satisfy the aforementioned equations and thus provide a valid way to reach the end position from any given arrangement. We are done.
Main Point(s): Once we have equations for the values of
try to find an equation relating the values so that we can single out just one vertex. In this situation, always try multiplying by different numbers and taking mod 5.



_______
Note that interchanging the order of the turns does not affect anything. Thus we can consider just the 5 distinct possible moves. Let





![\[\begin{cases} 2m_2-m_1-m_3=-x_2 \\ 2m_3-m_2-m_4=-x_3 \\ 2m_4-m_3-m_5=-x_4 \\ 2m_5-m_4-m_1=-x_5\end{cases}\]](http://latex.artofproblemsolving.com/2/4/4/2442db9c1eae03876c039e431386292ec31b4f59.png)
We have








Now it remains to prove that there always exists a set of




![\[\begin{cases}m_5=\frac{x_2+2x_3+3x_4-x_5}{5} \\ m_4=0 \\ m_3=\frac{-x_2-2x_3+2x_4+x_5}{5}\\ m_2=\frac{-2x_2+x_3+4x_4+2x_5}{5}\\ m_1=\frac{2x_2+4x_3+6x_4+3x_5}{5}\end{cases}\]](http://latex.artofproblemsolving.com/7/6/d/76d903d5d250bd34ac122d5180593f301c784801.png)
There values are all integers considering

Main Point(s): Once we have equations for the values of

This post has been edited 1 time. Last edited by KingSmasher3, Apr 3, 2013, 3:33 AM