Question

The figure below shows a grid of $10$ squares in a row. Each square has a diagonal connecting its lower left vertex to its upper right vertex. A bug moves along the line segments from vertex to vertex, never traversing the same segment twice and never moving from right to left along a horizontal or diagonal segment. Let $N$ be the number of paths the bug can take from the lower left corner $(A)$ to the upper right corner $(B).$ One such path from $A$ to $B$ is shown by the thick line segments in the figure. Find $\sqrt{N}.$

Answer

Answer: 243

Concepts:lattice paths multiplication principle

Difficulty rating: 2230

Solution:

Put $A = (0, 0)$ and $B = (10, 1).$ Every horizontal and diagonal move goes rightward, so the bug's $x$ -coordinate never decreases, and it crosses each of the $10$ vertical strips exactly once, using exactly one of that square's three rightward segments: the bottom edge, the top edge, or the diagonal.

These ten choices determine the whole path. Each crossing arrives at a definite height (bottom edge: low; top edge or diagonal: high) and departs at a definite height (bottom edge or diagonal: low; top edge: high), so at each vertical line the bug traverses the vertical segment exactly when the arrival and departure heights differ — and each vertical segment is needed at most once, so no segment repeats. The same applies at the ends: the bug starts low at $A$ and finishes high at $B,$ using the end verticals if necessary. Conversely, every sequence of choices yields a valid path.

Therefore $N = 3^{10},$ and $\sqrt{N} = 3^5 = 243.$

2026 AIME II Problem 2

Answer: 243

Difficulty rating: 2230

Solution:

Problem 2 in Other Years