At last Drog understood the nature of the beast he was up against. … No creature without tentacles had ever developed true intelligence. That was Etlib’s Law, and it had never been disputed. In a battle between intelligence and instinctive cunning, intelligence always won. It had to. All he had to do was figure out how.
Robert Sheckley, “Hunting Problem”.
I was planning to tell about an exciting probability game problem, but I decided to postpone that and to tell instead about a much easier game. This is one of my favorite simple problems.
We are playing a game of Battleship. The enemy Battleship is located at some integer point A on the number line. It is moving at some constant integer velocity V, meaning on each turn its position changes by V units. Both A and V are unknown. Find a strategy that allows to sink the ship in a finite number of shots.
That wasn’t a very clear formulation so let me explain. Player 1 (P1) chooses an integer number A as the initial position of the ship, and some integer number V as the velocity. On each turn, Player 2 (P2) attempts to guess the current position of the ship. If the guess is correct, the ship is sunk and P2 wins. Otherwise, P1 moves the ship by V units, and the players continue to take turns. We want to find a strategy that allows P2 to sink the ship in a finite number of turns.
Here is how to approach and solve this problem.
First let’s see what do we do if the ship is not moving, i.e. if we know that V=0. It’s trivial: we shoot at all integers one by one until we hit the target. 0, 1, –1, 2, –2, …
Now, what do we do if we know the position of the ship at some moment (let’s say on turn 0, A=A0), but we don’t know the velocity? Again, we can enumerate all values of velocity: V0=0, V1=1, V2=-1,… Then on turn n, we shoot at A0 + n * Vn. As soon as we guess the correct velocity, we sink the ship.
And finally, if both A and V are unknown, we do the same thing: we enumerate all pairs (An, Vn) and shoot at An + n * Vn.
So it doesn’t matter how many parameters define our opponent’s strategy. If the set of all possible strategies is countable, we can guess the strategy in finite time.
“Countable set” is an anagram of “Battle Us Once”