HMMT 十一月 2015 · 团队赛 · 第 5 题
HMMT November 2015 — Team Round — Problem 5
题目详情
英文原题
- [ 5 ] Kelvin the Frog is trying to hop across a river. The river has 10 lilypads on it, and he must hopon them in a specific order (the order is unknown to Kelvin). If Kelvin hops to the wrong lilypad atany point, he will be thrown back to the wrong side of the river and will have to start over. Assuming
Kelvin is infinitely intelligent, what is the minimum number of hops he will need to guarantee reachingthe other side?
解析
英文解析
- [ 5 ] Kelvin the Frog is trying to hop across a river. The river has 10 lilypads on it, and he must hopon them in a specific order (the order is unknown to Kelvin). If Kelvin hops to the wrong lilypad atany point, he will be thrown back to the wrong side of the river and will have to start over. Assuming
Kelvin is infinitely intelligent, what is the minimum number of hops he will need to guarantee reachingthe other side?
Proposed by: Alexander Katz
Answer: 176
Kelvin needs (at most) i (10 − i ) hops to determine the i th lilypad he should jump to, then an additional
∑
11 hops to actually get across the river. Thus he requires i (10 − i ) + 11 = 176 hops to guarantee 10
i =1
success.