Maths Olympiad Prep

Library / /4 of 11

Combinatorics Difficulty 6.2 National olympiad Find the answer

Let nn be a positive integer. A child builds a wall along a line with nn 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?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to determine how many distinct ways the child can build a wall with n n identical cubes. Each cube can be placed in such a way that it shares a face with the previous cube. This can be done either by placing the new cube on the ground or on top of the previously placed cube.

Let's analyze the process:

1. Understanding the Cube Placement: When starting with the first cube, there are no choices; it must be placed on the line.

2. Choices for Subsequent Cubes: For each subsequent cube, the child has two choices:
- Place it directly next to the previous cube on the same level (ground level).
- Place it on top of the previous cube.

3. Recursive Formulation:
- After placing the first cube, each additional cube requires a decision to be made independently of the previous decisions, except where cubes are supported.
- Hence, for each cube from the second to the n n -th, there are 2 independent choices to be made.

4. Counting Distinct Structures:
- This leads to a binary decision problem for each cube position, starting from the second one.
- Therefore, there are 2n1 2^{n-1} distinct ways to arrange the n n cubes.

5. Conclusion: For n n cubes, the number of distinct walls is determined by the number of binary choices we make for the position of each cube starting from the second cube, which equates to 2n1 2^{n-1} .

Thus, the number of distinct walls that can be constructed is:
2n1 \boxed{2^{n-1}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.