Competition problem — Combinatorics

Library / /17 of 18

Combinatorics Difficulty 6.6 National olympiad Prove it Austria

Each brick of a set has 5 holes in a horizontal row. We can either place pins into individual holes or brackets into two neighboring holes. No hole is allowed to remain empty. We place $n$ such bricks in a row in order to create patterns running from left to right, in which no two brackets are allowed to follow another, and no three pins may be in a row. How many such patterns of bricks can be created?

Solution

Since 3 pins (P) or 2 brackets (B) may not lie in a row, they may not do so on an individual brick. This means that there are only three different types of brick, which we name A (PBPP), B (PPBP) and C (BPB). Naming the number of possible patterns of $n$ bricks with a brick A at the end $a_n$ , and analogously $b_n$ and $c_n$ for B and C, the number we wish to determine is $s_n = a_n + b_n + c_n$ . Due to the restrictions on the bricks, we see that $a_{n+1} = b_n + c_n$ , $b_{n+1} = c_n$ and $c_{n+1} = a_n + b_n$ with starting values $a_1 = b_1 = c_1 = 1$ .

This yields
$s_{n+1} = s_n + (b_n + c_n) = s_n + (a_{n-1} + b_{n-1} + c_{n-1}) = s_n + s_{n-1}$
with $s_1 = 3$ and $s_2 = 5$ . We see that the resulting sequence $s_n$ is simply the Fibonacci sequence starting from the fourth element, and $s_n = F_{n+3}$ .

qed

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.