View source for 2001 Pan African MO Problems/Problem 2

==Problem==

Let <math>n</math> be a positive integer. A child builds a wall along a line with <math>n</math> identical cubes. He lays the first cube on the line and at each subsequent step, he lays the next cube either on the ground or on the top of another cube, so that it has a common face with the previous one. How many such distinct walls exist?

==Solution==

From smaller values of <math>n</math>, there is 1 wall with 1 cube, 2 walls with 2 cubes, 4 walls with 3 cubes, and 8 walls with 4 cubes.  Thus, we can suspect that there are <math>2^{n-1}</math> walls with <math>n</math> cubes.

<br>
To prove our claim, we can calculate the number of walls with <math>n</math> blocks and <math>k</math> columns.  We can use [[ball-and-urn]] counting to determine the number of walls.  Since there are <math>k</math> columns, there would be <math>k-1</math> dividers.  There are a total of <math>n</math> blocks, but each column must have at least one block, so there are <math>n-k</math> blocks left to sort.  Thus, there are <math>\binom{n-1}{n-k}</math> walls that have <math>n</math> blocks and <math>k</math> columns.

<br>
Summing all possible values of <math>k</math> means that there are a total of <math>\binom{n-1}{n-1} + \binom{n-1}{n-2} + \cdots + \binom{n-1}{0} = \boxed{2^{n-1}}</math> walls with <math>n</math> cubes.

==See Also==
{{Pan African MO box
|year=2001
|num-b=1
|num-a=3
}}

[[Category:Intermediate Combinatorics Problems]]