uniolympiads Ελληνικά

IMC 2005, Day 1, Problem 2

For an integer n≥3n \ge 3 consider the sets

Sn={(x1,x2,…,xn):∀i xi∈{0,1,2}}S_n = \{(x_1, x_2, \dots, x_n) : \forall i\ x_i \in \{0, 1, 2\}\}
An={(x1,x2,…,xn)∈Sn:∀i≤n−2  ∣{xi,xi+1,xi+2}∣≠1}A_n = \{(x_1, x_2, \dots, x_n) \in S_n : \forall i \le n - 2\ \ |\{x_i, x_{i+1}, x_{i+2}\}| \ne 1\}

and

Bn={(x1,x2,…,xn)∈Sn:∀i≤n−1  (xi=xi+1⇒xi≠0)}.B_n = \{(x_1, x_2, \dots, x_n) \in S_n : \forall i \le n - 1\ \ (x_i = x_{i+1} \Rightarrow x_i \ne 0)\}.

Prove that ∣An+1∣=3⋅∣Bn∣|A_{n+1}| = 3 \cdot |B_n|. (∣A∣|A| denotes the number of elements of the set AA.)

Original from the official PDFFor an integer n ≥ 3 consider the sets S n = {(x 1 , x 2 , . . . , x n ) : ∀i x i ∈ {0, 1, 2}} A n = {(x 1 , x 2 , . . . , x n ) ∈ S n : ∀i ≤ n − 2 |{x i , x i+1 , x i+2 }| = 6 1} and B n = {(x 1 , x 2 , . . . , x n ) ∈ S n : ∀i ≤ n − 1 (x i = x i+1 ⇒ x i 6 = 0)} . Prove that |A n+1 | = 3 · |B n |. (|A| denotes the number of elements of the set A.)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution 1. Extend the definitions also for n=1,2n=1,2. Consider the following sets

An′={(x1,x2,…,xn)∈An:xn−1=xn},An′′=An∖An′,A'_n=\{(x_1,x_2,\dots,x_n)\in A_n : x_{n-1}=x_n\},\quad A''_n=A_n\setminus A'_n,
Bn′={(x1,x2,…,xn)∈Bn:xn=0},Bn′′=Bn∖Bn′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 an=∣An∣a_n=|A_n|, an′=∣An′∣a'_n=|A'_n|, an′′=∣An′′∣a''_n=|A''_n|, bn=∣Bn∣b_n=|B_n|, bn′=∣Bn′∣b'_n=|B'_n|, bn′′=∣Bn′′∣b''_n=|B''_n|.

It is easy to observe the following relations between the aa–sequences

{an=an′+an′′an+1′=an′′an+1′′=2an′+2an′′,\left\{\begin{array}{rcl} a_n &=& a'_n+a''_n\\ a'_{n+1} &=& a''_n\\ a''_{n+1} &=& 2a'_n+2a''_n \end{array}\right.,
which lead to an+1=2an+2an−1a_{n+1}=2a_n+2a_{n-1}.

For the bb–sequences we have the same relations

{bn=bn′+bn′′bn+1′=bn′′bn+1′′=2bn′+2bn′′,\left\{\begin{array}{rcl} b_n &=& b'_n+b''_n\\ b'_{n+1} &=& b''_n\\ b''_{n+1} &=& 2b'_n+2b''_n \end{array}\right.,
therefore bn+1=2bn+2bn−1b_{n+1}=2b_n+2b_{n-1}.

By computing the first values of (an)(a_n) and (bn)(b_n) we obtain

{a1=3,a2=9,a3=24b1=3,b2=8\left\{\begin{array}{l} a_1=3,\quad a_2=9,\quad a_3=24\\ \qquad b_1=3,\quad b_2=8 \end{array}\right.
which leads to
{a2=3b1a3=3b2\left\{\begin{array}{l} a_2=3b_1\\ a_3=3b_2 \end{array}\right.
Now, reasoning by induction, it is easy to prove that an+1=3bna_{n+1}=3b_n for every n≥1n\ge1.

Solution 2. Regarding xix_i to be elements of Z3\mathbb{Z}_3 and working "modulo 3", we have that

(x1,x2,…,xn)∈An⇒(x1+1,x2+1,…,xn+1)∈An, (x1+2,x2+2,…,xn+2)∈An(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/31/3 of the elements of AnA_n start with 0. We establish a bijection between the subset of all the vectors in An+1A_{n+1} which start with 0 and the set BnB_n by
(0,x1,x2,…,xn)∈An+1⟼(y1,y2,…,yn)∈Bny1=x1, y2=x2−x1, y3=x3−x2,…,yn=xn−xn−1\begin{gathered} (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} \end{gathered}
(if yk=yk+1=0y_k=y_{k+1}=0 then xk−xk−1=xk+1−xk=0x_k-x_{k-1}=x_{k+1}-x_k=0 (where x0=0x_0=0), which gives xk−1=xk=xk+1x_{k-1}=x_k=x_{k+1}, which is not possible because of the definition of the sets ApA_p; therefore, the definition of the above function is correct).

The inverse is defined by

(y1,y2,…,yn)∈Bn⟼(0,x1,x2,…,xn)∈An+1x1=y1, x2=y1+y2,…,xn=y1+y2+⋯+yn\begin{gathered} (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 \end{gathered}

Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?