Question: Roxy is a frog trying to make it across a stream by hopping between lilypads conveniently arranged along a line. From any lilypad, she can
Roxy is a frog trying to make it across a stream by hopping between lilypads conveniently arranged along a line. From any lilypad, she can hop to any other within 5 feet and she is trying to make it from one bank of the stream to the other in as few hops as possible. Roxy thinks that she can minimize the number of hops by at each hop, leaping to the furthest lilypad she can reach. So for example, if there are lilypads at 1,4,6,7,10, and 13 feet from the near bank and the far bank is at 15 feet, she should hop to the lilypads at 4, 7, and 10 feet before hopping to the far bank. Prove that this strategy always successfully reaches the far bank in the smallest possible number of hops
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
