As promised, this is the 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 is smart. She wants to avoid the above case where she loses. So she says: "Aha! I only write , 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 times and then times , which after interpreting in binary is 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 respectively and , if so, then we can change the numbers to . 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 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 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 but the absolute value can be quite unpredictable at times, so we consider the "nicer" alternative squares .
So referring back to the notation at the beginning, consider a function . Clearly . Suppose WLOG that and we do the transformation in the problem. Then:
Since and we assumed that , we have that so decreases at each step. By infinite descent we are done. □
Question for the reader: Can you find a monovariance using as sugeested in the solution above?
Hint: Consider including pairwise sums then testing and etc.
Look forward to the next post :)