some questions about IMO 1986 problem 3

Question

To each vertex of a pentagon, we assign an integer $x_i$ with sum $s=\sum{x_i > 0}.$ If $x, y,z $ are the numbers assigned to three successive vertices and if $ y < 0$ , then we replace $(x, y,z)$ by $(x + y, −y, y + z)$. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Decide if the algorithm always stops and how many steps are required?

following is from Problem Solving Strategies by Arthur Engel:

Bernard Chazelle (Princeton) asked: How many steps are needed until stop? He considered the infinite multiset $S$ of all sums defined by $s(i, j )=x_i +···+ x_{j−1}$ with $1 ≤ i ≤ 5$ and $j > i$. A multiset is a set which can have equal elements. In this set, all elements but one either remain invariant or are switched with others. Only $s(4, 5)= x_4$ changes to $−x_4$. Thus, exactly one negative element of $S$ changes to positive at each step. There are only finitely many negative elements in $S$, since $s > 0$. The number of steps until stop is equal to the number of negative elements of S. It is interesting to find a formula with the computer, which, for input $a, b, c, d, e,$ gives the number of steps until stop. This can be done without much effort if $s=1$. For instance, the input $(n, n, 1 − 4n, n, n)$ gives the step number $\color {red}{ f(n)=20n-10 }$.

---

Fisrt : I'm not convinced There are only finitely many negative elements in $S$. I understand that if $x_4$ is negative, then we can go forward and since s>0 after at most reaching to $s(4,9)$ it will be positive but if we continue why it can't get negative again?

Second : how one should find the formula marked by red ? and why is it easier when $s=1$?

I checked the similar questions but they don't answer my specific questions.

Answer 1

Let $u=\min\{\,s(i,j)\mid 1\le i\le 5<j\le 10\,\}$. For $j>10$, let $k=\lfloor\frac{j-5}{5}\rfloor$. Then $$f(i,j)=f(i,j-5k)+ks\ge u+ ks. $$ As $s>0$, we conclude $f(i,j)\ge 0$ for $k\ge -\frac us$, so certainly for $j>-\frac {5u}s+5$. This shows that $S$ has only finitely many negative elements.

The number of negative elements in $S$ is not that hard to find computationally:

1. $N\leftarrow 0$
2. $i\leftarrow 1$
3. $j\leftarrow i$, $t\leftarrow 0$
4. If $t<0$, set $N\leftarrow N+\lfloor\frac{-t}{s}\rfloor$
5. $t\leftarrow x_{j}$, $j\leftarrow j\bmod 5+1$
6. If $j\ne i$, go back to step 4
7. $i\leftarrow i+1$.
8. If $i\le 5$, g back to step 3.
9. Stop. $N$ is the number of negative elements in $S$.

Of course, if $s=1$, there is simply $N\leftarrow N-t$ in step 4 and the final $N$ can simply be described as the negative sum of all negative circular partial sums. With $(n,n,1-4n,n,n)$, these negative circular partial sums are

• $1-4n$
• $n+(1-4n)$ and $(1-4n)+n$
• $n+n+(1-4n)$ and $n+(1-4n)+n$ and $(1-4n)+n+n$
• $n+n+n+(1-4n)$ and $n+n+(1-4n)+n$ and $n+(1-4n)+n+n$ and $(1-4n)+n+n+n$

Summing the negatives of these, we obtain $$ (4n-1)+2(3n-1)+3(2n-1)+4(n-1)=20n-10.$$

With $2-4n$ in place of $1-4n$, we have $s=2$ and would instead need to sum $$ \left\lfloor\frac{4n-2}{2}\right\rfloor +2\left\lfloor\frac{3n-2}{2}\right\rfloor +3\left\lfloor\frac{2n-2}{2}\right\rfloor +4\max\left\{\left\lfloor\frac{n-2}{2}\right\rfloor,0\right\}. $$ Doable, but less nice (and you can simplify this for $n=1$, $n>1$ odd, and $n$ even separately).