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 hop on them in a specific order (the order is unknown to Kelvin). If Kelvin hops to the wrong lilypad at any 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 reaching the other side?

解析

[ 5 ] Kelvin the Frog is trying to hop across a river. The river has 10 lilypads on it, and he must hop on them in a specific order (the order is unknown to Kelvin). If Kelvin hops to the wrong lilypad at any 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 reaching the 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 ∑ 10 11 hops to actually get across the river. Thus he requires i (10 − i ) + 11 = 176 hops to guarantee i =1 success.