Math Quiz Two

A MathQuiz:

A enemy submarine is sailing through an infinite ocean. Cartographers have laid a Cartesian grid over the ocean, with blocks of 1 km by 1 km. Every whole hour, the submarine emerges exactly at a grid point, and resubmerges immediately. The submarine moves with a constant speed and direction, which is (of course) such that it emerges exactly at a grid point hour after hour. Note that this means that it follows a straight line. Apart from that, nothing is known about the submarine's speed and direction. It's initial position is also unknown. The submarine leaves no trail.

You are given the task to intercept the submarine. To this end, you are issued an infinitely fast helicopter. However, you cannot see below the sea surface, so your only hope is to intercept the submarine while it emerges. You have to be exactly at the right place, exactly at the right time. So every hour, you have to make a decision where you will try to intercept the submarine next. As said, your helicopter is infinitely fast, so you could be at grid point (-googolplex, -googolplex) at 10 hour and at grid point (googolplex, GoogolPlex) at 11. However, you can only check 1 grid-point per hour. You have as much time as you like; however, you must eventually find the submarine.

What strategy will guarantee that you succeed in your mission?

-- StephanHouben

My solution for the submarine problem is for the helicopter to stay in the exact same place. This is finite, for the submarine must pass my point at some time. -- KeithCoogan

There are some variations of this puzzle where some limitation is placed on the initial position (see below under Related Problems), but even in this very general form it is soluble.

Discussion (no spoilers here, please!)

[Is this possible in] finite time? There are an infinite number of rays in a plane. --anon

In finite but arbitrary large time. There are an infinite number of rays, but they are countable [hint, hint]. --sh

I know how to do it, but I'm a mathematician by training and maybe that's regarded as cheating. I'll restrain myself for the moment. :-) -- GarethMcCaughan

The search-space is countable (even under considerably relaxed assumptions) so just enumerate the possibilities and try them one by one. However, the expected (in a statistical sense) number of tries required is infinite. -- VickiKerr

A good way to work with the puzzle is to start with a simple version where the sub starts at 0,0 and has a limited speed (say less than 1000 km/hr), and only moves along the four simple 90-degree paths. Once you do that, start removing the restrictions (starting with the angle, the speed, and then the starting position).

I'll admit I don't see a way to find the sub given an infinitely-variable starting position. My best solution takes about as much time as finding all the integers (give or take a few factors of infinity). Even if the sub moves due north at 1km/hr (Y = Y+1 each hour), finding the X coordinate will take some time. If I'm in the helicopter, I hope I'm getting paid by the hour! --CliffordAdams

I'm not a mathematician, but I just don't get it. If I don't have any information about where the sub started, then no strategy can be better than any other.

True (for strategies that do work), but in that case (no start-point information), all that was asked for was any strategy that works.

Why not just pick the same point every time, then?

That wouldn't work.

: You aren't supposed to find the best strategy, but merely a strategy that always works (given sufficient time). By contrast, one (bad) strategy would be to first assume that the boat started at 0,0 and headed straight North (y = y + speed). Using this simple strategy one would start with speed 1 and count up through all the integers. This strategy obviously fails for (most) other initial conditions.

If the sub could have started out anywhere, and be going in any direction, then -- it seems to me -- me picking the same point over and over (or some other "blind" selection) is the same as me picking random points.

: Here's another hint. Suppose the sub wasn't moving (speed = 0), but was located at an unknown grid point. How could you be sure to eventually find that grid point?

Try all grid points. But if the sub is moving, what's the difference between me trying all grid points, or me sitting in one place waiting for the sub to hit me? Hmmm. If I move around, I'll eventually (after infinite time) have tried all grid points. Then, no matter where the sub started or what it's direction, I'll find it. Someday. A long time from now. However, if I sit still, then I've restricted the number of situations where I can win. The sub could have started right next to me but headed away, and I'll never find it. Ok, I get it. Thanks for the hint.

