Selection tests for the International Mathematical Olympiad 2013

We will construct such a sequence by induction: Define $a_1=1$ and $a_2=2$. In this case we have $b_1=|a_1-a_2|=1$. Assume that $a_1,a_2,\dots ,a_{2n}$ are defined such that there is no positive integer which occurs at least twice neither in the finite sequence $a_1,a_2,\dots ,a_{2n}$ nor in the finite sequence $b_1=|a_1-a_2|,b_2=|a_2-a_3|,\dots ,b_{2n-1}=|a_{2n-1}-a_{2n}|$. Let $M_n$ be the maximum element of the set of integers $\{a_1,a_2,\dots ,a_{2n}\}$, $c_n$ the maximum of the integers $k$ such that $\{1,2,\dots ,k\}\subseteq \{a_1,a_2,\dots ,a_{2n}\}$, and $d_n$ the maximum of the integers $k$ such that $\{1,2,\dots ,k\}\subseteq \{b_1,b_2,\dots ,b_{2n-1}\}$. Notice that for all $1\le i\le 2n-1$, we have $$b_i=|a_i-a_{i+1}|\le \underset{1\le j\le 2n}{\max }{a}_j-\underset{1\le j\le 2n}{\min }{a}_j=M_n-1.$$ If $c_n<d_n$ define $a_{2n+1}=2M_n+c_n+1$ and $a_{2n+2}=c_n+1$. If $c_n\ge d_n$ define $a_{2n+1}=2M_n+1$ and $a_{2n+2}=2M_n+d_n+2$. It is clear that none of the two possible values for $a_{2n+1}$ and for $a_{2n+2}$ occur in the finite sequence $a_1,a_2,\dots ,a_{2n}$. In the first case, we have $$b_{2n}=2M_n+c_n+1-a_{2n}\ge M_n+c_n+1>M_n-1\ge b_i$$ and $$b_{2n+1}=2M_n>M_n-1\ge b_i$$ for all $1\le i\le 2n-1$, and $b_{2n+1}\ne b_{2n}$ since $a_{2n}\ne c_n+1$. In the second case, we have $$b_{2n}=2M_n+1-a_{2n}\ge M_n+1>M_n-1\ge b_i$$ and $$b_{2n+1}=d_n+1\ne b_i$$ for all $1\le i\le 2n-1$, and $b_{2n+1}=d_n+1\le M_n<M_n+1\le b_{2n}$. Therefore, there is no positive integer which occurs at least twice in the finite sequence $a_1,a_2,\dots ,a_{2n+2}$ or in the finite sequence $b_1,b_2,\dots ,b_{2n+1}$. This proves that there is no positive integer which occurs at least twice in the infinite sequence $a_1,a_2,\dots ,a_n,\dots$ or in the infinite sequence $b_1,b_2,\dots ,b_n,\dots$. Notice moreover, that in the first case $c_{n+1}\ge c_n+1$ and in the second case $d_{n+1}\ge d_n+1$. Therefore, if $e_n=\min \{c_n,d_n\}$ then $e_{n+2}\ge e_n+1$. But $c_1=2$ and $d_1=1$. We deduce that $e_{2n}\ge n$ for all integer $n$. Therefore, any positive integer $n$ occurs in both finite sequences $a_1,a_2,\dots ,a_{4n}$ and $b_1,b_2,\dots ,b_{4n-1}$. This proves that any positive integer $n$ occurs exactly once in each infinite sequence $a_1,a_2,\dots$ and $b_1,b_2,\dots$.