Maths Olympiad Prep

Library / /50 of 62

Combinatorics Difficulty 6.0 National Olympiad Find the answer United States

Problem:
Roger the ant is traveling on a coordinate plane, starting at (0,0)(0,0). Every second, he moves from one lattice point to a different lattice point at distance 11, chosen with equal probability. He will continue to move until he reaches some point PP for which he could have reached PP more quickly had he taken a different route. For example, if he goes from (0,0)(0,0) to (1,0)(1,0) to (1,1)(1,1) to (1,2)(1,2) to (0,2)(0,2), he stops at (0,2)(0,2) because he could have gone from (0,0)(0,0) to (0,1)(0,1) to (0,2)(0,2) in only 22 seconds. The expected number of steps Roger takes before he stops can be expressed as ab\frac{a}{b}, where aa and bb are relatively prime positive integers. Compute 100a+b100a + b.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Roger is guaranteed to be able to take at least one step. Suppose he takes that step in a direction uu. Let e1e_{1} be the expectation of the number of additional steps Roger will be able to take after that first move. Notice that Roger is again guaranteed to be able to make a move, and that three types of steps are possible:
(1) With probability 14\frac{1}{4}, Roger takes a step in the direction u-u and his path ends.
(2) With probability 14\frac{1}{4}, Roger again takes a step in the direction uu, after which he is expected to take another e1e_{1} steps.
(3) With probability 12\frac{1}{2}, Roger takes a step in a direction ww perpendicular to uu, after which he is expected to take some other number e2e_{2} of additional steps.
If Roger makes a move of type (3), he is again guaranteed to be able to take a step. Here are the options:
(1) With probability 12\frac{1}{2}, Roger takes a step in one of the directions u-u and w-w and his path ends.
(2) With probability 12\frac{1}{2}, Roger takes a step in one of the directions uu and ww, after which he is expected to take an additional e2e_{2} steps.
Using these rules, we can set up two simple linear equations to solve the problem.
e2=12e2+1e2=2e1=12e2+14e1+1=14e1+2e1=83 \begin{aligned} & e_{2} = \frac{1}{2} e_{2} + 1 \Longrightarrow e_{2} = 2 \\ & e_{1} = \frac{1}{2} e_{2} + \frac{1}{4} e_{1} + 1 = \frac{1}{4} e_{1} + 2 \Longrightarrow e_{1} = \frac{8}{3} \end{aligned}
Since Roger takes one step before his expectation is e1e_{1}, the answer is 113\frac{11}{3}.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.