You are trying to hit a moving battleship, but you have no way of monitoring its position. However, you have the following information:
- You know where the battleship started.
- You know when the battleship started moving.
- You know the battleship is only moving along a straight line.
- You know the battleship moves a constant speed per hour, and that speed is an integer. But you do not know what that speed is.
Every hour, you can fire precisely once at any point on that line. Is there a strategy you can use that will guarantee you will hit the battleship in a finite amount of time?
Fun fact, this was an actual brainteaser given to me in the second round interview for a hedge fund internship back in 2011.
Preparing for a brain teaser interview? Check out our ultimate guide to brain teaser interviews.
Solution
Yes. Even though you don’t know the speed of the battleship, you can make guesses that eliminate each possible speed until you eventually guess the correct speed.
Let the starting point be 0 on the line.
- The first hour, you guess 1 to guess that the battleship has been moving at 1 speed for 1 hour.
- The second hour, you guess 4 to guess that the battleship has been moving at 2 speed for 2 hours.
- The third hour, you guess 9 to guess that the battleship has been moving at 3 speed for 3 hours.
You see where this is going – every hour you guess the number of hours elapsed multiplied by the speed you want to eliminate (which in this case means guessing the square of the hour). This strategy eventually guesses all possible whole number speeds and thus will guarantee you hit the battleship in a finite number of hours.
If we allow negative speeds or the battleship to move in either direction along the line, you use the exact same logic, you just won’t get nice round numbers:
- The first hour, you guess 1 to guess that the battleship has been moving at 1 speed for 1 hour.
- The second hour, you guess -2 to guess that the battleship has been moving at -1 speed for 2 hours.
- The third hour, you guess 6 to guess that the battleship has been moving at 2 speed for 3 hours.
And so forth, eliminating each integer speed alternating between positive and negative possibilities.