Problem A. 914. (October 2025)
A. 914. We write the ordered pair \(\displaystyle (1,0)\) on the board. In one step, if the ordered pair \(\displaystyle (a,b)\) is on the board, we erase it and replace it with either \(\displaystyle (a+b,b)\) or \(\displaystyle (2a+b,a+b)\). (For example, after two steps, the pair on the board may be one of \(\displaystyle (1,0)\), \(\displaystyle (2,1)\), \(\displaystyle (3,1)\), or \(\displaystyle (5,3)\).) Prove that after \(\displaystyle n\) steps, the ordered pair on the board can take exactly \(\displaystyle 2^n\) different values.
Proposed by András Imolay, Budapest
(7 pont)
Deadline expired on November 10, 2025.
Let's introduce transformation \(\displaystyle (a,b)\rightarrow(a,a+b)\), and note that \(\displaystyle (2a+b,b)\) can be obtained from \(\displaystyle (ab)\) by applying \(\displaystyle (a,b)\rightarrow(a+b,b)\) first and then our new transformation. This leads to the following rephrasing of the problem: we start from \(\displaystyle (1,0)\), and then apply transformations \(\displaystyle (a,b)\rightarrow(a+b,b)\) or \(\displaystyle (a,b)\rightarrow(a,a+b)\): we apply the first type exactly \(\displaystyle n\) times, and the number of times we've applied the second type is not fixed, however, each time we apply it, subsequently we have to apply the first type.
Now observe that after applying the first type of transformation the first member of the resulting pair is bigger, and after applying the second type of transformation the second member of the resulting pair is bigger. Thus if we know the result, we can always decide which transformation was applied to obtain it, and therefore we also know the previous pair. Now we have to decide whether it is possible reach \(\displaystyle (1,0)\) from the final result in two different ways: we've showed that it is possible to trace back our steps, therefore the only problem is that after reaching \(\displaystyle (1,0)\) we can still apply the reverse of the first transformation to go back to itself. However, since the number of times we've applied the first type of transformation is fixed, this means that the whole sequence is unique, and thus we've proved the claim.
Statistics:
Problem A. 914. is not processed yet.
Problems in Mathematics of KöMaL, October 2025