: Well, moving is the right general idea, but you have to have a plan for how to move (see below for PseudoCode of a working strategy). If you're trying to find a fixed sub at a single unknown point, then every strategy that eventually looks at all points is equally good. If, as here, you're trying to find a sub with fixed but unknown trajectory, then every strategy that eventually looks at all trajectories is equally good. (A strategy "looks at" a trajectory if at some time T it looks at the place that trajectory passes through at time T.) However, most strategies don't eventually look at all trajectories; for instance, the strategy "pick one point, over and over" doesn't, because it misses trajectories that never go through that point.

I throw up my hands in despair. Maths, oh why do you torment me so!

Political Commentary

Alternate mathod, for Soviet subs: Use the cold war to bankrupt their economy (and nearly ruin your own). When they run out of money, you'll find their submarine, rusting and leaking radiation, tied up to a dock. Problem solved.

But from the use of "enemy" and "kilometer", one can easily deduce that the sub is an American sub. ;-)

You can't deduce that, as I'm pretty sure that both us and the Soviets use NauticalMiles. Good joke about "enemy," though. Do you remember this wonderful bumper sticker?: http://www.fourmilab.ch/evilempire/

What's up with the America bashing all of a sudden?

It's not very sudden, and it's not bashing. In beating our sworn enemy, we acted, in some ways, very much like them. It's hard to recognize, while fighting it, just how strange a mindset the cold war put us in. Now that we're somewhat out of it, step back and look at the things we did and said during that time. How much alike were we the Soviets? The bumper sticker, in a deliberate exaggeration, claims exactly alike. As a nation, as an ideal, perhaps we were not so much alike. But ask anyone whose rights were infringed by an illegal FBI wiretap, done as a cold-war necessity, if they felt better than a Soviet citizen who had their phone listened to by the KGB. To them, the difference wasn't so great after all.

Solutions

Here's what you do. Consider that there are countably many starting positions (x, y), and countably many velocities (x', y'). Here, x and y are integer multiples of 1 km, and x' and y' are integer multiples of 1 km/hr. Therefore, there are countably many paths the sub can take according to the problem rules: Z^4 has a 1-1 correspondence with N. Enumerate these paths: p_i corresponds to starting position (x_i, y_i) and velocity (x'_i, y'_i). Then, list the successive positions of each path:

 Time 1Time 2Time 3
 p_1: (x_1, y_1), (x_1, y_1) + (x'_1, y'_1), (x_1, y_1) + 2(x'_1, y'_1), ...
 p_2: (x_2, y_2), (x_2, y_2) + (x'_2, y'_2), (x_2, y_2) + 2(x'_2, y'_2), ...
 p_3: (x_3, y_3), (x_3, y_3) + (x'_3, y'_3), (x_3, y_3) + 2(x'_3, y'_3), ...

Now, look at the diagonal; search at (x_1, y_1) at time 1, (x_2, y_2) + (x'_2, y'_2) at time 2, (x_3, y_3) + 2(x'_3, y'_3) at time 3, and so on.

This is the correct solution. You won. -- StephanHouben

This use of the diagonal reminds me of the classical demonstration that the real numbers are not countable. In words, rather than algebra, the submarine solution says: Make a numbered list of all the possible voyages and on the first hour fly to where the submarine would be at that time if it were on the first voyage and on the second hour fly to where the submarine would be at that time if it were on the second voyage, and so on. If the submarine is on the millionth voyage on the list it will be found after a million hours, or possibly earlier by accident. To the objection that it will take infinite time to create the list, note that the list making can be done on the fly. -- GeoffPickering

