If $ y$ < $ 0$, only then we can apply this transformation, but then if we have $ y$ < $ 0$ initially, we have reached the end of procedure and if there is not any $ y$ < $ 0$, we can't apply this transformation. Does it make sense, please clarify?

I like this problem a lot also . Let \[ S(a_1,a_2,a_3,a_4,a_5) = \sum_{S \subseteq \{1,2,3,4,5\}} \left|\sum_{i\in S}a_i\right|\]. Observe that under the given transformation, S is strictly decreasing, but no strictly decreasing sequence of positive integers is infinite so we are done. Proof: Compare S' = S(a+b,-b,b+c,d,e) with S=(a,b,c,d,e). Most of the terms are the same. However, the different terms we get are S-S' = |a+c+d+e|-|a+2b+c+d+e| > 0 because b is negative, but a+b+c+d+e is positive, so a+c+d+e is positive.

Ilthigore wrote: Let \[ S(a_1,a_2,a_3,a_4,a_5) = \sum_{S \subseteq \{1,2,3,4,5\}} \left|\sum_{i\in S}a_i\right|\] . I don't understand your notation. Could you clarify please?

Another way to solve this problem by introducing a different function: Consider $ x_i$ for $ i = 1,2,3,4,5$ as the five numbers in the pentagon. Now, consider $ x_4 = y < 0$, and by the problem hypothesis $ S = \sum_{i = 1}^n x_i > 0$, we have by the function $ f(x_1, x_2, x_3, x_4, x_5) = \sum_{i = 1}^n (x_{i + 2} - x_i) ^2$ where $ x_6$ can be thought of as $ x_1$ and $ x_7$ as $ x_2$. Obviously, if we consider $ f_2$ as the new value of $ f(x_i, i = 1,2,3,..5)$ after the transformation and $ f_1$ as the initial one , we get that $ f_2 - f_1 = 2s x < 0$ by the given condition...... So, the function is decreasing on the positive integers , by the Principle of FIniteness of a Decreasing Sequence on positive integers, we get that the operation has to stop at some point.

Agr_94_Math wrote: Principle of FIniteness of a Decreasing Sequence on positive integers http://en.wikipedia.org/wiki/Well-ordering_principle

Similar problem was proposed at Kosova Mathematical Olympiad See it here

Agr_94_Math wrote: Another way to solve this problem by introducing a different function: Consider $ x_i$ for $ i = 1,2,3,4,5$ as the five numbers in the pentagon. Now, consider $ x_4 = y < 0$, and by the problem hypothesis $ S = \sum_{i = 1}^n x_i > 0$, we have by the function $ f(x_1, x_2, x_3, x_4, x_5) = \sum_{i = 1}^n (x_{i + 2} - x_i) ^2$ where $ x_6$ can be thought of as $ x_1$ and $ x_7$ as $ x_2$. Obviously, if we consider $ f_2$ as the new value of $ f(x_i, i = 1,2,3,..5)$ after the transformation and $ f_1$ as the initial one , we get that $ f_2 - f_1 = 2s x < 0$ by the given condition...... So, the function is decreasing on the positive integers , by the Principle of FIniteness of a Decreasing Sequence on positive integers, we get that the operation has to stop at some point. WHAT IF THERE ARE N NUMBERS:REPLY QUICKLY

See here for a paper.

Agr's solution is straight from Engel.

See also http://www.artofproblemsolving.com/Forum/viewtopic.php?t=294347 for both a generalization to $n$ numbers, as well as a discussion on why the result stays the same if the numbers are only known to be real, not integer.

The algorithm always stops. Consider the function \[f(x_1, x_2, x_3, x_4, x_5)=\displaystyle\sum_{i=1}^5(x_i-x_{i+2})^2, x_6=x_1, x_7=x_2.\] Clearly $f>0$ always and $f$ is integer valued. Suppose, WLOG, that $y=x_4<0$. Then $f_{\text{new}}-f_{\text{old}}=2Sx_4<0$ since $S>0$. Thus if the algorithm does not stop, we can find an infinite decreasing sequence of nonnegative integers $f_0>f_1>f_2>\cdots$. This is impossible, so the algorithm must stop. $\Box$

In PSS,Engel wrote,'All but one of the eleven students who solved the problem found the same function."Can one point out whats the function the remaining participant exhibited?? tc1729 posted the same solution as Agr_94_Math.Well,no point in posting the same solutions.

