2024 AMC 10 A Problem 24

Inclusion-Exclusion Method

Count the number of valid paths inside one specific unit cube, multiply by the 8 possible unit cubes around the origin, and then subtract the paths that lie on the boundaries between cubes because they are counted more than once.

Step 1: Determine the total number of possible paths

The bee makes 4 moves. Each move is determined by rolling a 6-sided die, corresponding to the positive and negative directions of the 3 axes. Since each roll is independent, we multiply the number of choices.

Step 2: Identify the conditions for a valid path inside one unit cube

A unit cube has 8 vertices. If the bee stays inside one specific unit cube (for example, the cube with coordinates 0 and 1), every vertex it visits has exactly 3 available edges within that cube. To traverse 4 distinct edges, the bee must not make any immediate U-turns. Because the grid is a bipartite graph, a 4-step path without U-turns cannot loop back to reuse an edge. Therefore, avoiding U-turns is both necessary and sufficient.

Step 3: Count valid paths within a single unit cube

Starting at the origin, the bee has 3 available edges in the chosen unit cube. For the second move, it has 3 available edges from the new vertex, but 1 of them goes back where it came from. To avoid a U-turn, it has 2 choices. The same logic applies to the third and fourth moves.

Step 4: Calculate the total across all 8 unit cubes

The origin is surrounded by 8 unit cubes (one for each octant, corresponding to the choices of positive or negative signs for the x, y, and z axes). If we simply multiply the paths per cube by 8, we will overcount paths that lie on the boundaries shared by multiple cubes.

Step 5: Subtract the overcounted paths using Inclusion-Exclusion

A path belongs to multiple unit cubes only if it lies entirely on the boundary between them. The boundaries are 2D faces (unit squares). A valid 4-step path on a unit square must traverse all 4 of its edges, meaning it must form a square cycle. There are 2 such paths per face (clockwise and counterclockwise). How many faces meet at the origin? There are 3 coordinate planes (xy, yz, zx). In each plane, there are 4 faces meeting at the origin (one for each quadrant). So there are 12 shared faces total. Each of these 12 faces is shared by exactly 2 unit cubes. No valid path can belong to 3 cubes, because the intersection of 3 cubes is a single edge, which cannot hold a 4-step path.

Step 6: Calculate the final probability

We subtract the overcounted paths from the uncorrected total to find the exact number of distinct valid paths. Finally, we divide by the total number of paths to find the probability.

Dimensional Classification Method

Instead of using subtraction, we can partition the valid paths into two distinct groups: paths that move in all 3 dimensions (which uniquely identify one unit cube) and paths that stay in a 2D plane.

Step 1: Analyze the 24 paths inside a single unit cube

As established, there are 24 valid paths inside a single unit cube. We can divide them into two categories based on how many dimensions they explore. There are 3 faces connected to the origin. A path staying on one of these faces must be a square cycle (2 paths per face). Thus, 6 paths stay entirely in 2D. The remaining paths must venture into all 3 dimensions.

Step 2: Count the total number of 3D paths

A 3D path inside the first octant visits +1 in the x, y, and z directions. Because it extends into all three dimensions, it cannot fit inside any other unit cube. Therefore, we can safely multiply the 18 paths by the 8 possible unit cubes without any risk of overcounting.

Step 3: Count the total number of 2D paths

A 2D path never leaves its coordinate plane. There are 3 coordinate planes (xy, yz, zx). Within each plane, there are 4 quadrants, and each quadrant forms a 1×1 square face connected to the origin. Each face has exactly 2 valid paths (the clockwise and counterclockwise cycles). We can count these directly without worrying about unit cubes.

Step 4: Combine the cases to find the probability

Since a path cannot be both 2D and 3D, these categories are mutually exclusive. We add them together to get the total number of valid paths, and then divide by the 1296 possible random walks.