Here's some PseudoCode for a sub-finding algorithm. Before starting, pick any point on the grid and call it 0, 0.

 # Variables (all Very-Big-Integers)
 x, y    # possible starting sub coordinates (at time = 0)
 dx, dy  # possible sub speeds (constant)
 tx, ty  # coordinates to test for a sub
 time    # time measured in hours
 step    # major step of algorithm

 # Initialization
 time = 0
 step = 0

 while (TRUE != FALSE) {   # Program relies on consistent logical principles
   for (x = (0-step) ; x <= step ; x = x + 1) {
     for (y = (0-step) ; y <= step ; y = y + 1) {
       for (dx = (0-step) ; dx <= step ; dx = dx + 1) {
         for (dy = (0-step) ; dy <= step ; dy = dy + 1) {
           tx = x + (time * dx)
           ty = y + (time * dy)
           if (fly_to_and_check(tx, ty)) {
             print "found sub at x=", tx, " y=", ty
             return/halt/BlueScreenOfDeath
           }
           time = time + 1
           wait(1 hour)
         }
       }
     }
   }
   step = step + 1
 }

The basic idea is to search an increasing area using increasing speeds. At step=0, it checks for a sub at 0,0 that is not moving (dx=0, dy=0). At step=1, it checks for a sub that started within -1,-1 to 1,1 where dx=-1 to 1, and dy=-1 to 1. At step=2, it checks for a sub that started within -2,-2 to 2,2 where dx=-2 to 2, and dy=-2 to 2. Etc.

To find the (maximum) time required to catch a particular sub, first set "max" to be the maximum value of the sub's starting X-coordinate (relative to search starting point), Y-coordinate (also relative), DX-speed, and DY-speed (all translated to absolute/positive values). The time required to catch a sub will be about:

 time = 0
 for (i = 0 ; i <= max ; i = i + 1) { 
   time = time + (2i + 1)^4
 }

...although one could get lucky earlier. The strategy can be improved by eliminating redundant checking (each increased step above repeats all previous steps), but it makes the strategy harder to follow.

Finally, although the above strategy will find the sub, it won't tell you the speed or heading. If you want that information you can use another loop like:

 wait(1 hour)  # Wait 1 hour after initial spotting
 time = 1
 step = 0
 x = X position last spotted (at time = 0)
 y = Y position last spotted (at time = 0)

 while (TRUE != FALSE) {   # Program relies on consistent logical principles
   for (dx = (0-step) ; dx <= step ; dx = dx + 1) {
     for (dy = (0-step) ; dy <= step ; dy = dy + 1) {
       tx = x + (time * dx)
       ty = y + (time * dy)
       if (fly_to_and_check(tx, ty)) {
         print "found sub (again) at x=", tx, " y=", ty
         print "speed/heading is dx=", dx, " dy=", dy
         return/halt/BlueScreenOfDeath
       }
       time = time + 1
       wait(1 hour)
     }
   }
   step = step + 1
 }

--CliffordAdams (who thought he had better things to do than this ;-)

Related Problems

More Specific

If you restrict the sub's initial position, things go much faster:

The version I remembered said something like the sub was initially within a 1000-KM radius of an initial point.

Using something like the diagonalization above, I was able to figure out a way to find the sub in something like factorial(distance^2) times factorial(speed^2), where the distance is from your search-starting location to the sub's *original* position, and the speed is the sub's constant speed in KM/hour (rounded up to the next integer). (Factorial(n) is n * (n-1) * (n-2) ... * 2 * 1 for those who slept through math.) This is probably not the fastest way.

Too bad this isn't a physics quiz. My preferred solution then is to use the infinitely-fast helicopter to time-travel back into the past and kill the grandparents of whoever invented the infinitely-fast helicopter. Finding the sub should be the least of one's problems then. (The idea of a faster-than-light underwater submarine is also interesting...) -- CliffordAdams

A considerably simpler but still fun problem is to limit the grid to 100 X 100, and have the grid wrap around in both X and Y directions. Since there are only 100^4 (100,000,000) possibilities for speed/direction and starting points, one can obviously do a brute-force solution; the challenge is to find a strategy that does much better than that for every possible speed/location combination.

