HMMT 十一月 2019 · 冲刺赛 · 第 26 题
HMMT November 2019 — Guts Round — Problem 26
题目详情
- [13] Dan is walking down the left side of a street in New York City and must cross to the right side at one of 10 crosswalks he will pass. Each time he arrives at a crosswalk, however, he must wait t seconds, where t is selected uniformly at random from the real interval [0 , 60] ( t can be different at different crosswalks). Because the wait time is conveniently displayed on the signal across the street, Dan employs the following strategy: if the wait time when he arrives at the crosswalk is no more than k seconds, he crosses. Otherwise, he immediately moves on to the next crosswalk. If he arrives at the last crosswalk and has not crossed yet, then he crosses regardless of the wait time. Find the value of k which minimizes his expected wait time.
解析
- [13] Dan is walking down the left side of a street in New York City and must cross to the right side at one of 10 crosswalks he will pass. Each time he arrives at a crosswalk, however, he must wait t seconds, where t is selected uniformly at random from the real interval [0 , 60] ( t can be different at different crosswalks). Because the wait time is conveniently displayed on the signal across the street, Dan employs the following strategy: if the wait time when he arrives at the crosswalk is no more than k seconds, he crosses. Otherwise, he immediately moves on to the next crosswalk. If he arrives at the last crosswalk and has not crossed yet, then he crosses regardless of the wait time. Find the value of k which minimizes his expected wait time. ( ) 1 ( ) 9 1 Answer: 60 1 − 10 ( ) 9 k With probability 1 − , Dan reaches the last crosswalk without crossing at any previous site, in 60 ( ) 9 k which case the expected value of his wait time is 30 seconds. Otherwise, with probability 1 − 1 − , 60 k Dan crosses at an earlier crosswalk, in which case the expected value of his wait time is . We want 2 to find the k that minimizes ( ) ( ) ( ) ( ) ( ) ( ) 9 9 9 k k k k k 30 1 − + 1 − 1 − = 30 − 30 − 1 − 1 − 60 2 60 2 60 k Letting a = 1 − , we can use weighted AM-GM: 60 9 1 9 ( ( )) ( ) ( ) 1 9 9 9 9 10 10 10 10 9 a 1 − a = 9 a 1 − a ≤ 10 ( ) 1 1 ( ) ( ) 1 1 9 9 9 9 where equality occurs when 9 a = 1 − a , or a = , meaning that k = 60 1 − . Because 10 10 our original expression can be written as 9 30 − 30 a (1 − a ) , ( ) 1 ( ) 1 9 the minimum occurs at the same value, k = 60 1 − . 10