Problem:
Let . For every sequence of integers
satisfying , for , define another sequence
by setting to be the number of terms in the sequence that precede the term and are different from . Show that, starting from any sequence as above, fewer than applications of the transformation lead to a sequence such that .
Solution:
Note first that the transformed sequence also satisfies the inequalities , for . Call any integer sequence that satisfies these inequalities an index bounded sequence.
We prove now that that , for . Indeed, this is clear if . Otherwise, let and . None of the first consecutive terms is greater than so they are all different from and precede (see the diagram below). Thus , that is, , for .
| index | 0 | 1 | ||||
|---|---|---|---|---|---|---|
| a_ | a_ | a_ | ||||
This already shows that the sequences stabilize after finitely many applications of the transformation , because the value of the index term in index bounded sequences cannot exceed . Next we prove that if , for some , then no further applications of will ever change the index term. We consider two cases.
| index | 0 | 1 | ||
|---|---|---|---|---|
| 0 | 0 | 0 | ||
| 0 | 0 | 0 |
In this case, we assume that . The first terms are all different from . Because , the terms must then all be equal to . Consequently, for and further applications of cannot change the index term (see the diagram below).
| index | 0 | 1 | ||||||
|---|---|---|---|---|---|---|---|---|
| a_ | a_ | a_ | ||||||
For , the index entry satisfies the following properties: (i) it takes integer values; (ii) it is bounded above by ; (iii) its value does not decrease under transformation ; and (iv) once it stabilizes under transformation , it never changes again. This shows that no more than applications of lead to a sequence that is stable under the transformation .
Finally, we need to show that no more than applications of is needed to obtain a fixed sequence from an initial -term index bounded sequence . We induct on .
For , the two possible index bounded sequences and are already fixed by so we need zero applications of .
Assume that any index bounded sequences reach a fixed sequence after no more than applications of . Consider an index bounded sequence . It suffices to show that will be stabilized in no more than applications of . We approach indirectly by assume on the contrary that applications of transformations are needed. This can happen only if and each application of increased the index term by exactly 1 . Under transformation , the resulting value of index term will not the effected by index term for . Hence by the induction hypothesis, the subsequence will be stabilized in no more than applications of . Because index term is stabilized at value after no more than applications of and index term obtains value after exactly applications of under our current assumptions. We conclude that the index term would become equal to the index term after no more than applications of . However, once two consecutive terms in a sequence are equal they stay equal and stabilize together. Because the index term needs no more than transformations to be stabilized, can be stabilized in no more than applications of , which contradicts our assumption of applications needed. Thus our assumption was wrong and we need at most applications of transformation to stabilize an -term index bounded sequence. This completes our inductive proof.
The problems on this page are the property of the MAA's American Mathematics Competitions