[25] Jessica the jackrabbit wants to climb down a wall. The wall consists of 2026 horizontal layers stacked vertically. The $n$ -th layer from the top is partitioned into $2^n - 1$ identical rectangular bricks arranged side by side. Jessica begins in the topmost layer, which contains a single brick. A move consists of Jessica going down one layer to a brick that shares a side with the brick she is currently on. Determine, with proof, the total number of distinct sequences of moves Jessica can take to reach the 2026th layer. (combinatorics, pathfinding, layers, sequences)

Answer: $2^{2025}$

Step-by-step solution

Step 1: Analyze the structure of the wall layers

The problem states that the $n$ -th layer from the top is partitioned into $2^n - 1$ identical rectangular bricks. Let $L_n$ denote the number of bricks in the $n$ -th layer. So, $L_1 = 2^1 - 1 = 1$ brick, $L_2 = 2^2 - 1 = 3$ bricks, $L_3 = 2^3 - 1 = 7$ bricks, and so on. Jessica starts in the topmost layer, which is layer 1.

Step 2: Determine the number of possible moves from one layer to the next

A move consists of Jessica going down one layer to a brick that shares a side with the brick she is currently on. Since the bricks are arranged side by side, a brick in layer $k$ can connect to either one or two bricks in layer $k+1$ . Specifically, if a brick in layer $k$ is at an edge, it connects to one brick in layer $k+1$ . If it's in the middle, it connects to two bricks in layer $k+1$ . However, the problem implies that the bricks in layer $k+1$ are directly below the bricks in layer $k$ , and the total width of the wall increases. The key is that each brick in layer $k$ can connect to exactly two bricks in layer $k+1$ , except for the outermost bricks in layer $k+1$ . But since the number of bricks in layer $k+1$ is $2^{k+1}-1$ , which is always odd, there is always a central brick in layer $k+1$ that aligns with the center of a brick in layer $k$ . The problem implies that any brick in layer $k$ can connect to two bricks in layer $k+1$ if it's not at the edge of the layer, and one if it is. However, the structure of $2^n-1$ bricks suggests a binary tree-like expansion. Each brick in layer $n$ can be thought of as having two 'children' in layer $n+1$ . This means from any brick in layer $n$ , there are 2 possible bricks in layer $n+1$ that it can move to.

Step 3: Calculate the number of paths for a few initial layers

Let $P_n$ be the number of distinct sequences of moves to reach layer $n$ . Jessica starts in layer 1, which has 1 brick. So, $P_1 = 1$ . To reach layer 2, from the single brick in layer 1, there are 2 possible bricks in layer 2 she can move to. So, $P_2 = 2$ . To reach layer 3, from each of the 2 bricks in layer 2, there are 2 possible bricks in layer 3 she can move to. So, $P_3 = 2 \times 2 = 4$ . This pattern suggests that for each step down, the number of paths doubles.

Step 4: Formulate a general rule for the number of paths

From the observation in the previous step, the number of distinct sequences of moves to reach layer $n$ is $2^{n-1}$ . This is because for each of the $n-1$ moves (from layer 1 to layer 2, from layer 2 to layer 3, ..., from layer $n-1$ to layer $n$ ), there are 2 choices. Therefore, the total number of sequences is $2 \times 2 \times \dots \times 2$ ( $n-1$ times).

Step 5: Calculate the total number of sequences to reach the 2026th layer

We need to find the total number of distinct sequences of moves Jessica can take to reach the 2026th layer. Using the formula derived, we substitute $n = 2026$ into $P_n = 2^{n-1}$ .

Solve your own maths question free →