16
$\begingroup$

Joshua was a box-stacker at the local supermarket. Every day he had to stack hundreds upon hundreds of boxes, so he devised a little game to keep himself entertained. Each day, he would take out a certain number($n$) of cubic boxes, and stack them according to these rules:

  • He would only stack the boxes in a $2$-dimensional plane (only 1 layer deep).
  • Every box in the bottom layer of boxes must be adjacent to another box, i.e. no gaps between the boxes in the bottom layer.
  • Every box that is not on the bottom layer must be placed directly on top of another box.

After having stacked the $n$ boxes, Joshua would take a picture of the set-up and store it on his phone. How many different pictures could Joshua take if he had $n$ boxes to play with?possible arrangement

*Hint: You may be tempted to bash away with combinatoric mathematics, but I promise there is a very simplistic and beautiful way that involves no hard maths whatsoever.

$\endgroup$
1
  • 1
    $\begingroup$ The real question is, After what value of n does the stack overflow? $\endgroup$
    – CodeNewbie
    Aug 13, 2015 at 8:10

4 Answers 4

23
$\begingroup$

Here is another way to arrive at the answer of

$2^{n-1}$

We can represent these "stackings" by taking a row of $n$ $*$'s, and placing |'s between some of the stars to break them into groups, representing the stacks.

For example, the below layout

*
* *
****

would be represented by

* * *|*|* *|*

This represents every possible stacking in a unique way, so asking for the number of stackings is the same as asking the number of strings of $*$'s and |'s in the above form. The latter is much easier to count: between every two adjacent $*$'s, there either is a |, or there isn't. This means there are $n-1$ choices to make, each with $2$ options, for a total of $2^{n-1}$ possibilities.

$\endgroup$
13
$\begingroup$

Answer:

$2^{n-1}$

How I arrived at this solution: We start by looking at the base case of $n=1$. There is only one way to stack one box.

Continuing for $n=2,3,4$, we get:

n=2,3,4

While drawing each piece out, I made sure to group the figures by the number of bottom pieces. By doing this, I noticed that the number in each group is very familiar:

n=1: 1
n=2: 1 1
n=3: 1 2 1
n=4: 1 3 3 1
.... It's Pascal's Triangle!

Thus, using the well known formula for the sum of each row, we get the answer:

$2^n$, but looking at the case of $n=1$, we only have one configuration, so the answer is actually: $2^{n-1}$

$\endgroup$
12
$\begingroup$

For every arrangement of $n$ boxes, we can define a procedure to create that arrangement consisting of $n$ instructions of either of the forms:

  • Place a box on the current stack.
    OR
  • Place a box to the right of the current stack. (This box is the new stack.)

Let's call the first instruction $0$ and the second instruction $1$. A sequence of instructions consists of a string of $n$ $1$s and $0$s. The only restriction is that, assuming we start with an empty stack, the first instruction must be a $0$: otherwise we could end up with an empty stack, and we don't want any gaps.

We can see that every arrangement has a unique sequence of instructions, and that every possible sequence of instructions corresponds to a unique arrangement of boxes. Thus the number of arrangements is equal to the number of length-$n$ binary strings that start with $0$; which is itself equal to the number of length-$(n-1)$ binary strings:

$$2^{n-1}$$

$\endgroup$
1
  • $\begingroup$ Beautiful and easy - the most natural/intuitive solution for me so far! $\endgroup$
    – Falco
    Aug 11, 2015 at 10:42
0
$\begingroup$

We're basically looking for the number of possible arrangements of vertical boxes whose sum of lengths give $n$. Let's imagine that there are $n$ 1s, with each linked to the adjacent 1. We can either cut a link or leave it as it is. The linked ones will be considered grouped together. Since there are $n-1$ links, we can leave them in $2$^$(n-1)$ ways.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.