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
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.
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.