IMC 2005 · Day 1 · P2

Extend the definitions also for $n = 1, 2$. Consider the following sets $$A_n' = \{ (x_1, x_2, \dots, x_n) \in A_n : x_n = x_{n-1} \}, \quad A_n'' = A_n \setminus A_n',$$ $$B_n' = \{ (x_1, x_2, \dots, x_n) \in B_n : x_n = 0 \}, \quad B_n'' = B_n \setminus B_n'$$ and denote $a_n = |A_n|$, $a_n' = |A_n'|$, $a_n'' = |A_n''|$, $b_n = |B_n|$, $b_n' = |B_n'|$, $b_n'' = |B_n''|$.

It is easy to observe the following relations between the $a$–sequences $$\begin{cases} a_n = a_n' + a_n'' \\ a_{n+1}' = a_n'' \\ a_{n+1}'' = 2 a_n' + 2 a_n'' \end{cases},$$ which lead to $a_{n+1} = 2 a_n + 2 a_{n-1}$.

For the $b$–sequences we have the same relations $$\begin{cases} b_n = b_n' + b_n'' \\ b_{n+1}' = b_n'' \\ b_{n+1}'' = 2 b_n' + 2 b_n'' \end{cases},$$ therefore $b_{n+1} = 2 b_n + 2 b_{n-1}$.

By computing the first values of $(a_n)$ and $(b_n)$ we obtain $$\begin{cases} a_1 = 3,\ a_2 = 9,\ a_3 = 24 \\ b_1 = 3,\ b_2 = 8 \end{cases}$$ which leads to $$\begin{cases} a_2 = 3 b_1 \\ a_3 = 3 b_2 \end{cases}$$ Now, reasoning by induction, it is easy to prove that $a_{n+1} = 3 b_n$ for every $n \ge 1$.

Regarding $x_i$ to be elements of $\mathbb{Z}_3$ and working “modulo 3”, we have that $$(x_1, x_2, \dots, x_n) \in A_n \Rightarrow (x_1 + 1, x_2 + 1, \dots, x_n + 1) \in A_n,\ (x_1 + 2, x_2 + 2, \dots, x_n + 2) \in A_n$$ which means that $1/3$ of the elements of $A_n$ start with 0. We establish a bijection between the subset of all the vectors in $A_{n+1}$ which start with 0 and the set $B_n$ by $$(0, x_1, x_2, \dots, x_n) \in A_{n+1} \longmapsto (y_1, y_2, \dots, y_n) \in B_n$$ $$y_1 = x_1,\ y_2 = x_2 - x_1,\ y_3 = x_3 - x_2,\ \dots,\ y_n = x_n - x_{n-1}$$ (if $y_k = y_{k+1} = 0$ then $x_k - x_{k-1} = x_{k+1} - x_k = 0$ (where $x_0 = 0$), which gives $x_{k-1} = x_k = x_{k+1}$, which is not possible because of the definition of the sets $A_p$; therefore, the definition of the above function is correct).

The inverse is defined by $$(y_1, y_2, \dots, y_n) \in B_n \longmapsto (0, x_1, x_2, \dots, x_n) \in A_{n+1}$$ $$x_1 = y_1,\ x_2 = y_1 + y_2,\ \dots,\ x_n = y_1 + y_2 + \dots + y_n$$