This website contains problems from math contests. Problems and corresponding tags were obtained from the Art of Problem Solving website.

Tags were heavily modified to better represent problems.

AND
OR
NO

Found problems: 2

2016 India IMO Training Camp, 1
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.
geometry recurrence relation power of 2 number theory bir tinga qimmat ekan boru invariants modular arithmetic recurrence relations sequences

2016 India IMO Training Camp, 1
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.
geometry recurrence relation power of 2 number theory bir tinga qimmat ekan boru invariants modular arithmetic recurrence relations sequences