## Pathway Arrangements

#### Problem

A pathway measuring four units in length can be paved in exactly eight different ways using any combination of paving stones measuring one to four units in length.

Find the number of ways that a pathway measuring $n$ units in length can be paved if paving stones of any whole unit length size can be used.

#### Solution

We begin by showing that each pathway arrangement can be represented by a binary string with the alternating lengths of 0's and 1's corresponding with the length of each paving stone.

Using this system, the arrangements given in the problem are demonstrated.

\begin{align}0 101 &\iff 1 1 1 1\\0 010 &\iff 2 1 1\\0 110 &\iff 1 2 1\\0 100 &\iff 1 1 2\\0 011 &\iff 2 2\\0 001 &\iff 3 1\\0 111 &\iff 1 3\\0 000 &\iff 4\end{align}

Clearly for a pathway length $n$, the string must comprise of $n$ bits. However, note that all the strings begin with zero, otherwise a string like $1010$ would be a duplicate of its "inverted" string, $0101$. In other words, we need only concern ourselves with the last $n - 1$ bits; it is also significant to note that every combination of these $n - 1$ bits corresponds precisely with a unique pathway arrangement.

Hence there are exactly $2^{n-1}$ different pathway arrangements.

What if the maximum length stone is two units in length?
Investigate for different maximum length stones.

Problem ID: 270 (16 Feb 2006)     Difficulty: 3 Star

Only Show Problem