Maths Olympiad Prep

Library / /57 of 100

Combinatorics Difficulty 4.9 AIME Find the answer China

Suppose sequence {an}\{a_n\} consists of nine terms, which satisfy a1=a9=1a_1 = a_9 = 1 and ai+1ai{2,1,12}\frac{a_{i+1}}{a_i} \in \{2, 1, -\frac{1}{2}\} for any i{1,2,,8}i \in \{1, 2, \dots, 8\}. Then the number of sequences like this is ______.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let bi=ai+1aib_i = \frac{a_{i+1}}{a_i} (1i81 \le i \le 8). Then for each {an}\{a_n\} satisfying the given condition, we have
i=18bi=i=18ai+1ai=a9a1=1, with bi{2,1,12}(1i8).1 \prod_{i=1}^{8} b_i = \prod_{i=1}^{8} \frac{a_{i+1}}{a_i} = \frac{a_9}{a_1} = 1, \text{ with } b_i \in \{2, 1, -\frac{1}{2}\} (1 \le i \le 8). \qquad \textcircled{1}
Conversely, a sequence of eight terms {bn}\{b_n\} satisfying 1 can uniquely determine a sequence {an}\{a_n\} in the question.

In each {bn}\{b_n\}, there are obviously even number of 12-\frac{1}{2} and the same number of 22, with the remainder being 11. Or, in other words, the numbers of 12-\frac{1}{2} and 22 are both 2k2k, while the number of 11 is 84k8-4k. Here, it is easy to check that kk can only be 0,1,20, 1, 2. Once kk is given, there are C82kC82k2kC_8^{2k} C_{8-2k}^{2k} ways to construct {bn}\{b_n\}.

Therefore, the total number of {bn}\{b_n\} satisfying ① is
N=1+C82C62+C84C44=1+28×15+70×1=491. N = 1 + C_8^2 C_6^2 + C_8^4 C_4^4 = 1 + 28 \times 15 + 70 \times 1 = 491.
The answer is 491.

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 and solution reproduced as published; topic and difficulty added by this site.