SCHOOL OF COMPUTER SCIENCE

  Puzzle 21: Searching for the truth

A wise but short-sighted toad is looking for the Truth. The toad sees no more than 1 meter away while the Truth is located in the plane at distance at most D meters from the toad. The toad can make jumps, each of length at most 1 meter and after each jump she knows if she came closer to the Truth or not. Show that the toad can find the Truth (i.e. get within distance 1 meter) in at most D + o(D) jumps, for large D.

 

 

  Solution

< back to the main puzzle page