Problem

Source: Iran Third Round MO 1998, Exam 1, P1

Tags: modular arithmetic, induction, number theory unsolved, number theory



Define the sequence $(x_n)$ by $x_0 = 0$ and for all $n \in \mathbb N,$ \[x_n=\begin{cases} x_{n-1} + (3^r - 1)/2,&\mbox{ if } n = 3^{r-1}(3k + 1);\\ x_{n-1} - (3^r + 1)/2, & \mbox{ if } n = 3^{r-1}(3k + 2).\end{cases}\]where $k \in \mathbb N_0, r \in \mathbb N$. Prove that every integer occurs in this sequence exactly once.