Competition problem — Algebra — Maths Olympiad Prep

Library / /66 of 155

Algebra Difficulty 5.9 AIME, harder Prove it Saudi Arabia

Define the sequence $a_{1}, a_{2}, \ldots$ as follows: $a_{1}=1$ , and for every $n \geq 2$ , $a_{n}=n-2$ if $a_{n-1}=0$ and $a_{n}=a_{n-1}-1$ , otherwise. Find the number of $1 \leq k \leq 2016$ such that there are non-negative integers $r, s$ and a positive integer $n$ satisfying $k=r+s$ and $a_{n+r}=a_{n}+s$ .

Solution

Let $N=n+r$ and $M=n$ , then
$r=N-M,\ s=a_{N}-a_{M}\ \text{ and }\ k=r+s=\left(a_{N}+N\right)-\left(a_{M}+M\right) .$
We need to find the number of possible values of $\left(a_{N}+N\right)-\left(a_{M}+M\right)$ , where $N \geq M$ and $a_{N} \geq a_{M}$ .
It is easy to see by induction that $a_{2^{k}}=0$ and thus $a_{2^{k}+1}=2^{k}-1$ for all $k \geq 1$ . The sequence is as the following
$1,0,1,0,3,2,1,0,7,6,5,4,3,2,1,0, \ldots$
We divide the sequence into blocks with $k^{\text{th}}$ block contains $a_{i}$ for $2^{k-1}< i \leq 2^{k}$ . Within each block, the value $a_{n}+n$ is constant, and for the $k^{th}$ block $(k \geq 1)$ it equals $2^{k}$ .
Therefore, $d=\left(a_{N}+N\right)-\left(a_{M}+M\right)$ is the difference of two powers of $2$ . Now it's not difficult to show that there are $51$ such possible values. $\square$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.