Maths Olympiad Prep

Track / Stage 6 / 292 of 400 #1932 of 2604

Problem 1932

National Olympiad, first round
Combinatorics Difficulty 6.7 Prove it Brazilian Mathematical Olympiad · Brazil

One has a long row of glasses and nn stones in the central glass (glass 00). The following movements are allowed:

• Movement AA
Figure 1
If there is at least one stone in glass ii and at least one in glass i+1i+1, one may make one stone in glass i+1i+1 jump to glass i−1i-1, eliminating one stone in glass ii.

• Movement B
Figure 2
If there are at least two stones in glass i one may make a stone in glass i jump to glass i + 2 and make another stone jump to glass i - 1.

Prove the following: performing movements A and B for a sufficiently long time, one shall always obtain a configuration from which neither movements are allowed anymore. Besides this final configuration does not depend on the choices of movements during the process.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Assign x′x' to a stone in the iith glass. Let's consider what happens to the sum of the number assigned to all stones with each movement.

Movement A replaces xi+xi+1x^i + x^{i+1} with xi−1x^{i-1}; movement B replaces 2xi2x^i with xi−1+xi+2x^{i-1} + x^{i+2}. So the difference in the sum is either xi−1(1−x−x2)x^{i-1}(1 - x - x^2) or xi−1(1+x3−2x)=xi−1(1−x−x2)(1−x)x^{i-1}(1 + x^3 - 2x) = x^{i-1}(1 - x - x^2)(1 - x).

Choose xx so that 1−x−x2=01-x-x^2=0, say x=ϕ−1=5−12x = \phi^{-1} = \frac{\sqrt{5}-1}{2}. Then the sum SS of the numbers assigned to the stones always stays the same. There is a number xkx^k such that S<xkS < x^k, so there is a limit to the leftmost stone, so it won't move after a while. Now consider the sum without this stone; the leftmost stone (that is, the second leftmost stone overall) won't move after a while and so on. So the configuration will remain constant at some time, that is, there won't be any two stones in the same glass nor two stones in two consecutive glasses.

Now notice that the representation of SS in base ϕ−1\phi^{-1} (all digits equal to one, no two consecutive ones) is unique: suppose on the contrary that there are two such representations and let kk be the first position from left to right in which those representations differ. This means that ϕ−k\phi^{-k} is equal to the sum of some numbers of the form ϕ−m\phi^{-m} for m>k+1m > k + 1. But ∑m=k+2∞ϕ−m=ϕ−k−21−ϕ−1=ϕ−k\sum_{m=k+2}^{\infty} \phi^{-m} = \frac{\phi^{-k-2}}{1-\phi^{-1}} = \phi^{-k}, so this isn't possible. So the final configuration is unique.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.