HMMT 十一月 2019 · 冲刺赛 · 第 31 题
HMMT November 2019 — Guts Round — Problem 31
题目详情
- [17] James is standing at the point (0 , 1) on the coordinate plane and wants to eat a hamburger. For each integer n ≥ 0, the point ( n, 0) has a hamburger with n patties. There is also a wall at y = 2 . 1 which James cannot cross. In each move, James can go either up, right, or down 1 unit as long as he does not cross the wall or visit a point he has already visited. Every second, James chooses a valid move uniformly at random, until he reaches a point with a hamburger. Then he eats the hamburger and stops moving. Find the expected number of patties that James eats on his burger.
解析
- [17] James is standing at the point (0 , 1) on the coordinate plane and wants to eat a hamburger. For each integer n ≥ 0, the point ( n, 0) has a hamburger with n patties. There is also a wall at y = 2 . 1 which James cannot cross. In each move, James can go either up, right, or down 1 unit as long as he does not cross the wall or visit a point he has already visited. Every second, James chooses a valid move uniformly at random, until he reaches a point with a hamburger. Then he eats the hamburger and stops moving. Find the expected number of patties that James eats on his burger. Proposed by: Joey Heerens 7 Answer: 3 Note that we desire to compute the number of times James moves to the right before moving down to the line y = 0 . Note also that we can describe James’s current state based on whether his y -coordinate is 0 or 1 and whether or not the other vertically adjacent point has been visited. Let E (1 , N ) be the expected number of times James will go right before stopping if he starts at a point with y -coordinate 1 and the other available point with the same x -coordinate has not been visited. Define E (1 , Y ) , E (2 , N ) , and E (2 , Y ) similarly. Then we can construct equations relating the four variables: 1 1 E (1 , N ) = E (2 , Y ) + ( E (1 , N ) + 1) , 3 3 as James can either go up, right, or down with probability 1 / 3 each if he starts in the state (1 , N ) . Similarly, we have 1 1 1 E (2 , N ) = E (1 , Y ) + ( E (2 , N ) + 1) , E (1 , Y ) = ( E (1 , N ) + 1) , 2 2 2 7 and E (2 , Y ) = E (2 , N )+1 . Solving these equations, we get E (1 , N ) = , which is our answer, as James 3 starts in that state having gone left 0 times.