HMMT 十一月 2020 · 团队赛 · 第 7 题

HMMT November 2020 — Team Round — Problem 7

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

解析

[45] Roger the ant is traveling on a coordinate plane, starting at (0 , 0). Every second, he moves from one lattice point to a different lattice point at distance 1, chosen with equal probability. He will continue to move until he reaches some point P for which he could have reached P more quickly had he taken a different route. For example, if he goes from (0 , 0) to (1 , 0) to (1 , 1) to (1 , 2) to (0 , 2), he stops at (0 , 2) because he could have gone from (0 , 0) to (0 , 1) to (0 , 2) in only 2 seconds. The expected a number of steps Roger takes before he stops can be expressed as , where a and b are relatively prime b positive integers. Compute 100 a + b . Proposed by: Carl Schildkraut Answer: 1103 Solution: Roger is guaranteed to be able to take at least one step. Suppose he takes that step in a direction u . Let e be the expectation of the number of additional steps Roger will be able to take 1 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