Submarine hunting

You know that a submarine is travelling in an infinite ocean, at a constant speed, in a constant direction. Each second you can bomb a point of choice, and each submarine within a distance ϵ of that point will be destroyed. Is it possible to device a bombing strategy that will certainly destroy the submarine at a finite point in time.

Source

One dimensional case

First will will solve a simpler version, where the submarines can move in a line, not on a plane.

Our submarine has 2 free variables, it's position at time 0 x₀ and it's velocity v. Its position at time t will be x₀ + vt. If we bomb the ocean at position x, the submarine will be destroyed if
x − ϵ < x₀ + vt < x + ϵ
.

Instead of looking at this like bombing a one-dimensional area at different times with moving submarines, we can look at this as bombing a two dimensional area (x, v) where the submarine is at a fixed point (x, v) and not moving. Each bomb we launch covers the area described by the above equation. So we can rewrite our question as follows:

Find a function f : ℤ⁺ → ℝ such that:
{(x,v)∈ℝ²|−ϵ<x₀+vt−f(t)<ϵ}
covers the plain.

If we can find a subset of this set that covers the plane, then the original set also covers the plane.

This figure describes different "areas" that would be bombed if we bomb at time t at position f(t). Each submarine with starting position x and speed v will be destroyed by a specific bombing if the point on the graph is coloured in that respective colour.

Take a look at this equation
−ϵ/2 < x₀ − f₁(t)<ϵ/2 ∩ −ϵ/2 < vt − f₂(t)<ϵ/2

It is easy to see that if f(x)=f₁(x)+f₂(x), this equations implies the above equation (just sum the two equations). It is also easy to see that the bottom equation descibes rectangles with sizes ϵ x ϵ/t where we can choose the position freely.

This figure you can see in blue our original area, and in yellow our new area. You can easily see that orange is a subset of blue, so if our orange tiles can tile the plane, blue can cover it.

Therefore, if we can cover a plane with rectangles with sizes ϵ x ϵ/t, we can destroy the submarine.

To tile our rectangles, we will decide to tile them as follows:

Each lane, marked in red, contains stacked rectangles of different sizes. Each line is also numbered in red, and each rectangle is stacked as follows:

1. The first rectangle is stacked in the respective lane. if l is the lane number, v will be ( − 1)^⌊l/2⌋⌊l/4⌋ϵ.
2. For odd numbered lanes, the following values of x will have added a negative sign.
3. The first rectangle added to the lane will be put at x = u₀/2
4. The second rectangle added to the lane will be stacked on top. x = u₀ + u₁/2
5. Each additional rectangle will be stacked at $x=\sum^{n-1}_{i=0} u_i + u_n/2$

Where u_i is the i-th value assigned to the respective lane.

To tile the full plane, all we have to do is assign each rectancle at the correct lane, such that the sum of every lane will be infinite.

We can do it like this: if at t the prime decomposition has two unique primes, assign it to the lane of the lowest prime. If it isn't do whatever (or skip, or bomb (0,0), nobody cares).

The total sum assigned to a lane will be
$$\frac{1}{p_l} \sum_{i=l}^{\infty} \frac{1}{p_i}$$
And due to this property this will diverge.

Putting this all together, we arrive at the following strategy.

1. Calculate prime decomposition of t
2. If t does not have two primes, bomb 0
3. Otherwise, call l and k the two indexes of the primes
4. calculate v = ( − 1)^⌊l/2⌋⌊l/4⌋ϵ
5. calculate $x=\frac{1}{p_l} \sum_{i=l}^{k-1} \frac{1}{p_i} + \frac{1}{2p_lp_k}$
6. bomb ( − 1)^lx + v/t

Two dimensional case

We use the same technique as for the two dimensional case. This time our submarine has 4 free variables, its position at time 0 (x₀, y₀) and it's velocity (v_x, v_y) The position of a submarine at time t will be
(x₀ + v_xt, y₀ + v_yt)
If we bomb the ocean at position (x, y), the submarine will be destroyed if
(x₀ + v_xt − x)² + (y₀ + v_yt − y)² < ϵ²

Analogious to the previous case, our problem can be restated as follows:

Find a function f : ℤ⁺ → ℝ² such that
{(x,y,v,w)∈ℝ⁴|(x+vt−x(t))²+(y+wt−y(t))²<ϵ²}
is a cover. (where f(t)=(x(t),y(t)))

For this to be a cover, it has to be a cover for every subset. Take the subset (0, 0, v, w). The intersection of our original set with the subset is
{(0,0,v,w)∈ℝ⁴|(vt−x(t))²+(wt−y(t))²<ϵ²}
This can be simplified to
$$\left\{(0,0,v,w) \in \mathbb{R}^4 \middle|\left(v-\frac{x(t)}{t}\right)^2 + \left(w-\frac{y(t)}{t}\right)^2 < \frac{\epsilon^2}{t^2}\right\}$$

This expression is never a cover for the full plane, as this is a set of circles with a surface area of $\frac{\epsilon^2\pi}{t^2}$ The total measure of this cover is $\frac{\epsilon^2\pi^3}{6}$ (source), so this measure can never cover the full plane as it have finite area.