Problem:
Roger the ant is traveling on a coordinate plane, starting at . Every second, he moves from one lattice point to a different lattice point at distance , chosen with equal probability. He will continue to move until he reaches some point for which he could have reached more quickly had he taken a different route. For example, if he goes from to to to to , he stops at because he could have gone from to to in only seconds. The expected number of steps Roger takes before he stops can be expressed as , where and are relatively prime positive integers. Compute .
Solution
Solution:
Roger is guaranteed to be able to take at least one step. Suppose he takes that step in a direction . Let 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 , Roger takes a step in the direction and his path ends.
(2) With probability , Roger again takes a step in the direction , after which he is expected to take another steps.
(3) With probability , Roger takes a step in a direction perpendicular to , after which he is expected to take some other number 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 , Roger takes a step in one of the directions and and his path ends.
(2) With probability , Roger takes a step in one of the directions and , after which he is expected to take an additional steps.
Using these rules, we can set up two simple linear equations to solve the problem.
Since Roger takes one step before his expectation is , the answer is .