Competition problem — Combinatorics

Library / /42 of 65

Combinatorics Difficulty 6.1 National Olympiad Prove it Romania

For $n \ge 2$ , consider $n$ boxes aligned from left to right. In each box, one puts a ball that can be red, blue or white such that the following condition is fulfilled: Each box is neighboring at least one box containing a ball of the same color. We denote by $I_n$ the number of such configurations.

a) Determine $I_{11}$ . Justify your answer.

b) Find, with proof, the general formula for $I_n$ .

Solution

Obviously $a_2 = 1$ , $a_3 = 1$ . For $a \ge 4$ , if the first box contains a red ball, then so does the second one. Now we distinguish two types of configurations: those containing a red ball in the third box, and those with a blue or a white ball in the third box. In order to count the configurations of the first type, simply forget about the first box. We can easily see that there are $a_{n-1}$ configurations of this type. For the second type of configurations, we omit the first two boxes and obtain $2a_{n-2}$ configurations. Thus, $a_n = a_{n-1} + 2a_{n-2}$ .

By induction, it is easy to prove that $a_n = \frac{2^{n-1} + (-1)^n}{3}$ , hence $I_n = 2^{n-1} + (-1)^n$ . For $n = 11$ we get $I_{11} = 1023$ .

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.