As promised, this is the \( 4 \)th instalment, following the 3rd.
Let us start with the solution to the second part of the problem that was left to the reader:
So remember that \( A \) is smart. She wants to avoid the above case where she loses. So she says: "Aha! I only write \( 0s \), in that way, I will win!" Well, sad life A, because you don't. Because if A only writes "0s", using the same argument above we can in fact make B write \( 1998 \) times \( 0 \) and then \( 3 \) times \( 1 \), which after interpreting in binary is \( 21 \) so B wins again. □
Recall the method of infinite descent or more commonly known as monovariants introduced in the 2nd instalment.
Let us now apply infinite descent to a much more difficult problem.
Example 3: (IMO 1986) We assign an integer to each vertex of a regular pentagon, so that the sum of all of them is positive. We are allowed to perform a transformation if three consecutive vertices have assigned numbers \( x,y, z \) respectively and \( y < 0 \), if so, then we can change the numbers \( (x,y,z) \) to \( (x+y, -y, z+y) \). This process can be continued as long as one of the numbers is negative. Does this process always come to an end?
Solution: Don't freak out that this is from IMO.
We label the pentagon with \( a,b,c,d,e \) as shown.
So we need to find a certain invariance. In fact the only "basic" thing we have is the sum of all numbers. Also notice that \( (x+y) + (-y) + (z+y) = (x+y+z) \) so the sum remains constant. This does not tell us whether the process ends. We need something that decreases. Now from the sum, it is certainly quite motivated to consider the average. So if every number is very close to the average then none would be negative and the process would end. So we want to search for something that will increase as the numbers are different to the average. Naturally, we might think of \( |x-y| \) but the absolute value can be quite unpredictable at times, so we consider the "nicer" alternative squares \( (x-y)^2 \).
So referring back to the notation at the beginning, consider a function \( f(a,b,c,d,e) = (a-c)^2 + (c-e)^2 + (e-b)^2 + (b-d)^2 + (d-a)^2 \). Clearly \( f(a,b,c,d,e) ≥ 0 \). Suppose WLOG that \( c < 0 \) and we do the transformation in the problem. Then:
\( f(a,b+c, -c, d+c, e) = (a+c)^2 + (-c-e)^2 + (e-b-c)^2+ (b-d)^2 + (d+c-a)^2 \)
\( = [(a-c)^2 +4ac] + [(c-e)^2 + 4ce] + [(e-b)^2 - 2ec + 2bc + c^2] + (b-d)^2 + [(d-a)^2 - ac + 2cd + c^2] \)
\( = f(a,b,c,d,e) + 2c(a+b+c+d+e) \)
Since \( c<0 \) and we assumed that \( a+b+c+d+e > 0 \), we have that \( 2c(a+b+c+d+e) < 0 \) so \( f(a,b,c,d,e) \) decreases at each step. By infinite descent we are done. □
Question for the reader: Can you find a monovariance using \( |x-y| \) as sugeested in the solution above?
Hint: Consider including pairwise sums then testing and etc.
Look forward to the next post :)