More General

You can also make the problem a bit more general. Say that the sub is controlled by a (deterministic) computer which doesn't receive input from its surroundings. Even if you know nothing about the computer's program, you can still catch the sub. You do this by simply enumerating all possible computer programs, and then at time T you go to the place were the sub would be at T when he was programmed with computer program T.

Unfortunately, this doesn't work. Suppose it could be done; the chopper has an algorithm A that alleges to catch the sub. But what if the sub (by chance or good intelligence) happens to use the algorithm "At every time step, go to the position 1 km to the north as predicted by algorithm A"? -- StephanHouben

: Unfortunately, your counter-example (spelling?) doesn't work. Suppose you could program the sub to do as you say. Then this would be a computer program too, let's call it P_t. Then, at time t, the helicopter would be at the point where the submarine with program P_t would be at the same time. But the submarine with program t (that is, our submarine) is one kilometre to the north of that position. Contradiction. --AnonymousDonor

The difficulty is enumerating all the programs. You have to enumerate all, and only all, programs that actually produce output at each time T; that is equivalent to solving the halting problem, which you can't do. --GarethMcCaughan

: However, if the processing speed (steps/hour) or memory capacity of the sub is limited, and the helicopter's capacity is not limited (or is sufficiently fast to execute all possible sub-programs in less than an hour), then the helicopter can still catch the sub. Note that even the simple fixed-speed case may require unbounded memory in the helicopter just to keep the number of hours for the algorithm.

... So "doing this faster" is, to some extent, the issue after all. :-) --GarethMcCaughan (who, just in case it's not clear, didn't write the previous paragraph)

The halting problem is a non-issue here. Assume that there is a program that calculates the position at every time t. The helicopter just needs to have a computer slightly, but constantly faster to catch the sub. The helicopter does indeed enumerate all programs, in any order. Say program P is selected at time t1. The helicopter now starts simulating P and because the helicopter's computer is slightly faster than the sub's, it will ultimately catch up at some time t2. E.g., if the helicopter's computer is twice as fast, it will catch up at t2=2*t1. It then moves to that square, trying to catch the sub. (It sat idle all the time in between.) Of course it will take longer for the helicopter to catch up with the sub, if the initial time t1 was larger, but it will catch up. If the simulated program terminates early, the sub simply discards it, and starts over with the next program. So, it is a matter of speed and only a constant speedup is required. --- OlafKummer

The original counterargument seems to hold for me -- no matter what program the helicopter is running, the same code could be run on the sub. If the sub can calculate its next move with that algorithm by the time it needs to make it, it can instead elect to go anywhere else. If the sub's computer is unable to calculate its moves in that time, then the problem becomes ill-defined because the sub itself doesn't know what it's doing. --DavisHerring?

Different

On the other hand, CliffordAdams' (first) suggestion is reminiscent of JohnHortonConway's Angel Problem, contained in his article

J.H. Conway: The Angel Problem. In: Richard J. Nowakowski (ed.): Games of No Chance. Combinatorial Games at MSRI. Workshop, July 11--21, 1994 in Berkeley, CA, USA. Cambridge: Cambridge Univ. Press, (ISBN 0-521-57411-0 /hbk; 0-521-64652-9/pbk). Math. Sci. Res. Inst. Publ. 29, 3-12 (1996).

The simplest of these problems is the following. Consider an infinite chessboard. An Angel sits on square (0,0). Each turn, two things happen: the Angel flies to another (uneaten) square, and then a Devil devours any other square on the chessboard.

Question: Can the Angel always escape the Devil? Answer: Certainly.

Now, limit the Angel; say that he has power n if he can only fly a distance of n squares in each of his turns.

Question: Can the Devil trap the Angel (by surrounding him with an n square-deep moat of eaten squares)?

Answer: Unknown.

Put some more restrictions on the Angel, and the answer is yes. --EricJablow

CategoryMath