Team Selection Test for IMO, 2011

a.
Let $b_n = \frac{2^{(k+1)n}k - 1}{2^{(k+1)n} - 1} = 2^{(k+1)n(k-1)} + \dots + 2^{(k+1)n} + 1$ for $n \ge 0$ and
$$a_n = \frac{b_n}{b_{n-1}} = \frac{(2^{(k+1)n}k - 1)(2^{(k+1)n-1} - 1)}{(2^{(k+1)n} - 1)(2^{(k+1)n-1}k - 1)} \quad \text{for } n \ge 1.$$
Since $(2^{(k+1)n} - 1, 2^{(k+1)n-1}k - 1) = 2^{((k+1)n, (k+1)n-1)} - 1 = 2^{(k+1)n-1} - 1$, $a_n$ is an integer and $t(a_1a_2\dots a_n) = t(b_n) = k$ for all $n \ge 1$.

b.
It suffices to show that $t(n(2^r - 1)) \ge r$ for all positive integers $n$ and $r$. We will use induction on $n$.

* For $n = 1$, $t(n(2^r - 1)) = t(2^r - 1) = r$.
* Let $n > 1$. If $n$ is even, then $t(n(2^r - 1)) = t((n/2)(2^r - 1)) \ge r$ by the induction hypothesis. Assume that $n = 2j + 1$ where $j$ is a positive integer. Then
$$\begin{align*} t(n(2^r - 1)) &= t((2j + 1)(2^r - 1)) \\ &= t((2j + 2)(2^r - 1) - 2^r + 1) \\ &= t((2j + 2)(2^r - 1) - 2^r) + 1 \\ &\ge t((2j + 2)(2^r - 1)) - 1 + 1 \\ &= t((j + 1)(2^r - 1)) \\ &\ge r \end{align*}$$
where we used the induction hypothesis and the fact that $t(i - 2^r) \ge t(i) - 1$ for $i > 2^r$.