Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2011 USAMO Problems/Problem 2"

(Created page with '==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 intege…')
 
(→‎Solution)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
==Problem==
 
==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 <math>m</math> from each of the integers at two neighboring vertices and adding <math>2m</math> to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount <math>m</math> 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.
+
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 <math>m</math> 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 <math>m</math> 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 <math>\mathbb{F}_5</math> 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 <math>i \in \mathbb{F}_5</math> let <math>n_i</math> be the integer at vertex <math>i</math> and let <math>r_i \in \mathbb{F}_5</math> be defined as:
 +
<cmath>
 +
r_i
 +
  \equiv 4n_{i+1} + 3n_{i+2} + 2n_{i+3} + n_{i+4}
 +
  \equiv \sum_{k\in\mathbb{F}_5}(i-k)n_k \pmod 5.
 +
</cmath>
 +
Let <math>s = \sum_{i\in\mathbb{F}_5} n_i</math>. A move in the game consists of
 +
<cmath>
 +
(n_i, n_{i+1}, n_{i+2}, n_{i+3}, n_{i+4}) \mapsto (n_i + 2m, n_{i+1}, n_{i+2} - m, n_{i+3} - m, n_{i+4})
 +
</cmath>
 +
for some vertex <math>i \in \mathbb{F}_5</math> and integer <math>m</math>. We immediately see that <math>s</math> is an invariant of the game. After our move the new value of <math>r_i</math> is decreased by <math>3m + 2m \equiv 0 \pmod 5</math> as a result of the change in the <math>3n_{i+2}</math> and <math>2n_{i+3}</math> terms. So <math>r_i</math> does not change after a move at vertex <math>i</math>.
 +
 
 +
For all <math>i \in \mathbb{F}_5</math> we have:
 +
<cmath>
 +
r_{i+1} - r_i
 +
  \equiv \sum_{k\in\mathbb{F}_5} ((i+1-k)n_k - (i-k)n_k)
 +
  \equiv \sum_{k\in\mathbb{F}_5} n_k \equiv s \pmod 5.
 +
</cmath>
 +
 
 +
Therefore, the <math>r_i</math> form an arithmetic progression in <math>\mathbb{F}_5</math> with a difference of <math>s</math>. Since <math>r_k</math> is unchanged by a move at vertex <math>k</math>, so are all the remaining <math>r_i</math> as the differences are constant.
 +
 
 +
Provided <math>s \not\equiv 0 \pmod 5</math>, we see that the mapping <math>i \mapsto r_i</math> is a bijection <math>\mathbb{F}_5 \to \mathbb{F}_5</math> and exactly one vertex will have <math>r_i \equiv 0 \pmod 5</math>. As <math>r_i</math> is an invariant, a winning vertex must have <math>r_i \equiv 0</math>, since in the final state each <math>n_k</math> with <math>k \ne i</math> is zero. So, for <math>s \not\equiv 0 \pmod 5</math>, if a winning vertex exists, it is the unique vertex with <math>r_i \equiv 0</math>.
 +
 
 +
Without loss of generality, it remains to show that if <math>r_0 \equiv 0 \pmod 5</math>, then 0 must be a winning vertex. To prove this, we perform the following moves:
 +
<cmath>
 +
\begin{align*}
 +
(n_0, n_1, n_2, n_3, n_4) &\mapsto (n_0-n_1, 0, n_2, n_3 + 2n_1, n_4), & (i, m) &= (3, n_1) \\
 +
&\mapsto (n_0-n_1-n_4, 0, n_2+2n_4, n_3 +2n_1, 0) & (i, m) &= (2, n_4)
 +
\end{align*}
 +
</cmath>
 +
