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 3 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.
Asked
Active
Viewed 275 times
2
-
If you're not willing to do any part of the work yourself but want random strangers on the internet to provide you with a "detailed solution", then why are you even in the contest? – hmakholm left over Monica Mar 23 '13 at 12:17
-
Well I found this question in a book.I tried a lot,but couldn't figure out a solution. – Shaswata Mar 23 '13 at 12:25
1 Answers
3
This is IMO 1986 Q3.
Consider the monovariant $S=\sum_{i=1}^{5}{(x_{i+2}-x_i)^2}$, where $x_6=x_1, x_7=x_2$.
WLOG suppose we perform an operation to get from $(x_1, x_2, x_3, x_4, x_5)$ to $(x_1+x_2, -x_2, x_2+x_3, x_4, x_5)$, and $S$ changes to $S'$. Then
\begin{align} S-S' &=(x_3-x_1)^2+(x_4-x_2)^2+(x_5-x_3)^2+(x_1-x_4)^2+(x_2-x_5)^2 \\ & -(x_3-x_1)^2-(x_4+x_2)^2-(x_5-x_2-x_3)^2-(x_1+x_2-x_4)^2-(-x_2-x_5)^2 \\ &=-2x_2(x_1+x_2+x_3+x_4+x_5) \\ & <0 \end{align}
since $s=\sum{x_i}>0$ and $x_2<0$.
Now $S$ is clearly a non-negative integer, and is strictly decreasing in each step, so the algorithm will always stop.
There is another solution using a different monovariant here.
Ivan Loh
- 16,955