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 $m$ 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 $m$ 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.
Problem
Source:
Tags: invariant, USA(J)MO, USAMO, algorithm, rotation, geometry, Hi
29.04.2011 00:54
label vertices a,b,c,d,e. let f_i for vertex i = value of that vertex. Let g_a= 1, g_b=2, g_c=3, g_d=4, g_e=0. Sum of f_i*g_i stays invariant mod 5.
29.04.2011 01:17
LastPrime wrote: label vertices a,b,c,d,e. let f_i for vertex i = value of that vertex. Let g_a= 1, g_b=2, g_c=3, g_d=4, g_e=0. Sum of f_i*g_i stays invariant mod 5. That's not sufficient; imo the hard part of the problem was showing that some winning position is reachable. (also amusingly this problem, chip-firing, has been my research project for the past (some number of) years... too bad I graduated? ) Generally it turns out that the "positions" (graph + numbers assigned to each vertex) can be split into a bunch of equivalence classes, and these equivalence classes form the "sandpile group"... in this case it has order 5.
29.04.2011 02:44
Do you think the graders will like it if I just showed a series of moves without explaining anything? I think a sequence of moves can take you to (2011 0 x 0 -x) (assume wlog that x is positive). Then if it's in the winning position the invariant defined in the first part means that x = 5k for some k. We can then take the moves (2011 0 5k 0 -x) (2011 -1 5k-1 0 -5k+2) (2012 0 5k-1 -2 -5k+2) (2008 0 5k+1 0 -5k+2) (2011 0 5k-5 0 -5k+5). Thus we always decrease by 5 until we get (2011 0 0 0 0). Unfortunately I didn't have time to do the last sequence during the test so I just bsed something. I hope I get some partial credit...
29.04.2011 03:19
I'll give a more elementary proof, what I did on it.
29.04.2011 04:53
A tedious but straightforward way is to set up a linear system of "transfers" and do elimination until you get to an equation with one side divisible by 5. From there you can prove the uniqueness by this divisibility and prove the existence by massive back-substitution and checking equalities.
29.04.2011 05:04
Ugh, I didn't know that we had to show that the ending position was reachable. I just showed that at most one position was a winnable one.
29.04.2011 05:10
29.04.2011 14:36
Edit: Oops, I didn't notice timwu wrote the same idea.
29.04.2011 21:00
james4l wrote:
A more complete write-up along these lines is now posted on the USAMO wiki. 2011 USAMO Problems/Problem 2
30.04.2011 03:27
However, I almost ran out of time writing my solution up, so I probably lost a point or two for clarity.
30.04.2011 18:55
I used Linear Algebra and 5-dimensional vector space...though I did not show sufficient evidence of the mod 5 stuff...I was kinda frantic for time, and decided to state it as trivial (even though I proved it once I got home, only to see that it was far from trivial). Probably only got 3 points for what I put.
01.05.2011 21:32
25.01.2012 19:32
$ r_{i}\equiv 4n_{i+1}+3n_{i+2}+2n_{i+3}+n_{i+4}\equiv\sum_{k\in\mathbb{Z}_{5}}(i-k)n_{k}\pmod 5. $ Can someone explain what motivated this invariant? (This is from AoPS Wiki, but a bunch of people here used expressions like this as well).
26.01.2012 04:28
My line of reasoning on the test was like "okay so let's try looking for an invariant since they're pretty good with this kind of problem" "hmm so we should use all 5 numbers in our invariant since they all matter" "i guess it's pretty natural to try multiplying each by a different constant and then taking it some mod" "well, mod 5 first would make sense" "hey it works!" I'm not the best person to explain this, but basically, invariants are pretty helpful for showing uniqueness. Since you need at least 5 different possible values of the invariant, taking it mod 5 makes sense.
11.02.2013 19:04
Okaiii....these are new elementary solutions by me for this problem (both uniqueless and offering a way which guarantees arriving to $(2011,0,0,0,0)$ on vertices of hexagon:
12.02.2013 16:14
Another way is to set up $5$ invariants: $2a+4b+1c+3d+0e=i_1$ $3a+0b+2c+4d+1e=i_2$ $4a+1b+3c+0d+2e=i_3$ $0a+2b+4c+1d+3e=i_4$ $1a+3b+0c+2d+4e=i_5$. Of course, as all of these are constant mod $5$ so we can win at at most one vertex. Any move actually decreases one of the $i_j$ by $5$ and either increases $i_{j-1}$ or $i_{j+1}$ by $5$, where the indices are mod $5$. WLOG originally that $i_1$ is $2$ mod $5$. The sum of the $i_j$ is fixed. We can make the set $(i_1,i_2,i_3,i_4,i_5)$ absolutely anything as long as the sum of the $i_j$ continues to be $2011$ mod $5$ and $i_j$ is $j+1$ mod $5$. Using these moves, we can get $i_1=2011$, $i_2=2011(2)$, $i_3=2011(3)$, $i_4=2011(4)$ from which we will have that $i_5=2011(1)$ and $a=2011$, $b=0$, $c=0$, $d=0$, $e=0$. This gives a more motivated way to construct the $4$ move solution.
08.06.2014 03:52
not_trig wrote: That's not sufficient; imo the hard part of the problem was showing that some winning position is reachable. Hmm IMO that was the easy part Like once you get to the point where you can see which vertex is the only winning one, the system is a natural thing to set up since the operations are all commutative. (To see that at most one vertex is winning, note that $a_1 + 2a_2 + 3a_3 + 4a_4 + 5a_5 \pmod 5$ is invariant.) Then you just slog through the algebra. I'll write up this in full here. Call the vertices $0$, $1$, $2$, $3$, $4$. Let $a_i$, $x_i$ denote the number initially at $i$ and $x_i$ denote $\sum m$ over all $m$ where vertex $i$ gains $2m$. WLOG the winning vertex is $0$, meaning $a_1 + 2a_2 + 3a_3 + 4a_4 \equiv 0 \pmod 5$. Moreover we want \begin{align*} 2011 &= a_0 + 2x_0 - x_2 - x_3 \\ 0 &= a_1 + 2x_1 - x_3 - x_4 \\ 0 &= a_2 + 2x_2 - x_4 - x_0 \\ 0 &= a_3 + 2x_3 - x_0 - x_1 \\ 0 &= a_4 + 2x_4 - x_1 - x_2. \end{align*}We can ignore the first equation since its the sum of the other four. Moreover, we can WLOG shift $x_0 \to 0$ by shifting each $x_i$ by a fixed amount. Then \[ x_4 = 2x_2 + a_2 \text{ and } x_1 = 2x_3 + a_3. \]We let $p$ and $q$ denote $x_2$ and $x_3$ (noting that $p, q \in \mathbb Z \implies x_1, x_4 \in \mathbb Z$). Anyways the system now expands as \[ 2p - 3q = 2a_3 + a_1 - a_2 \text{ and } 2q-3p = 2a_2 + a_4 - a_3 \]whence we have a two-var system, easy! We compute \[ p-q = \frac15 \left[ a_1 - 3a_2 + 3a_3 - a_4 \right]. \]This is an integer by the condition, whence so are $p$ and $q$, QED.
02.03.2015 09:46
This is pretty motivated. First note $(0,0,5,0,0) \rightarrow (0,3,-1,3,0) \rightarrow (1,1,1,1,1)$. Note that the reachable transitions form a group because they are generated by the $5$ "push $2$ things outward" moves and the product of these is $0$ so they are all invertible. Therefore, because we can go from a $5$ in any spot to all $1$'s, we can go back, and thus we can ignore $5$'s. It is also clear that we can go from any position to one in which there are at most $2$ places with nonzero numbers. Because these two places sum to $2011$, we can conclude that there are at most $5$ distinct equivalence classes. But the positions with $2011$ at each vertex are in different equivalence classes because we can number the spots with $0$,$1$, $2$, $3$, and $4$ and then the sum of the products of the numbering and the assigned integer at each spot is constant mod $5$ and respectively $0$, $1$, $2$, $3$, and $4$ for these positions. Therefore, there is exactly one vertex at which the game can be won as desired.
03.12.2015 08:17
Does this work? Can someone check it??
14.04.2022 17:59
07.10.2022 16:16
25.05.2023 05:34
Label the vertices $1,2,3,4,5.$ Let $a_i$ be the initial value of the number at vertex $i.$ Let $x_i$ be the sum of all $m$ where $2m$ is added to vertex $i.$ Claim: $a_1+2a_2+3a_3+4a_4+5a_5 \pmod{5}$ is invariant. Proof: At each step, the value changes by $2im-m(i+1)-m(i+3) \equiv 0 \pmod{5}.$ Since $a_1+2a_2+3a_3+4a_4+5a_5 \equiv 2011i \equiv i \pmod{5},$ it follows that for any initial assignment, the game can be won at at most one vertex. Without loss of generality, assume $a_1+2a_2+3a_3+4a_4+5a_5 \equiv 1 \pmod{5}.$ It remains to show that the game can be won at vertex $1.$ Then, we want to find $x_1,x_2,x_3,x_4,x_5$ such that \begin{align*} 2011 &= a_1+2x_1-x_3-x_4, \\ 0 &= a_2+2x_2-x_4-x_5, \\ 0 &= a_3+2x_3-x_1-x_4, \\ 0 &= a_4+2x_4-x_1-x_2, \\ 0 &= a_5 + 2x_5 - x_2-x_3. \end{align*}Note the first equation is irrelevant, since adding the latter four equations, we obtain \[0=a_2+a_3+a_4+a_5+x_3+x_4-2x_1 \Longleftrightarrow 2011 = a_1+2x_1-x_3-x_4.\]From here, we may set $x_1=0,$ since this is equivalent to shifting all the $x_i.$ Then, we have \begin{align*} 0&= a_2+2x_2-x_4-x_5, \\ 0&= a_3+2x_3-x_5, \\ 0&= a_4+2x_4-x_2, \\ 0&= a_5+2x_5-x_2-x_3. \end{align*}Write $x_5=a_3+2x_3, x_2=a_4+2x_4.$ Substituting into the two other equations gives $2x_3-3x_4=a_2+2a_4-a_3$ and $2x_4-3x_3=a_5+2a_3-a_4.$ Slog through algebra to obtain \[x_3-x_4=\frac{1}{5}(a_2-3a_3+3a_4-a_5).\]But recall $a_2+2a_2+3a_3+4a_4+5a_5 \equiv 1 \pmod{5},$ so $a_2+2a_3+3a_4+4a_5 \equiv 0 \pmod{5}.$ But this just so happens to mean that $a_2-3a_3+3a_4-a_5 \equiv 0 \pmod{5},$ so $x_3$ and $x_4$ are integers. Since we set $x_5=a_3+2x_3$ and $x_2=a_4+2x_4,$ they take on integer values as well, completing the proof.
08.10.2023 03:32
28.10.2023 02:05
Label the vertices $1,2,3,4,5$. Let $a_i$ be the initial value of the number at vertex $i.$ Let $x_i$ be the sum of all $m$ where $2m$ is added to vertex $i$. Notice that $a_1+2a_2+3a_3+4a_4+5a_5 \pmod{5}$ is invariant, which can be shown easily. Since $a_1+2a_2+3a_3+4a_4+5a_5 \equiv 2011i \equiv i \pmod{5},$ the game can be won at at most one vertex for any inital position. WLOG, assume $a_1+2a_2+3a_3+4a_4+5a_5 \equiv 1 \pmod{5}.$ It remains to show that the game can be won at vertex $1$. That is essentially equivalent to finding $x_i$ such that \begin{align*} 2011 &= a_1+2x_1-x_3-x_4, \\ 0 &= a_2+2x_2-x_4-x_5, \\ 0 &= a_3+2x_3-x_1-x_4, \\ 0 &= a_4+2x_4-x_1-x_2, \\ 0 &= a_5 + 2x_5 - x_2-x_3. \end{align*} Sum the latter four equations to get \[0=a_2+a_3+a_4+a_5+x_3+x_4-2x_1\] From here, set $x_1=0$, as this is equivalent to shifting all the $x_i.$ Then, we have \begin{align*} 0&= a_2+2x_2-x_4-x_5, \\ 0&= a_3+2x_3-x_5, \\ 0&= a_4+2x_4-x_2, \\ 0&= a_5+2x_5-x_2-x_3. \end{align*} Bash out some algebra and we get \[x_3-x_4=\frac{1}{5}(a_2-3a_3+3a_4-a_5).\] Recall however, that $a_1+2a_2+3a_3+4a_4+5a_5 \equiv 1 \pmod{5}$. This gives us $a_2+2a_3+3a_4+4a_5 \equiv 0 \pmod{5}$, implying that $x_3$ and $x_4$ are integers. This also implies $x_2$ and $x_5$ are integers, completing the proof. $\square$
28.10.2023 02:51
joshualiu315 wrote: Label the vertices $1,2,3,4,5$. Let $a_i$ be the initial value of the number at vertex $i.$ Let $x_i$ be the sum of all $m$ where $2m$ is added to vertex $i$. Notice that $a_1+2a_2+3a_3+4a_4+5a_5 \pmod{5}$ is invariant, which can be shown easily. Since $a_1+2a_2+3a_3+4a_4+5a_5 \equiv 2011i \equiv i \pmod{5},$ the game can be won at at most one vertex for any inital position. WLOG, assume $a_1+2a_2+3a_3+4a_4+5a_5 \equiv 1 \pmod{5}.$ It remains to show that the game can be won at vertex $1$. That is essentially equivalent to finding $x_i$ such that \begin{align*} 2011 &= a_1+2x_1-x_3-x_4, \\ 0 &= a_2+2x_2-x_4-x_5, \\ 0 &= a_3+2x_3-x_1-x_4, \\ 0 &= a_4+2x_4-x_1-x_2, \\ 0 &= a_5 + 2x_5 - x_2-x_3. \end{align*} Sum the latter four equations to get \[0=a_2+a_3+a_4+a_5+x_3+x_4-2x_1\] From here, set $x_1=0$, as this is equivalent to shifting all the $x_i.$ Then, we have \begin{align*} 0&= a_2+2x_2-x_4-x_5, \\ 0&= a_3+2x_3-x_5, \\ 0&= a_4+2x_4-x_2, \\ 0&= a_5+2x_5-x_2-x_3. \end{align*} Bash out some algebra and we get \[x_3-x_4=\frac{1}{5}(a_2-3a_3+3a_4-a_5).\] Recall however, that $a_1+2a_2+3a_3+4a_4+5a_5 \equiv 1 \pmod{5}$. This gives us $a_2+2a_3+3a_4+4a_5 \equiv 0 \pmod{5}$, implying that $x_3$ and $x_4$ are integers. This also implies $x_2$ and $x_5$ are integers, completing the proof. $\square$ imagine finishing entry combo
06.12.2023 18:00
Enjoyed Entry Combo at OTIS Solution(Storage) :Let $a_i$ be the number at vertex $i$ initially and $b_i$ = $\sum m$ over all $m$ where vertex $i$ $\longrightarrow$ $2m$. Now observe that $$ 2011 = a_0 + 2b_0 - b_2 - b_3 $$$$0 = a_1 + 2b_1 - b_3 - b_4 $$$$0 = a_2 + 2b_2 - b_4 - b_0 $$$$0= a_3 + 2b_3 - b_0 - b_1 $$$$0 = a_4 + 2b_4 - b_1 - b_2 $$has an integer solution. Adding all of them , we have $$ 5| a_1+2a_2+3a_3+4a_4$$ Now consider $$p+2q+3r+4s$$$$q+2r+3s+4t$$$$r+2s+3t+4p$$$$s+2t+3p+4q$$$$t+2p+3q+4r$$where $p,q,r,s,t$ are the residues of $a_1,a_2,a_3,a_4,a_0$ mod 5 respetivly. Now see that above 5 are consecutive numbers (mod 5) by PHP hence at least 1 of them must be divisible by 5. Hence for any choice of the initial integers, there is exactly one vertex at which the game can be won.
16.12.2023 23:46
Assign vertex $i$ with value $a_i$, and take indices modulo 5 when needed. Note that the game can be condensed to making a single move centered at each vertex. Denote this single $m$ value as $d_i$ for vertex $i$. Then winning at vertex $k$ is equivalent to \[a_i+2d_i-d_{i+2}-d_{i+3} = \begin{cases} 2011 & \text{ for } i=k \\ 0 & \text{ for } i \neq k \end{cases}\] having integer solutions for $d_i$. We can rearrange this system to $a_{i+1}+2a_{i+2}+3a_{i+3}+4a_{i+4} \equiv 0 \pmod 5$. We claim the left hand side is unique for each $i$ modulo 5. By contradiction, suppose the expressions for $i=x$ and $i=x+y$ are equivalent modulo 5. Manipulating, we get \[y(a_0+\ldots+a_4) \equiv y \equiv 0 \pmod 5.\] Thus $a_{i+1}+2a_{i+2}+3a_{i+3}+4a_{i+4} \pmod 5$ encompass the residues 0 through 4, so exactly 1 value is 0, implying exactly 1 vertex can win the game. We finish by getting a quintuple $(d_i)$ of integers to solve the system. $\blacksquare$
16.12.2023 23:53
Let us multiply the converse adjacent integers, which increase consecutively. Thus this number is a constant, no possible chnange in outcome possible. This is very easy!
09.01.2024 23:35
I hate this problem so much. I used a 39% hint from ARCH as well as a quick peek at 70% to figure out how to solve the system of equations. Let $x_1, x_2, x_3, x_4, x_5$ be the numbers on the vertices of the pentagon to start with, in clockwise order. Let $2y_1, 2y_2, \dots, 2y_5$ be the total value of the operations we perform at vertices $1,2,3,4,5,$ respectively. Then at the end of the process, the value of vertex $1$ is $x_1 + 2y_1 - y_3 - y_4,$ and similar expressions for the other vertices. If the game can be won at vertex $1,$ we then have the system of equations \begin{align*} x_1 + 2y_1 - y_3 - y_4 &= 2011 \\ x_2 + 2y_2 - y_4 - y_5 &= 0 \\ x_3 + 2y_3 - y_5 - y_1 &= 0 \\ x_4 + 2y_4 - y_1 - y_2 &= 0 \\ x_5 + 2y_5 - y_2 - y_3 &= 0. \end{align*}Two things: 1. We can get rid of the first equation (the messy one) because the sum of all of the equations is $0 = 0,$ a tautology. 2. We are left with $4$ equations and $5$ variables (the $y_i$), so this does not have a unique solution. Indeed, if $y_i$ works, then so does $y_i + r$ for any integer $r.$ Thus we can assume $y_2 = 0.$ We therefore reduce this system to the following: \begin{align*} x_2 - y_4 - y_5 &= 0 \\ x_3 + 2y_3 - y_5 - y_1 &= 0 \\ x_4 + 2y_4 - y_1 &= 0 \\ x_5 + 2y_5 - y_3 &= 0. \end{align*}The last two equations yield $y_1 = 2y_4 - x_4$ and $y_3 = 2y_5 - x_5.$ Plugging into the second equation, we get the new system of equations \begin{align*} y_4 + y_5 &= x_2 \\ -2y_4 + 3y_5 &= x_4 - x_3 - 2x_5. \end{align*}Solving for $y_5$ gives \[ y_5 = \frac{x_4 + 2x_2 - x_3 - 2x_5}{5}. \]In order for this to be an integer, we require $x_4 + 2x_2 - x_3 - 2x_5 \equiv 0 \pmod{5}.$ This is equivalent to $2x_2 + 4x_3 + 6x_4 + 8x_5 \equiv 0 \pmod{5}.$ Dividing both sides by $2,$ we get that the game can be won at vertex $1$ if and only if \[ \boxed{x_2 + 2x_3 + 3x_4 + 4x_5 \equiv 0 \pmod{5}}. \]We can use this to similarly determine that we can win at vertex $i$ if and only if \[ x_2 + 2x_3 + 3x_4 + 4x_5 \equiv i-1 \pmod{5}. \]Therefore, we just calculate $1+x_2 + 2x_3 + 3x_4 + 4x_5$ mod $5$, and that is the unique vertex where the game can be won.
14.02.2024 04:21
Let the starting values of each point be $a_0,a_1,a_2,a_3,a_4.$ If for a point, the total number added was $2m,$ let $x_i=m$ for $i \in {0,1,2,3,4}.$ Let the $a_0$ spot win. Note that we have \begin{align*} 2011 &= a_0 + 2x_0 - x_2 - x_3 \\ 0 &= a_1 + 2x_1 - x_3 - x_4 \\ 0 &= a_2 + 2x_2 - x_4 - x_0 \\ 0 &= a_3 + 2x_3 - x_0 - x_1 \\ 0 &= a_4 + 2x_4 - x_1 - x_2. \end{align*}WLOG, let $x_0=0$ by shifting all $x_i$ by a fixed amount. This gives us $$x_4 = 2x_2 + a_2 \text{ and } x_1 = 2x_3 + a_3$$and $$2x_2 - 3x_3 = 2a_3 + a_1 - a_2 \text{and} 2x_3-3x_2 = 2a_2 + a_4 - a_3.$$Manipulating, we get $$x_2-x_3=\frac{a_1-3a_2+3a_3-a_4}{5},$$which is obviously an integer. Thus, we have $a_1+2a_2+3a_3+4a_4 \equiv 0 \pmod 5.$ Note that this is \begin{align*} &= (a_1+a_2+a_3+a_4)+(a_2+a_3+a_4)+(a_3+a_4)+(a_4) \\ &= (1-a_0)+(1-a_0-a_1)+(1-a_0-a_1-a_2)+(1-a_0-a_1-a_2-a_3) \\ &= 4-4a_0-3a_1-2a_2-a_3 \\ &\equiv 0 \pmod 5 \\ \end{align*}because $a_0+a_1+a_2+a_3+a_4 \equiv 2011 \equiv 1 \pmod 5$ This means that $a_3+2a_2+3a_1+4a_0 \equiv 4 \pmod 5.$ Note that we can continue this to start for all $a_i$ as $\gcd(2,5)=1,$ $gcd(4,5)=1,$ and as there are $5$ $a_i,$ our $1$ solution always exists and is always unique.
06.05.2024 11:44
Let $x_1, x_2, x_3, x_4, x_5$ be the numbers on the vertices of the pentagon. Now we do the operation at vertex 1,2,3,4,5 respectively. Let $2y_1, 2y_2, 2y_3, 2y_4, 2y_5$ be the total value of the operations we do on each vertex $\Rightarrow$ we can make a system of equations of the values on each vetex. The value of vertex 1 is $x_1 + 2y_1 - y_3 - y_4$, so we build up the system in similar way. Let the game be won at vertex 1, so we have the system: $x_1 + 2y_1 - y_3 - y_4 = 2011$ $x_2 + 2y_2 - y_4 - y_5 = 0$ $x_3 + 2y_3 - y_5 - y_1 = 0$ $x_4 + 2y_4 - y_1 - y_2 = 0$ $x_5 + 2y_5 - y_2 - y_3 = 0$. Now we see that the first equation is useless, since we get that 0 = 0, also we now can assume $y_2 = 0$. So the system now looks like: $x_2 - y_4 - y_5 = 0$ $x_3 + 2y_3 - y_5 - y_1 = 0$ $x_4 + 2y_4 - y_1 = 0$ $x_5 + 2y_5 - y_3 = 0$ Now from the 3rd equation we get $y_1 = 2y_4 + x_4$. From the 4th equation we get $y_3 = 2y_5 + x_5$. From the 1st equation we get $x_2 = y_4 + y_5$. Plugging in $y_1$ and $y_3$, in the 2nd equation we have $-2y_4 + 3y_5 = x_4 - x_3 - 2x_5$. Now $y_4 = x_2 - y_5$, so we use that in the last equation we got and we have: $-2x_2 + 2y_5 + 3y_5 = x_4 - x_3 - 2x_5$ $\Rightarrow$ $5y_5 = 2x_2 - x_3 + x_4 - 2x_5$ $\Rightarrow$ $2x_2 - x_3 + x_4 - 2x_5 \equiv 0 \pmod{5}$ $\Rightarrow$ $2x_2 + 4x_3 + 6x_4 + 8x_5 \equiv 0 \pmod{5}$ $\Rightarrow$ $x_2 + 2x_3 + 3x_4 + 4x_5 \equiv 0 \pmod{5}$ $\Rightarrow$ if we win in vertex $x_i$, then $x_2 + 2x_3 + 3x_4 + 4x_5 \equiv i-1 \pmod{5}$ $\Rightarrow$ if we have $x_2 + 2x_3 + 3x_4 + 4x_5 + 1 \equiv i \pmod{5}$, then we had won the game at vertex $x_i$ $\Rightarrow$ this is the unique vertex in which the game can be won, so we are ready.
30.12.2024 16:37
I found a answer using polynomial close to @porkemon2. Observation: Label the vertices $0, 1, 2, 3, 4$ with $a_0, a_1, ..., a_4$. Then $(a_0, ..., a_4)$ can be transformed into $(a_0', ..., a_4')$ if and only if the polynomial $P(x) = a_0 + a_1x + ... + a_4x^4$ and $P'(x) = a_0' + a_1'x + ... + a_4'x^4$ satisfy the relation: $$ P'(x) = P(x) + (x^5-1) A(x) + (x^3 - x - 1) B(x) $$for some $A, B \in \mathbb{Z} [x]$. The proof of sufficiency is straightfoward; necessity is somewhat trickier. Denote by $P \sim P'$ if $P, P'$ satisfy the relation in "Observation," i.e., $P - P' \in <x^5-1, x^3-x-1>_\mathbb{Z}$. Then: Uniqueness. $2011x^i \sim 2011x^j$ iff $i \equiv j \mod 5$. Thus at most one of $2011, 2011x, 2011x^2, 2011x^3, 2011x^4$ is reachable. Proof: Notice that: $$ 2011(i-j) \equiv \frac{2011x^i - 2011x^j}{x-1}|_{x = 1} = (1+x+x^2+x^3+x^4)A(x) + (2x^2+2x+1)B(x)|_{x=1} = 5(A(1)+B(1)) $$where $A(1)+B(1) \in \mathbb{Z}$, giving $i \equiv j$. The rest is construction. I did not use polynomial for this, but I haven't seen anyone using exactly my method yet, so here we go: Construction. It is possible to move so two adjacent vertices are both $0$. Suppose the remaining three numbers, labeled $(a_0, a_1, a_2)$ are $(a, c, b)$. If $a=b$ we win by doing the move at $3, 4$ with $m=a=b$, then at $1$ again with $m=a=b$. Furthermore we have the sequence $$ (a, c, b, 0, 0) \mapsto (a-2, c, b+4, 0, -2) \mapsto (a-2, c-1, b+3, 0, 0) $$so it suffices if $a \equiv b \mod 5$. Working mod 5, we can always do the move: $$ (a, 1-a-b, b, 0, 0) \mapsto (0, 1-2a-b, b, 2a, 0)$$and so on. Thus is suffices to verify that the map $(a,b) \mapsto (1-2a-b, 2a)$ eventually maps anything to two equal numbers mod 5. This is indeed the case by calculation. Remark. The polynomial method might give a motivation of why we choose the invariant $a_1 + 2a_2 + 3a_3 + 4a_4$ mod $5$, as the key invariant of the polynomial is $\frac{P(x)-P'(x)}{x-1} |_{x=1}$ or equivalently its derivative evaluated at $x=1$, but taking the derivative since $(x^n)' = nx^{n-1}$ gives a similar formula.
12.01.2025 01:28
This problem is really unenjoyable to solve and is basically solving systems of equations on steroids. Used 0% hint to set up equations (which IMO the variables aren't trivial to come up with). Label the vertices $a, b, c, d, e$ and the values centered at each vertice $v, w, x, y, z$ respectively. We seek integer solutions to \begin{align*} 2011 &= a+2v-x-y \\ y+z &= b+2w \\ z+v &= c+2x \\ v+w &= d+2y \\ w+v &= e+2z \end{align*}We now need to solve this. We can treat $v$ as a constant and express $w, x, y, z$ each in terms of $a, b, c, d, e, v$ (in fact we can eliminate $a$ here as well from $a+b+c+d+e=2011$ as the sum is invariant). We have $v = \frac{b+c+d+e+x+y}{2}$ and can move the vairables to the left: \begin{align*} y+z-2w &= b \\ z-2x &= c - v \\ w - 2y &= d - v \\ w+x-2z &= e \end{align*}4 variables in four equations? Lets go !!!!! First kill $z$ from everything: \begin{align*} y-2w+2x &= b - c + v \\ w-2y &= d - v \\ w-3x &= 2c-2v+e \end{align*}Then we kill $y$ to get: \begin{align*} 4x - 3w &= 2b-2c+d+v \\ w-3x &= 2c-2v+e \end{align*}To obtain $x = \frac{5v-4c-3e-2b-d}{5}$. Plug and chug back in to get: \begin{align*} w &= \frac15 \left( -6b-2c-3d-4e+5v \right) \\ x &= \frac15 \left( -2b-4c-d-3e+5v \right) \\ y &= \frac15 \left( -3b-c-4d-2e+5v \right) \\ z &= \frac15 \left( -4b-3c-2d-6e+5v \right) \end{align*}Therefore, there being an integer solution reduces to $b+2c+3d+4e \equiv 0 \pmod{5}$ as the others are just cyclic versions of this mod 5. In other words, we need $b+2c \equiv e + 2d \pmod{5}$. We wish to show that two or more vertices cannot satisfy this. Assume FTSOC, that $b$ also satisfies this. Then we have $a+2e \equiv c + 2d \pmod{5}$. But adding these two up and rearranigng gives $a+b+c+d+e \equiv 0 \pmod{5}$, impossible using the miraculous identity $2011 \not \equiv 1 \pmod{5}$ . If $c$ was also possible, then we have $b+2a \equiv d+2e \pmod{5}$. Adding them up and multiplying by $3$ gives us another contradiction.
16.01.2025 14:32
Storage (Albeit less calculative proof I guess): Let $a_0, a_1, \cdots, a_4$ denote the numbers of the pentagon, in the order. Consider $I\equiv a_1 + 2 a_2 + 3 a_3 + 4a _4 \pmod 5$ with $0\le I \le 4$. Note that $I$ is invariant under any such operation. If $I = k$ for $k \neq 0$, then relabel the vertices as $b_0, \cdots, b_4$ with the former $k$th vertex as the latter $0$th vertex, which would turn $I' \equiv 0 \pmod 5$. Thus, WLOG assume $I \equiv 0 \pmod 5$. We will prove that the $0$th vertex is the only possible winning vertex. Note that, if we have vertex $k$ to be the winning vertex, then: $I \equiv k \equiv 0 \pmod p$. Thus, $k=0$ is the winning vertex, if it is possible. We will show that its indeed possible. Note that: $\sum a_i = 2011$ and the sum is invariant under any move. Now, play a move if necessary to make $a_0 = 2011$. Consider the following set of moves (notation: $(m, k)$ means add $2m$ to $a_k$ and subtract $m$ from $a_{k-2}$ and $a_{k+2}$: - $(a_1, 3)$ and $(-a_1, 4)$ results to $(2011, b_2, b_3, b_4)$. - $(-b_4, 4)$ and $(-b_4, 2)$ and $(b_, 3)$ results to $(2011, 0, c_3, c_4, 0)$. Note that: $c_3+c_4=0$. Also $I \equiv 0 \pmod 5$ implies $c_3 \equiv c_4 \equiv 0 \pmod 5$. The following claim finishes the problem: Claim: $(k, 0, 5, -5, 0)$ can reach $(k, 0, 0, 0, 0)$ for any $k \in \mathbb N$. Proof: Notice that: $$(k, 0, 5, -5, 0) \to (k+2, 0, 1, -5, 2) \to (k, -2, 1, -1, 2) \to (k-2, -2, 2, 0, 2) \to (k, -2, -2, 0, 4) \to (k, 0, 0, 0, 0).$$ Thus, we are done.