We designate the new state <math>(n'_0, 0, n'_2, n'_3, 0)</math>. Since <math>r_0 \equiv 0</math> is an invariant, and <math>n'_1 = n'_4 = 0</math>, we now have <math>r_0 \equiv n'_3 - n'_2 = 5p</math>, for some integer <math>p</math>. Our final set of moves is:
 +
<cmath>
 +
\begin{align*}
 +
(n'_0, 0, n'_2, n'_3, 0) &\mapsto (n'_0+p, p, n'_2, n'_3 - 2p, 0), & (i, m) &= (3, -p)\\
 +
&\mapsto (n'_0+p, 0, n'_2-p, n'_3 - 2p, 2p), & (i, m) &= (4, p) \\
 +
&\mapsto (n'_0-p, 0, n'_2+3p, n'_3 - 2p, 0), & (i, m) &= (2, 2p)\\
 +
&\mapsto (n'_0+2n'_2 + 5p, 0, 0, n'_3-n'_2 - 5p = 0, 0) & (i, m) &= (0, n'_2 + 3p)
 +
\end{align*}
 +
</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.
 +
 
 +
{{MAA Notice}}
 +
 
 +
==See also==
 +
*[[USAMO Problems and Solutions]]
 +
 
 +
{{USAMO newbox|year=2011|num-b=1|num-a=3}}

Latest revision as of 01:36, 21 April 2015

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 $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.

Solution

Let $\mathbb{F}_5$ 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 $i \in \mathbb{F}_5$ let $n_i$ be the integer at vertex $i$ and let $r_i \in \mathbb{F}_5$ be defined as: \[r_i \equiv 4n_{i+1} + 3n_{i+2} + 2n_{i+3} + n_{i+4} \equiv \sum_{k\in\mathbb{F}_5}(i-k)n_k \pmod 5.\] Let $s = \sum_{i\in\mathbb{F}_5} n_i$. A move in the game consists of \[(n_i, n_{i+1}, n_{i+2}, n_{i+3}, n_{i+4}) \mapsto (n_i + 2m, n_{i+1}, n_{i+2} - m, n_{i+3} - m, n_{i+4})\] for some vertex $i \in \mathbb{F}_5$ and integer $m$. We immediately see that $s$ is an invariant of the game. After our move the new value of $r_i$ is decreased by $3m + 2m \equiv 0 \pmod 5$ as a result of the change in the $3n_{i+2}$ and $2n_{i+3}$ terms. So $r_i$ does not change after a move at vertex $i$.

For all $i \in \mathbb{F}_5$ we have: \[r_{i+1} - r_i \equiv \sum_{k\in\mathbb{F}_5} ((i+1-k)n_k - (i-k)n_k) \equiv \sum_{k\in\mathbb{F}_5} n_k \equiv s \pmod 5.\]

Therefore, the $r_i$ form an arithmetic progression in $\mathbb{F}_5$ with a difference of $s$. Since $r_k$ is unchanged by a move at vertex $k$, so are all the remaining $r_i$ as the differences are constant.

Provided $s \not\equiv 0 \pmod 5$, we see that the mapping $i \mapsto r_i$ is a bijection $\mathbb{F}_5 \to \mathbb{F}_5$ and exactly one vertex will have $r_i \equiv 0 \pmod 5$. As $r_i$ is an invariant, a winning vertex must have $r_i \equiv 0$, since in the final state each $n_k$ with $k \ne i$ is zero. So, for $s \not\equiv 0 \pmod 5$, if a winning vertex exists, it is the unique vertex with $r_i \equiv 0$.

Without loss of generality, it remains to show that if $r_0 \equiv 0 \pmod 5$, then 0 must be a winning vertex. To prove this, we perform the following moves: \begin{align*} (n_0, n_1, n_2, n_3, n_4) &\mapsto (n_0-n_1, 0, n_2, n_3 + 2n_1, n_4), & (i, m) &= (3, n_1) \\ &\mapsto (n_0-n_1-n_4, 0, n_2+2n_4, n_3 +2n_1, 0) & (i, m) &= (2, n_4) \end{align*} We designate the new state $(n'_0, 0, n'_2, n'_3, 0)$. Since $r_0 \equiv 0$ is an invariant, and $n'_1 = n'_4 = 0$, we now have $r_0 \equiv n'_3 - n'_2 = 5p$, for some integer $p$. Our final set of moves is: \begin{align*} (n'_0, 0, n'_2, n'_3, 0) &\mapsto (n'_0+p, p, n'_2, n'_3 - 2p, 0), & (i, m) &= (3, -p)\\ &\mapsto (n'_0+p, 0, n'_2-p, n'_3 - 2p, 2p), & (i, m) &= (4, p) \\ &\mapsto (n'_0-p, 0, n'_2+3p, n'_3 - 2p, 0), & (i, m) &= (2, 2p)\\ &\mapsto (n'_0+2n'_2 + 5p, 0, 0, n'_3-n'_2 - 5p = 0, 0) & (i, m) &= (0, n'_2 + 3p) \end{align*} Now our chosen vertex 0 is the only vertex with a non-zero value, and since $s$ is invariant, that value is $s$ as required. Since a vertex $i$ with $r_i \equiv 0 \pmod 5$ is winnable, and with $s = 2011 \not\equiv 0 \pmod 5$ we always have a unique such vertex, we are done.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_2&oldid=70004"