AustriaMO2011

Question

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?

Accepted Answer

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