2

IMO 1986 P3: To each vertex of a pentagon, we assign an integer $x_i$ with sum $s=\sum x_i>0$. If $x,y,z$ are numbers assigned to three successive vertices and if $y<0$, then we replace $(x,y,z)$ by $(x+y,-y,y+z)$. This step is repeated as long as there is a $y<0$. Decide if the algorithm always stops. (Most difficult problem of the IMO).

After generating some examples, I found the following pattern: if $s$ is the sum of the integers at the vertices, then $\sum_{i=1}^5 (s-x_i)^2$ is a weakly decreasing function. Is this true? The solution, which was apparently given by only 11 students in the world, uses the function $\sum (x_i-x_{i+2})^2$, and shows that it is strictly decreasing. Moreover, if the function $\sum_{i=1}^5 (s-x_i)^2$ is indeed weakly decreasing, does it become strictly decreasing every $j$ iterations, where $j>1$?

Batominovski
  • 49,629
  • @saulspatz- Edited, thanks –  Jul 31 '18 at 14:00
  • Can you add the proof that your sum $\sum_{i=1}^5,(s-x_i)^2$ is weakly decreasing? Maybe we will notice something and be able to help out. However, in my opinion, this is not a natural choice. In this kind of problems, I would expect that a good semivariant would measure how much the data $x_1,x_2,\ldots,x_5$ are different. Something like $\sum |x_i-x_j|$ or $\sum (x_i-x_j)^2$ would be a good choice. And it is no surprising at all that $\sum (x_i-x_{i+2})^2$ turns out to be a good semivariant. – Batominovski Jul 31 '18 at 14:13
  • @Batominovski What is the definition of semivariant, please? I can find a few uses of the term by googling, but no definition. – saulspatz Jul 31 '18 at 14:18
  • Well, if you have a combinatorial process, a semivariance is a function that takes your current state and returns some real number (usually a positive integer). We want this function to either increase only or decrease only (weakly or strongly), as the process progresses further. (This is why the prefix semi- is there. The change is in only one direction, instead of both up and down.) This is in contrast with an invariance, which does not change as progresses are made. – Batominovski Jul 31 '18 at 14:22
  • @Batominovski Thanks for the explanation. – saulspatz Jul 31 '18 at 14:23

1 Answers1

0

I checked that $y:=\sum\limits_{i=1}^5\,(s-x_i)^2$ is not even a semivariant (apparently, the correct ending is t, not ce). For example, if we start with $(x_1,x_2,x_3,x_4,x_5):=(1,-3,1,1,1)$, then at the beginning, we have $$y=0^2+0^2+4^2+0^2+0^2=16\,.$$ The only allowed move is $(x_1,x_2,x_3,x_4,x_5)\mapsto (-2,3,-2,1,1)$. At this point, $$y=0^2+3^2+(-2)^2+3^2+0^2=22\,.$$ Therefore, $y=\sum\limits_{i=1}^5\,(s-x_i)^2$ is not a good function to be used.

For the sake of completeness, I shall supply a full answer to this IMO problem. I shall use the OP's hint. However, there is another semivariant, but it is very ugly. This semivariant is in the hidden box below.

The ugly semivariant ($u$ for ugly) I know is $$u:=\sum_{i=1}^5\,|x_i|+\sum_{i=1}^5\,|x_i+x_{i+1}|+\sum_{i=1}^5\,|x_i+x_{i+1}+x_{i+2}|+\sum_{i=1}^5\,|x_i+x_{i+1}+x_{i+2}+x_{i+3}|\,.$$ If you feel somewhat bored today, then please have fun with this semivariant.

To not cause any confusion, suppose the $k$-th state is denoted by $\left(x_1^k,x_2^k,x_3^k,x_4^k,x_5^k\right)$. We shall prove that $$z^k:=\sum_{i=1}^5\,\left(x_i^k-x_{i+2}^k\right)^2$$ is a (strong) semivariant. (The indices in the sum above are considered modulo $5$.) That is, $z^k>z^{k+1}$ as long as the game has not terminated. I should like to note that $s=\sum\limits_{i=1}^5\,x_i^k$ at all possible $k$.

Now, suppose without loss of generality that, at the $k$-th step, the transformation into the $(k+1)$-st step is given by $$\left(x_1^{k+1},x_2^{k+1},x_3^{k+1},x_4^{k+1},x_5^{k+1}\right)=\left(x_1^{k}+x_2^{k},-x_2^k,x_2^k+x_3^k,x_4^k,x_5^k\right)\,.$$ Hence, $$\begin{align}z^{k+1}-z^k &=(-x_2^k-x_4^k)^2-(x_2^k-x_4^k)^2+(x_2^k+x_3^k-x_5^k)^2-(x_3^k-x_5^k)^2 \\ &\phantom{aaaa}+(x_4^k-x_1^k-x_2^k)^2-(x_4^k-x_1^k)^2+(x_5^k+x_2^k)^2-(x_5^k-x_2^k)^2 \\ &=4x_2^kx_4^k+2(x_2^k)^2+2x_2^k(x_3^k-x_5^k)-2x_2^k(x_4^k-x_1^k)+4x_2^kx_5^k \\ &=2x_2^k(x_1^k+x_2^k+x_3^k+x_4^k+x_5^k)=2s\,x_2^k\,. \end{align}$$ Since this move is only allowed when $x_2^k<0$ and since $s>0$, we conclude that $z^{k+1}-z^k<0$.

Batominovski
  • 49,629
  • I suppose semivariance is "the state of being a semivariant," or "the quality of a semivariant," those it's hard to say what either of those phrases mean. :-) – saulspatz Jul 31 '18 at 15:06