SAUDI ARABIAN MATHEMATICAL COMPETITIONS

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\ge M$ and $a_N\ge 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\ge 1$. The sequence is as the following $$1,0,1,0,3,2,1,0,7,6,5,4,3,2,1,0,\dots$$ We divide the sequence into blocks with $k^{\text{th}}$ block contains $a_i$ for $2^{k-1}<i\le 2^k$. Within each block, the value $a_n+n$ is constant, and for the $k^{th}$ block $(k\ge 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$