There is an enemy submarine located at an unknown integer somewhere on the number line. The submarine is moving at a constant integer distance per minute (also unknown, and can be positive or negative). Every minute, you can fire a missile at an integer on the number line in an attempt to destroy the submarine.
Is there a strategy to strike the submarine in a finite amount of time?
Assume that you move first and that you can fire missiles at the number line for as long you need to.
The canonical solution to this problem is that it is possible to strike the submarine in a finite amount of time, by analogy with the method for demonstrating the countability of the rational numbers e.g. at https://www.homeschoolmath.net/teaching/rational-numbers-countable.php.
Thus, it is said, by an exhaustive search of all available values for the ordered pair A (the starting point) and B(t-1) (the velocity of the sub and time of each missile) the submarine must eventually be sunk by this algorithm:
at time t, bomb point A+B(t-1). Since all other possibilities have been eliminated, the submarine must then be sunk, and since we know that A, B and t are finite, that must happen within a finite time.
I have two reservations about this. One arises from this very helpful explanation of the mechanics that I found on the Web:
'There are countably many possible submarine paths, since each is given by an integer start point and speed. Enumerate all of them. On hour h, sink submarine h on the list by bombing its location at that time. Any possible submarine will eventually be be sunk.'
The problem I see here is that we could reorganise this putative list starting with all those cases where at least one sub was at 0 at time 0, all those where the sub was at 0 at time 1, all those where the sub was at 0 at time 2, and so on. We will never run out of submarines, since although their individual defining characteristics are finite, there is an infinite number of finite numbers to choose from - by definition, a finite number is any countable number less than infinity. The algorithm therefore gets stuck bombing point 0 forever. Yet this policy would surely miss all the submarines that never passed through 0.
The second reservation I have concerns the speed of the algorithm - the 'hunting speed'. The analogy with the countability of the rational numbers suggests a fairly linear algorithm. Clearly, if the sub is at rest, it will surely be hit eventually; but can the same be said of any higher integer velocity?
To make this point, let's consider a variant of the problem where the submarine is accelerating at an integer rate. Note that nothing has changed for the purposes of the canonical reasoning here except the defining equation, which is now not A+B(t-1), but AB^(t-1), where A is the starting point B is the constant term, and t is the time.
Actually in theory the variant should be much simpler, since if we start with point AB^1, the only numbers we need consider on one axis of the grid are the perfect powers B^n {1,4,8,9,16,25,27,..} whose density is zero comparative to the natural numbers as a whole - in theory, the faster the sub moves, the easier it should be to sink it.
Say B is positive; then B increases in geometric jumps while the search algorithm plods along linearly. The missiles never catch up. If B is negative, then the impudent sub can even flout the missiles from both ends of the number line at the same time. This example seems to me to undermine the claim that the algorithm is bound to catch up eventually, or at least to require that its bounds be formally proven.
Edited on June 9, 2019, 3:33 am
|
|
Posted by broll
on 2019-06-09 01:38:10 |
Yes (or maybe not)
