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.
Problem
Source: Iran Third Round MO 1998, Exam 1, P1
Tags: modular arithmetic, induction, number theory unsolved, number theory
professordad
07.07.2012 05:09
Here's a list
$n \equiv 1 \pmod{3} \Longrightarrow x_n = x_{n - 1} + 1$
$n \equiv 2 \pmod{3} \Longrightarrow x_n = x_{n - 1} - 2$
$n \equiv 3 \pmod{9} \Longrightarrow x_n = x_{n - 1} + 1 + 3$
$n \equiv 6 \pmod{9} \Longrightarrow x_n = x_{n - 1} - 2 - 3$
$n \equiv 9 \pmod{27} \Longrightarrow x_n = x_{n - 1} + 1 + 3 + 9$
$n \equiv 18 \pmod{27} \Longrightarrow x_n = x_{n - 1} - 2 - 3 - 9$
etc. etc. etc.
First numbers: 0, 1, -1, 3, 4, 2, -3, -2, -4, 9, 10, 8, 12, 13, 11, 6, 7, 5, ...
It isn't hard to prove that $x_{3n} = 3x_n$ by induction, just do cases on $n \equiv 1 \pmod{3}$ and $n \equiv 2 \pmod{3}$. It also follows by induction that $x_{3n + 1} = 3x_n + 1$ and $x_{3n + 2} = 3x_n - 1$.
Thus, $x_{3n} \equiv 0 \pmod{3}$, $x_{3n + 1} \equiv 1 \pmod{3}$, $x_{3n + 2} \equiv 2 \pmod{3}$. (*)
We now prove that every integer occurs at most once; we can prove this by contradiction. Suppose that there's integers $a$ and $b$ such that $x_a = x_b$. From (*), $a \equiv b \pmod{3}$. Also, for $a \equiv b \equiv 0 \pmod{3}$ we can just divide by 3 repeatedly until we reach a number not divisible by 3.
So WLOG assume $a \equiv b \equiv 2 \pmod{3}$. Then, $x_{a} = x_{a - 1} - 2$ and $x_{b} = x_{b - 1} - 2$, so $x_{a - 1} = x_{b - 1}$ and the $a \equiv b \equiv 1 \pmod{3}$ case is equivalent to this. Similarly, $x_{a - 2} = x_{b - 2}$. Now $a - 2 \equiv b - 2 \equiv 0 \pmod{3}$. Since $x_{a - 1} = 3x_{\frac{a - 1}{3}}$ and $x_{b - 1} = 3x_{\frac{b - 1}{3}}$, repeatedly divide by 3 until we get $x_{\frac{a - 1}{3^k}} = x_{\frac{b - 1}{3^k}}$, where $\tfrac{a - 1}{3^k} \equiv 1 \pmod{3}$ or $2 \pmod{3}$. Then repeat the process.
At some point we're bound to end. It keeps going until one of the two numbers, WLOG the one calculated from $b$, reaches $0$. Then, let the other number be $x_m$, with $m \neq 0$. We have $x_m = 0 \equiv 0 \pmod{3}$, so $m \equiv 0 \pmod{3}$. Then $x_{\frac{m}{3}} = 0$ as well. We keep dividing until we reach $x_{\text{number not divisible by 3}} = 0$. However, from (*) this is impossible. So we have reached a contradiction, and no integers occur more than once.
Now we prove that every integer occurs. This is easier; take an integer $k$ such that we're dubious whether it occurs in $x_n$.
If $k \equiv 1 \pmod{3}$, $x_k = 3x_m + 1$. If $k \equiv 2 \pmod{3}$, $x_k = 3x_m - 1$. So either add 1 to $k$ and divide by 3, or subtract 1 from $k$ and divide by 3 to get $x_{\text{number}} = \tfrac{k \pm 1}{3}$. Keep going until we get 1, 2, or 3, which are numbers in our sequence ($x_1 = 1$, $x_5 = 2$, $x_3 = 3$).
To demonstrate, let $k = 13$. Then, if $\tfrac{13 - 1}{3} = 4$ is in our sequence, $x_{13}$ is in our sequence. Similarly, if $\tfrac{4 - 1}{3} = 1$ is in our sequence, $x_4$ is in our sequence. But $1$ is in our sequence, since $x_1 = 1$. So $x_{13}$ is in our sequence. By our method, $x_4$ should be the $1 \cdot 3 + 1 = 4$th term in our sequence, and $x_{13}$ should be the $4 \cdot 3 + 1 = 13$th term in our sequence. Indeed, this is true.
If $k \equiv 0 \pmod{3}$, repeatedly divide until we get a new $1 \pmod{3}$ or $2 \pmod{3}$ number, then proceed as shown above.
Thus, every integer occurs in this sequence exactly once.
Edited for clarity in some parts.