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 atone 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 differentcrosswalks). Because the wait time is conveniently displayed on the signal across the street, Dan employsthe following strategy: if the wait time when he arrives at the crosswalk is no more than k seconds, hecrosses. Otherwise, he immediately moves on to the next crosswalk. If he arrives at the last crosswalkand has not crossed yet, then he crosses regardless of the wait time. Find the value of k which minimizeshis expected wait time.
解析
英文解析
- [13] Dan is walking down the left side of a street in New York City and must cross to the right sideat one of 10 crosswalks he will pass. Each time he arrives at a crosswalk, however, he must wait tseconds, where t is selected uniformly at random from the real interval [0 , 60] ( t can be different atdifferent 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 thank seconds, he crosses. Otherwise, he immediately moves on to the next crosswalk. If he arrives at thelast crosswalk and has not crossed yet, then he crosses regardless of the wait time. Find the value ofk which minimizes his expected wait time.
( )
( )1
Answer: 60 1 −19
( )10
k 9
With probability 1 − , Dan reaches the last crosswalk without crossing at any previous site, in
( )60
k 9
which case the expected value of his wait time is 30 seconds. Otherwise, with probability 1 − 1 − ,
k 60
Dan crosses at an earlier crosswalk, in which case the expected value of his wait time is . We wantto find the k that minimizes 2
( ) ( )
( ) ( ) ( ) ( )
9 9 9
k k k k k
30 1 − + 1 − 1 − = 30 − 30 − 1 − 1 −
60 2 60 2 60
Letting a = 1 − , we can use weighted AM-GM:k
9 1 960
( ( )) ( ) ( )
1 9
9 9 9
10 10 10
9 a 1 − a = 9 a 1 − a ≤10
( )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
30 − 30 a (1 − a ) ,9
( )
( )1
1 9
the minimum occurs at the same value, k = 60 1 − .
10