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)}+\cdots +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)}\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_1{a}_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{array}{rl}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{array}$$ where we used the induction hypothesis and the fact that $t(i-2^r)\ge t(i)-1$ for $i>2^r$.