riddle of the day

It seems impossible to hit an invisible target that could have started at any integer position and moved at any integer speed. However, the impossibility has a crack.

The invisible submarine

Master
Numerical territory

Riddle statement

An invisible submarine moves on 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 fire there. If you get it right, the search ends; If you fail, the submarine continues moving.

Is there a strategy that guarantees success in a finite number of days, regardless of X and V?

Show solution

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$ is 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 pair 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. Has some fixed pair:

$ (X,V). $

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

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

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

$ x_k+k v_k. $

But since $(x_k,v_k)$ is precisely the pair real, 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 real 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.