I have been reading PSS, and I have two questions about this problem: 1. What is the motivation for constructing the function $f(x_1, x_2, x_3, x_4, x_5)=\displaystyle\sum_{i=1}^5(x_i-x_{i+2})^2, x_6=x_1, x_7=x_2.$ How do we guess that it will decrease each step? 2. How do we determine $f_{\text{new}}-f_{\text{old}}=2Sx_4$? Do we have to expand out the function and simplify, or is there an easier way?

For more information on the history, alternative solutions, and generalizations of the problem see http://www.mathe.tu-freiberg.de/~wegert/Papers/Pentagon.pdf. (This is the manuscript of E.Wegert and Ch.Reiher, Relaxation procedures on graphs, Discrete Applied Mathematics 157, 2207-2216 (2009)). If you would like to learn who the problem arose, click "http://www.mathe.tu-freiberg.de/~wegert/Talks/2012Batumi.pdf" for a talk with some background material.

@JWK750 For your second question, I expanded, but not fully; a lot of things cancel out right away, and the algebra isn't that bad. For your first question, I'm wondering the same thing. Can someone explain the motivation behind constructing that function? (Like how would someone think of doing that?)

@JWK750 and @azmath333 For your first question: the lacking motivation for this function is the part which made the problem hard (IMO level). When I created the problem (see the second link in my post from Aug 11, 2016), I just "saw" this function. It is very specific, and does not work for all n-gons. To get some deeper understanding you may read the paper addressed in the second link.

$S(a,b,c,d,e)=(a–d) ^2+(b–e) ^2+(b–d) ^2+(b–e) ^2+(c–e) ^2\ge 0$ ,for all $a, b, c, d, e$ are real And let $a, b, d, e>0,c<0$ And as per transformation $(x, y, z) =(x+y,–y, y+z)$ We get $S(a,b,c,d,e)=S(a,b+c,–c, d+c,e)$ $\implies S(k)=(a+c)^2+(a–d –c) ^2+(c+e)^2+(b–e) ^2+(b–d) ^2=S(a,b,c,d,e)+2c(a+b+c+d+e)<0$ Since $c<0$ ,$a+b+c+d+e>0$ ,so by infinite descent we are done. Actually the motivation of this done by second moment. Actually the $n-gon$ is given the vertices $v(G)=({a, b, c, d, e})$

Let, denote the vertices of pentagone is $x_i \forall I =1,2,...,5$ now ,let in first step $(x_1,x_2,x_3,x_4,x_5) \to (x_1,x_2+x_3,-x_3,x_4+x_3,x_5)$ In this case every thing changes but s(sum) of the integer is invariant. So ,our claim is that we can got a mono variant funtion that decreases. Let,$f_0(x_1,x_2,x_3,x_4,x_5)=$ $\sum _{I=1}^5 x_i^2 -x_ix_{i+1}$ So ,$f_0(x_1,x_2,x_3,x_4,x_5)=$ $ \frac{1}{2} \sum_{i=1}^5 (x_{i+1}-x_i)^2$ now let $f_0 \to f_k $ denote operation on $f_0$ for k times and resulting $f_k$. So,$f_1-f_0\le 0$ I.e $f_1<f_0$ So,f is decreasingby property of integer it is naturally that the operation will stop after finite steps. $\square$. QED

ftheftics wrote: Let, denote the vertices of pentagone is $x_i \forall I =1,2,...,5$ now ,let in first step $(x_1,x_2,x_3,x_4,x_5) \to (x_1,x_2+x_3,-x_3,x_4+x_3,x_5)$ In this case every thing changes but s(sum) of the integer is invariant. So ,our claim is that we can got a mono variant funtion that decreases. Let,$f_0(x_1,x_2,x_3,x_4,x_5)=$ $\sum _{I=1}^5 x_i^2 -x_ix_{i+1}$ So ,$f_0(x_1,x_2,x_3,x_4,x_5)=$ $ \frac{1}{2} \sum_{i=1}^5 (x_{i+1}-x_i)^2$ now let $f_0 \to f_k $ denote operation on $f_0$ for k times and resulting $f_k$. So,$f_1-f_0\le 0$ I.e $f_1<f_0$ So,f is decreasingby property of integer it is naturally that the operation will stop after finite steps. $\square$. QED Plz can you explain the motivation behind defining the following function...

