Home > Riddles > The invisible submarine

The invisible submarine

It seems impossible to hit an invisible target that could have started in any position and moved at any entire speed. The key is that their possible trajectories, although infinite, can be ordered in a list.

An invisible submarine moves along the infinite line of integer positions: $$
\ldots,-2,-1,0,1,2,\ldots

$$ Its initial position is an unknown integer $X$. Its speed is also an unknown integer $V$ and remains constant. At instant $t=0,1,2,\ldots$, the submarine is in position: $$

X+tV.
$$ Each day you can choose a single entire position and shoot there. If you get it right, the search ends; If you fail, the submarine keeps moving. Is there a strategy that guarantees success in a finite number of days, regardless of $X$ and $V$?

Hints

Show hints
  1. Don't try to guess a specific trajectory: organize all possible trajectories.
  2. Each trajectory is determined by two integers: initial position and speed.
  3. Pairs of integers can be traversed in a list, for example by going diagonally in $\mathbb{Z}\times\mathbb{Z}$.

Solution

Show full solution

Answer: yes. Success can be guaranteed by listing all possible trajectories. Each trajectory is determined by two integers: $$
(X,V),

$$ where $X$ is the initial position and $V$ the constant speed. If we know that pair, we know where the submarine is on any given day $t$: $$

X+tV.

$$ The problem is that we don't know what the real torque is. But pairs of integers can be put into an infinite list: $$

(x_0,v_0),(x_1,v_1),(x_2,v_2),\ldots

$$ A concrete way to do this is to traverse the $\mathbb{Z}\times\mathbb{Z}$ grid diagonally, as in Cantor's enumeration. The exact order doesn't matter; The important thing is that every pair of integers appears at some point. The strategy is this: on day $t$, you take the pair number $t$ from the list, $(x_t,v_t)$, and fire at the position where the submarine would be that day if its trajectory were that: $$

x_t+t v_t.

$$ Now consider the actual submarine. It has some fixed pair: $$

(X,V).

$$ Since the list contains all pairs of integers, that pair will appear at a finite position in the list. Suppose it appears at position $k$: $$

(X,V)=(x_k,v_k).

$$ So, on day $k$, the strategy fires at: $$

x_k+k v_k.

$$ But since $(x_k,v_k)$ is precisely the real pair, that position is: $$

X+kV.
$$ That is, the exact position of the submarine on day $k$. Therefore, that day the shot hits. You don't know in advance when it will happen, because you don't know where the actual pair is on the list. But if a specific enumeration of $\mathbb{Z}\times\mathbb{Z}$ is set, the day of success is determined by the position occupied in that list by the real pair $(X,V)$. The essential thing is that this position exists and is finite.

Related riddles

Keep practicing

If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.

← Previous: The modular oracle · Next: Dashboard infection →