Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2001 Pan African MO Problems/Problem 2"

(→‎Solution)
(→‎Solution 2)
 
Line 17: Line 17:
  
 
-th1nq3r
 
-th1nq3r
 +
 +
I do not believe that this is the correct way. If I put the <math>2^{nd}</math> cube in front, then I have three choices for my next cube, stack it up on the first, or the second, or put it in front. The choice of either stack or put front assumes that stacking on all cubes is the same and equivalent, which is not correct, because the walls with 1-2-1 cubes and 2-1-1 cubes are different walls. If I am mistaken, please message me, I am interested in learning what I have done wrong. Thank you very much.
 +
 +
~ Rolt
  
 
==See Also==
 
==See Also==

Latest revision as of 05:27, 1 September 2025

Problem

Let $n$ be a positive integer. A child builds a wall along a line with $n$ 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 $n$, 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 $2^{n-1}$ walls with $n$ cubes.


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


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

Solution 2

There are $n$ cubes. After placing the first cube down, we have $(n-1)$ cubes left. Now for each of these remaining $(n-1)$ remaining cubes, we have two options; stack the cube or put it in front. This then gives that since there are $2$ options for each of the $(n-1)$ cubes, the answer as $\boxed{2^{n-1}}$.

-th1nq3r

I do not believe that this is the correct way. If I put the $2^{nd}$ cube in front, then I have three choices for my next cube, stack it up on the first, or the second, or put it in front. The choice of either stack or put front assumes that stacking on all cubes is the same and equivalent, which is not correct, because the walls with 1-2-1 cubes and 2-1-1 cubes are different walls. If I am mistaken, please message me, I am interested in learning what I have done wrong. Thank you very much.

~ Rolt

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_Pan_African_MO_Problems/Problem_2&oldid=259494"