This might be my favorite problem too! My solution is similar to what was posted above, but seems to be unique (as far as I've seen on the internet for now) and hopefully a little more motivated. Sorry for no latex. WLOG let x_2 be the negative number. After a bit of playing around, we see that the sum is constant and that (1) the sum of x_i^2 seems to be a decreasing function. It turns out it isn't, but continuing on we take (2) the sum of (x_i+x_(i+1))^2 before and after the operation. Neither (1) or (2) is sufficient, but adding them gives us a change of 2*x_2*(sum of x_i) after the operation. This is clearly a negative number. As the sum of 2 squares always decreases after the operation, we see that the operation must end at one point since the sum cannot be less than 0.

Let $a_i$ be the number on vertex $i$, $i=1,2,3,4,5$. $S=a_1+2a_2+3a_3+4a_4+5a_5$. $S$ decreases if and only if we operate on vertex 1. Assume the process never ends. This implies we operate the move on a vertex infinitely many times. WLOG, this vertex is vertex 1. This contradicts that $S$ has a lower bound.

Gorav wrote: If $ y$ < $ 0$, only then we can apply this transformation, but then if we have $ y$ < $ 0$ initially, we have reached the end of procedure and if there is not any $ y$ < $ 0$, we can't apply this transformation. Does it make sense, please clarify? No, because maybe y is now positive, but x and z are smaller - they can be negative. And also two other numbers can be negative.

KI_HG wrote: Let $a_i$ be the number on vertex $i$, $i=1,2,3,4,5$. $S=a_1+2a_2+3a_3+4a_4+5a_5$. $S$ decreases if and only if we operate on vertex 1. Assume the process never ends. This implies we operate the move on a vertex infinitely many times. WLOG, this vertex is vertex 1. This contradicts that $S$ has a lower bound. How did you show that $S$ has a lower bound?

It was said that we could change the condition ‘integer’ into ‘real number’ and the conclusion is still true. But how to prove that? One argues that we could introduce an number to count disorder pairs of number? But I cannot understand it. I am grateful if one could tell me how.

The value $$\sum_{i = 1}^5 a_i^2 + (a_{i} + a_{i + 1})^2$$is nonnegative and increments by $2a_i(a_1 + \ldots + a_5)$ when $a_i$ is operated on. Thought process... sorta: Checking small cases indicated to me that this does terminate (I almost convinced myself it doesn't). Some stuff later, I noticed that the terms end up close together, but don't quite get closer at every step: this led to the idea of modifying the sum of squares and forcing something to happen. From the observation of $$\big((a_{i-1} + a_i)^2 + (-a_i)^2 + (a_{i+1} + a_i)^2\big) - (a_{i-1}^2 + a_i^2 + a_{i+1}^2) = 2a_i(a_{i-1} + a_i + a_{i+1}),$$I decided to try the most blithely stupid thing possible and use this as the correction term, summed cyclically; that is, I wrote down $$\sum_{i = 1}^5 a_i^2 + \lambda a_i(a_{i-1} + a_i + a_{i+1})$$and prayed that this does something good. My prayers were answered: setting $\lambda = \tfrac{1}{2}$ gives the monovariant above.

Storage along with some intuition: Proof: Consider the mono variant: $I(a_1, \cdots, a_5) = \sum (|a_k|+|a_k+a_{k+1}|+|a_k+a_{k+1}+a_{k+2}|+|a_k+a_{k+1}+a_{k+2}+a_{k+3}|)$. Note that, after every step, the above quantity reduces monotonically. Also note, that its always attains non-negative integer in any configuration. Thus, the operation eventually finishes and we are done. Intuition: After a bit of small cases tinkering, one might guess that its always possible. Note that, the sum is invariant. Thus, we might consider something like sum of squares. But if $x, y, z$ are all negative, we are doomed and it fails. Now, closely observing that, we need something which looks for relative difference. Something like when $x$ are positive, then it would work. We try $\sum |a_k+a_{k+1}|$. After an operation, it will be generating something more like $|a_k + a_{k+1}+a_{k+2}|$. To cover it up and similar terms more, $|a_k|+|a_k+a_{k+1}|+|a_k+a_{k+1}+a_{k+2}|+|a_k+a_{k+1}+a_{k+2}+a_{k+3}|$ and BOOM, it works.