TSExams

We first note that $a_i + b_i = n + 1$ for all natural numbers $i$. We define three sequences $\{r_i\}$, $\{s_i\}$, $\{t_i\}$ as follows. Let $r_0 = 1$, $s_0 = t_0 = 0$. For $i > 0$, we let
$$(r_i, s_i, t_i) = \begin{cases} (2r_{i-1}, 2s_{i-1}, 2t_{i-1} + 1) & \text{if } a_{i-1} < b_{i-1}, \\ (2r_{i-1} - 1, 2s_{i-1} - 1, 2t_{i-1} - 1) & \text{if } a_{i-1} > b_{i-1}, \\ (r_{i-1}, s_{i-1}, t_{i-1}) & \text{if } a_{i-1} = b_{i-1}. \end{cases}$$
It is then easy to verify that $a_i = r_i a_0 + s_i b_0 + t_i$ and $b_i = (1 - r_i)a_0 + (1 - s_i)b_0 - t_i$ for all $i \ge 0$.

Now let $k$ be the smallest non-negative integer such that $a_k = b_k$. For any integer $l$ with $0 \le l \le k$ we claim that $r_l - s_l = t_l + 1 - 2s_l = 2^l$. We prove this claim by induction on $l$. The claim is straightforward to check for $l = 0$. Now, suppose that the claim is true for some non-negative integer $l < k$. Since $l + 1 \le k$ it follows that $(r_{l+1}, s_{l+1}, t_{l+1})$ equals either $(2r_l, 2s_l, 2t_l + 1)$ or $(2r_l - 1, 2s_l - 1, 2t_l - 1)$. In either case, $r_{l+1} - s_{l+1} = 2(r_l - s_l)$ and $t_{l+1} + 1 - 2s_{l+1} = 2(t_l + 1 - 2s_l)$. Hence the claim.

Now if $a_k = b_k$ then $r_k a_0 + s_k b_0 + t_k = (1 - r_k)a_0 + (1 - s_k)b_0 - t_k$. This implies $(2r_k - 1) + 2t_k = (1 - 2s_k)n$. Therefore $(n+3)(1 - 2s_k) = 2(r_k - s_k) + 2t_k - 4s_k + 2 = 2^{k+2}$. Hence $n+3$ is a power of 2. In fact, since $1 - 2s_k$ is also a power of 2, it follows that $s_k = 0$ and hence $n + 3 = 2^{k+2}$.