Let $n$ be a natural number. We define sequences $\langle a_i\rangle$ and $\langle b_i\rangle$ of integers as follows. We let $a_0=1$ and $b_0=n$. For $i>0$, we let $$\left( a_i,b_i\right)=\begin{cases} \left(2a_{i-1}+1,b_{i-1}-a_{i-1}-1\right) & \text{if } a_{i-1}<b_{i-1},\\ \left( a_{i-1}-b_{i-1}-1,2b_{i-1}+1\right) & \text{if } a_{i-1}>b_{i-1},\\ \left(a_{i-1},b_{i-1}\right) & \text{if } a_{i-1}=b_{i-1}.\end{cases}$$Given that $a_k=b_k$ for some natural number $k$, prove that $n+3$ is a power of two.
Problem
Source: India TST 2016 Day 3 Problem 1
Tags: number theory, recurrence relation, power of 2, geometry, bir tinga qimmat ekan boru
fractals
23.07.2016 01:55
It is easy to see that $n + 3$ being a power of two easily implies that $a_k = b_k$ for sufficiently large $k$, as an additional note.
Notice that the sum $a_i + b_i$ remains constant and equal to $n + 1$.
Now suppose that $n + 3$ is not a power of two. Let $v = v_2(n + 3)$. Then $n + 3 = 2^v(2k + 1)$ for $k \ge 1$ an integer. And now, we can easily induct to prove that $a_i = 2^{i + 1} - 1$ as long as $2^i - 1 < \frac{n + 1}{2}$; this is because $a_{i - 1} < b_{i - 1}$ for those values and thus we only look at the top branch of the recurrence. But certainly $\frac{n + 1}{2} = \frac{2^v(2k + 1) - 2}{2} = 2^{v - 1}(2k + 1) - 1 = 2^vk + 2^v - 1 \ge 2^v$ and thus for all $0 \le i \le v$ we must have $a_i = 2^{i + 1} - 1$. Then clearly $(a_v, b_v) = (2^{v + 1} - 1, n + 2 - 2^{v + 1})$ and thus $a_v\equiv b_v\equiv -1\pmod{2^v}$, since $2^v|n + 3$. And now it is easy to see that $a_l\equiv b_l\equiv -1\pmod{2^v}$ for all $l\ge v$. But if ever $a_i = b_i$ then all subsequent terms would equal that same constant, so certainly $a_l = b_l$ for all sufficiently large $l$. But then $a_l = \frac{n + 1}{2}$ would result, while also\[\frac{n + 1}{2}\equiv -1\pmod{2^v}\implies n + 1\equiv -2\pmod{2^{v + 1}}\implies 2^{v + 1}|n + 3,\]in contradiction to $v_2(n + 3) = v$. We are done.
WizardMath
23.07.2016 04:38
Note that after an obvious transformation it is solved by a method posted in the thread for last year's India TST nt problem.
Ankoganit
23.07.2016 08:50
My solution: Consider two new sequences $\langle c_i\rangle$ and $\langle d_i\rangle$ defined as $c_i=a_i+1,d_i=b_i+1.$ It is easy to see that the recurrence becomes $$\left( c_i,d_i\right)=\begin{cases} \left(2c_{i-1},d_{i-1}-c_{i-1}\right) & \text{if } c_{i-1}<d_{i-1},\\ \left( c_{i-1}-d_{i-1},2d_{i-1}\right) & \text{if } c_{i-1}>d_{i-1},\\ \left(c_{i-1},d_{i-1}\right) & \text{if } c_{i-1}=d_{i-1}.\end{cases}$$Note that $c_i+d_i$ is an invariant (and is equal to $c_0+d_0=n+3$), and at each step, $\text{gcd} (c_i,d_i)$ either stays the same, or becomes twice its previous value. Initially $\text{gcd}(c_0,d_0)=\text{gcd}(2,n+1)=1\text{ or }2$, so $\text{gcd}(c_i,d_i)$ is always a power of two. When we finally have $c_k=d_k$, then $\text{gcd}(c_k,d_k)=c_k=d_k=\tfrac{c_k+d_k}{2}=\tfrac{n+3}{2}$ must be a power of two. Hence $n+3$ is a power of two, as desired. $\blacksquare$
WizardMath
23.07.2016 08:55
Nice solution Ankoganit. My solution at the tst was almost the same but I established a congruence relation and using an inequality and the sum invariance we finish.
AnonymousBunny
23.07.2016 09:12
Using the same notations as Ankoganit, another finish which hopefully works...
Note that one of $c_i, d_i$ always gets doubled. Since their sum is zero mod $n+3$, the other number must also get doubled modulo $n+3$. So after $k$ steps, the numbers will be $2^k \cdot c_0 \mod (n+3)$ and $2^k \cdot (n+1) \mod (n+3)$. Hence if $c_k= d_k$, we have that $n+3 \mid 2^k (n+1-2) = 2^k (n-1)$. Note that $\gcd (n+3, n-1)$ cannot have an odd factor (it divides 4), so $n+3$ cannot have an odd factor, and hence must be a power of 2.
WizardMath
23.07.2016 09:15
@above this approach works and got a 10/10 on a tst for a student who used this approach.
shinichiman
23.07.2016 10:02
A different approach without considering modulo power of $2$ is to work backwards. So, if $n+3$ is divisible by an odd number $l \ge 3$ and $c_k=d_k=\tfrac{n+3}{2}$ implies $l \mid \gcd (c_k,d_k)$ which leads to $l \mid \gcd (c_i,d_i)$ for all $i \le k$ (this is true according to the operation). This means $l \mid (c_0,d_0)=(2,n+1)$, a contradiction. We are done.