Problem of the Week 1164

Stop the Battleship

Solution

The battleship problem was solved by Witold Jarnicki, Joseph DeVincentis, Alberto Monteiro, Derek Smith, James Guilford, Stephen Dupal, Chaim Goodman-Strauss, Peter Saltzman, and Hugh Thomas. One incorrect solution was received.

The key is realizing that the set of possible initial conditions is a countable set. (But we will show below that, remarkably, the problem is solvable in the affirmative even if the initial position and speed are unknown real numbers!) For the given problem one need only enumerate all possible pairs (N = start position, M = speed) and then consider them in sequence. If one has (N, M) at time t, fire a shot at N + t M.

Hugh Thomas (U. of New Brunswick) investigated the real-number version and proved, somewhat surprisingly, that the problem as stated is solvable even if the unknowns M and N are arbitrary real numbers. And Larry Carter (San Diego, Calif.) confirms that he had done the same, also using the idea of partitioning the harmonic series into infinitely many divergent series. This is an unexpected development, since of course the choices are now uncountable and the standard approach to the problem relies so heavily on countability.

Thomas's proof follows.

Consider the Euclidean plane of possible initial conditions: pairs (p, v), with p being the initial position and v the velocity. Each shot knocks out not just a single point, but an infinite strip in the plane. To be precise, if at time t we focus on the point (A, B) and shoot to get the left end of a ship that started at (p = A, v = B), then we would shoot at A + t B on the real line. This knocks out a ship that started at (A, B), but also any ship that started at (a, b) where

A + n B − 4 ≤ a + n b ≤ A + n B.

This inequality defines an infinite strip in the plane of horizontal width 4 and slope -1/n.

Observe next that inside a strip as just discussed, we can always locate a rectangle with sides in the coordinate directions, having width 2, and having height 2/n (its lower left corner will be on the left boundary of the strip). Consider the infinite sequence of such rectangles, one for each n, and subdivide them into infinitely many disjoint families so that the set of heights in each family diverges.

For example, consider heights 2/n where n is even, where n has the form 6k + 3, where n has the form 30k + 5, where n has the form 210k + 7, and so on, using new primes each time. These families are disjoint and each leads to a divergent series. We can use rectangles based on the first family to cover the full vertical strip over [0, 2], and the other families to similarly cover other vertical strips of width 2 so that, in all, we have an infinite family of rectangles R(n) that covers the entire plane.

Now at time n, use rectangle R(n) to decide where to shoot. Determine (A, B) so that the strip determined by (A, B) contains R(n). Shoot at A + n B. This will destroy ships whose initial conditions are in the strip, and hence it will destroy ships whose initial conditions are in R(n). Since the rectangles cover the plane, any ship would be struck at some finite time.

To be exact, note that any strip of the sort that arises is determined by a point and a slope. Given the width-2 rectangle R(n) with lower left corner at (a, b) and height 1/n, we want (A, B) so that this defines the strip for R(n):

A + n B − 4 ≤ x + n y ≤ A + n B

Let

A = n b − 4(n − 1)
B = 4 + (a/n)

Look at the strip determined by (n y − 4(n − 1), 4 + (x/n)). It is given by

a + b n ≤ x + n y ≤ a + b n + 4

This contains rectangle R(n). So at time n, shoot at the point A + n B, which is 4 + a + b n, where (a, b) is the lower-left corner of rectangle R(n). QED.

Lovely!

[Back to Problem 1164]

© Copyright 2013 Stan Wagon. Reproduced with permission.


27 September 2013