Nov 15, 2012
A starship is travelling at constant velocity through discrete, 1-dimensional space. Its velocity is known to be some integral number of units per second. You don't know the ship's position or the magnitude of its velocity ahead of time.
Your goal is to destroy the ship by hitting it with a photon torpedo. You can detonate one torpedo per second, instantly, at any single point along the line of space. Any particular point may be targeted as many or as few times as you please. Your supply of torpedoes is unlimited. There is no feedback from misses, but you do know when you hit the ship. Assume time is discrete and aligned between you and the ship.
Devise an algorithm for firing the torpedoes that is guaranteed to hit the ship in some finite amount of time. That is, if the ship's location and velocity details at some point in time were to be revealed, you could calculate the exact number of seconds it would take for your algorithm to find the ship.
Hat tip to @LogicalArthur for sharing this on Facebook the other day. Something tells me I have seen this puzzle in the past, but I don’t recall the original source. If anyone does know the origin of this puzzle, please let me know in the comments.
Solution will be posted next time :-)