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

Note that interchanging the order of the turns does not affect anything. Thus we can consider just the 5 distinct possible moves. Let $x_1, x_2, ..., x_5$ be the initial values of the 5 vertices, and let $m_1, m_2, ..., m_5$ be the total values of $m$ directed at the five vertices. Consider the case where $x_1$ is the vertex that reaches $2011.$ 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}\]
We have $N_1=x_5+2x_4+3x_3+4x_2+5x_1=5m_1-5m_2+5x_1$ is a multiple of $5.$ This means that for a set of $m_i$ to exist, $N$ must be a multiple of $5.$ Now note that $N_2=x_1+2x_5+3x_4+4x_3+5x_2 \equiv N_1+2011\pmod{5}.$ Therefore, all the $N_i$ are different values mod 5, so there can be at most 1 vertex that reaches $2011$ for each arrangement.

Now it remains to prove that there always exists a set of $m_i.$ Without loss of generality let $x_1$ be the vertex that reaches $2011.$ Consider the following values of $m_i.$

\[\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}\]
There values are all integers considering $N_1/5$ 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 $x_i,$ 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.
This post has been edited 1 time. Last edited by KingSmasher3, Apr 3, 2013, 3:33 AM

Comment

0 Comments

[img]http://s03.flagcounter.com/count/OsVD/bg_E8F2FF/txt_000000/border_CCCCCC/columns_2/maxflags_18/viewers_0/labels_1/pageviews_0/flags_1/[/img][/url]

avatar

KingSmasher3
Shouts
Submit
  • orz blog!!!

    by KevinChen_Yay, Dec 29, 2024, 1:39 AM

  • 1 year bump lol

    by Yiyj1, Mar 1, 2024, 1:55 AM

  • 2 year bump rip

    by cinnamon_e, Mar 25, 2023, 5:46 PM

  • Bumpity bump

    by mathboy282, Dec 13, 2020, 9:38 PM

  • NT God Please Return!

    by Pluto1708, Mar 20, 2019, 2:25 PM

  • dude,your blog is awesome.Please don't stop and continue your posts!! :)

    by Jiminhio 10, Jan 16, 2014, 2:11 PM

  • thanks haha

    by KingSmasher3, Sep 6, 2013, 3:15 AM

  • happy birthday

    by cire_il, Sep 3, 2013, 9:10 PM

  • btw im totally not trolling

    dude problem 2s are so hard
    what is this madness
    what is going on
    hehe
    we are not spamming up your blog like it might seem at first
    lalalalalalalalala

    by applepi2000, Jun 25, 2013, 12:31 AM

  • Hmm USAMO so hard

    by antimonyarsenide, Jun 25, 2013, 12:28 AM

  • dude you do problem 2s?
    dude so legit man
    i am not trolling

    by applepi2000, Jun 25, 2013, 12:28 AM

  • Hmm USAMO so hard

    by antimonyarsenide, Jun 25, 2013, 12:28 AM

  • dude you do problem 2s?
    dude so legit man
    i am not trolling

    by applepi2000, Jun 25, 2013, 12:27 AM

  • Hey look an excellent problem blog.

    It contains a bunch of USAMO problems that are familiar to me because I did them a couple months ago.

    by yugrey, Apr 5, 2013, 1:55 AM

  • Are you my mommy?

    by meisepic, Mar 26, 2013, 6:47 AM

  • too much math

    by cire_il, Mar 26, 2013, 3:15 AM

  • Yay you made a blog!

    by dinoboy, Mar 19, 2013, 4:29 AM

17 shouts
Tags
About Owner
  • Posts: 1399
  • Joined: Jul 16, 2009
Blog Stats
  • Blog created: Nov 11, 2012
  • Total entries: 26
  • Total visits: 14572
  • Total comments: 14
Search Blog
a