HMMT 十一月 2015 · THM 赛 · 第 10 题

英文解析

10. Consider a 10 × 10 grid of squares. One day, Daniel drops a burrito in the top left square, where awingless pigeon happens to be looking for food. Every minute, if the pigeon and the burrito are inthe same square, the pigeon will eat 10% of the burrito’s original size and accidentally throw it intoa random square (possibly the one it is already in). Otherwise, the pigeon will move to an adjacentsquare, decreasing the distance between it and the burrito. What is the expected number of minutesbefore the pigeon has eaten the entire burrito?
    Proposed by: Sam Korsky
    Answer: 71 . 8
    Label the squares using coordinates, letting the top left corner be (0 , 0). The burrito will end up in 10
    (not necessarily different) squares. Call them p = ( x , y ) = (0 , 0) , p = ( x , y ) , . . . , p = ( x , y ).
    1 1 1 2 2 2 10 10 10
    p through p are uniformly distributed throughout the square. Let d = | x − x | + | y − y | , the
    2 10 i i +1 i i +1 itaxicab distance between p and p .
    i i +1
    After 1 minute, the pigeon will eat 10% of the burrito. Note that if, after eating the burrito, the pigeonthrows it to a square taxicab distance d from the square it’s currently in, it will take exactly d minutesfor it to reach that square, regardless of the path it takes, and another minute for it to eat 10% of theburrito.
    Hence, the expected number of minutes it takes for the pigeon to eat the whole burrito is
    ( ) ( )
    9 9
    ∑ ∑
    1 + E ( d + 1) = 1 + E 1 + | x − x | + | y − y |
    i i +1 i i +1 ii =1 i =1
    ( )
    ∑9 = 10 + 2 · E | x − x |
    i +1 ii =1
    ( )
    ∑9 = 10 + 2 · E ( | x | ) + E ( | x − x | )
    2 i +1 ii =2 = 10 + 2 · ( E ( | x | ) + 8 · E ( | x − x | ))
    2 i +1 i
    ( )
    ∑9 = 10 + 2 · 4 . 5 + 8 · · k (20 − 2 k )1
    k =1100 = 10 + 2 · (4 . 5 + 8 · 3 . 3) = 71 . 8