Library / /665 of 740

, 2019

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

Consider sequences $a$ of the form $a = (a_1, a_2, \ldots, a_{20})$ such that each term $a_i$ is either $0$ or $1$ . For each such sequence $a$ , we can produce a sequence $b = (b_1, b_2, \ldots, b_{20})$ , where
$b_i = \begin{cases} a_i + a_{i+1} & i = 1 \\ a_{i-1} + a_i + a_{i+1} & 1 < i < 20 \\ a_{i-1} + a_i & i = 20 \end{cases}$
How many sequences $b$ are there that can be produced by more than one distinct sequence $a$ ?

Solution

Solution:

Let the two sequences be $b$ and $\hat{b}$ . Then, observe that given $a$ , if $b_1 = \hat{b}_1$ and $b_2 = \hat{b}_2$ , then $b = \hat{b}$ (since $a$ will uniquely determine the remaining elements in $b$ and $\hat{b}$ ). Thus, $b$ and $\hat{b}$ must start with $(1, 0, \ldots)$ and $(0, 1, \ldots)$ , respectively (without loss of generality).

Note that $a_3$ is either $1$ (in which case $b_3 = \hat{b}_3 = 0$ ) or $2$ (in which case $b_3 = \hat{b}_3 = 1$ ). Moreover, $b_4, b_5$ must be the same as $b_1, b_2$ (and the same for $\hat{b}$ ) for the sequences to generate the same $a_3, a_4$ . We can then pick $a_6, a_9, \ldots$

Observe, that the last elements also have to be $(\ldots, 1, 0)$ for $b$ and $(\ldots, 0, 1)$ for $\hat{b}$ . Thus, the answer is nonzero only for sequence lengths of $2 \pmod{3}$ , in which case, our answer is $2^k$ , where the length is $3k + 2$ (since we have two choices for every third element).

Here, since $N = 20 = 3 \times 6 + 2$ , the answer is $2^6 = 64$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.