Difference between revisions of "2001 Pan African MO Problems/Problem 2"
Rockmanex3 (talk | contribs) (Solution to Problem 2 -- wall) |
(→Solution) |
||
Line 12: | Line 12: | ||
<br> | <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. | 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. | ||
+ | |||
+ | ==Solution 2== | ||
+ | There are <math>n</math> cubes. After placing the first cube down, we have <math>(n-1)</math> cubes left. Now for each of these remaining <math>(n-1)</math> remaining cubes, we have two options; stack the cube or put it in front. This then gives that since there are <math>2</math> options for each of the <math>(n-1)</math> cubes, the answer as <math>\boxed{2^{n-1}}</math>. | ||
+ | |||
+ | -th1nq3r | ||
==See Also== | ==See Also== |
Latest revision as of 07:39, 5 September 2021
Contents
[hide]Problem
Let be a positive integer. A child builds a wall along a line with
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 , 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
walls with
cubes.
To prove our claim, we can calculate the number of walls with blocks and
columns. We can use ball-and-urn counting to determine the number of walls. Since there are
columns, there would be
dividers. There are a total of
blocks, but each column must have at least one block, so there are
blocks left to sort. Thus, there are
walls that have
blocks and
columns.
Summing all possible values of means that there are a total of
walls with
cubes.
Solution 2
There are cubes. After placing the first cube down, we have
cubes left. Now for each of these remaining
remaining cubes, we have two options; stack the cube or put it in front. This then gives that since there are
options for each of the
cubes, the answer as
.
-th1nq3r
See Also
2001 Pan African MO (Problems) | ||
Preceded by Problem 1 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 3 |
All Pan African MO Problems and Solutions |