Problem of the Week 1046

A Triumphal Arch

Suppose you have a budget to build an arch using 110 bricks that you are to purchase. The arch is made simply from two vertical columns of bricks that go up to the same height. A lintel is then placed over the top, but that does not use any bricks and is not relevant to the problem. Each brick is either one or two units high, and their price is the same.

How many ways are there to build such a pi-shaped arch when

• the two columns are to be made using all 110 bricks?
• the two columns are to have exactly the same height?
• a brick of height 2 is never placed on top of one of height 1?

Again, bricks are used in the columns only, not for the lintel. Arches that are symmetric about the vertical center but are not identical are considered to be different.

So, for example, with 4 bricks there would be exactly 3 arches.

With 5 bricks there are 4 arches, illustrated below in horizontal fashion. That is, the first example below means that the left column is 2, then 1, then 1, and the right columns has two 2s.

211
22

22
211

21
111

111
21

Source: This problem -- finding a formula with 110 replaced by general n -- is a "live" problem from the American Mathematical Monthly, #11183 by David Beckwith, Nov. 2005 issue.

© Copyright 2005 Stan Wagon. Reproduced with permission.