1

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

How can we use the following monovariant for solving the above question?

$g(x)$$=$$\sum_{i=1}^{5}$$\sum_{j=1}^{5}$$|x_i+x_{i+1}.........x_{j-1}|$

I tried my best, but I am not able relate the following function with the question.

user75659
  • 280
  • 1
    What does monovariant mean? I don't recall having seen the term before. – Jyrki Lahtonen May 28 '19 at 04:33
  • 1
    I don't recall seeing this question before (rust building up), but my first impression (due to having a bit of experience with Coxeter groups, Dynking diagrams and such) is that the cyclic nature of the graph makes a huge difference here, but your $g(x)$ does not take that into account. Making me a bit skeptical about what you want to achieve. But, your idea is unclear to me. And I don't know the solution to the question either, so I'm prepared to be wrong about this also. – Jyrki Lahtonen May 28 '19 at 04:38
  • 2
    Monovariant is a function which either decreases or increases. – user75659 May 28 '19 at 04:43

1 Answers1

1

Let $S = \{v,w,x,y,z\}$ denote the ordered set of 5 integers on the pentagon vertices. We are allowed to perform one operation on $S$, which is to take three numbers $x,y,z$ on any three consecutive vertices, and replace them by $x+y, -y, z+y$. If $\rho$ denotes an operation, we denote the result of this operation as $\rho \cdot S$.

The key property of $g(S)$ is that no matter what operation $\rho$ we perform, $g(S)$ is strictly decreasing, i.e. $g(\rho \cdot S) < g(S)$. To show this, one just needs to calculate it out and see that if $v,w,x,y,z$ are the numbers on the vertices, $y < 0$, and we do the operation on the three integers $x,y,z$, then $$g(S) - g(\rho \cdot S) = |v+w+x+z| - |v+w+x+z+2y| $$ and this quantity is strictly positive since $y < 0$.

Thus, $g(S)$ can only decrease finitely many times before reaching zero, which implies that only finite many operations can be performed on $S$.

eatfood
  • 2,414