Thread: Another puzzle:

A submarine is travelling with constant speed on a one-dimensional grid. Its position at the end of every minute is always an integer and its velocity per minute is also an integer. You can specify a number for each minute and a missile will hit that number on the grid at the end of the minute.

Does there exist a strategy so that you are guaranteed to hit the vessel at some future time even though you don't know its position and velocity?

(I've worked out a "mathematical" solution but i'm interested to see if anyone has one that doesn't need the maths)

Just to clarify - this grid is unbounded? Infinitely long in either direction?

And the submarine, are there any hidden assumptions - it only moves in one direction?

1. The grid is unbounded (it is more of a line then a grid, i just used the language the problem was originally phrased in when i found it)

2. No other assumptions about the submarine other then what is stated.

no takers?

Okay, here's a solution... It's probably along the lines of what you did. So the submarine's position at time t is determined by its initial position p and velocity v--namely, assuming we start at t = 0, the submarine is at the point p + tv at time t. The space of such initial conditions is countable--p and t are integers. So by choosing some ordering on Z^2 (for example (a,b) < (c,d) if |a|+|b| < |c|+|d|; if they're equal, then if a < c; and if these are equal, if b < d), we can list the initial conditions in a sequence (p_t, v_t), t = 0, 1, ... Then I'd send a missile to p_t + tv_t at time t.

My motivation? Cantor's diagonal argument, of course!

Same as mine, i was wondering if you can give a strategy that does not use the fact that ZxZ is countable (so you can give this problem to people without maths backgrounds). I'm stumped there, so i reverted to giving an example of the surjection from N onto NxN (changing the problem accordingly) on another forum but it is not ideal.

A-ha! I thought of Cantor's diagonal counting argument - but couldn't see how it could apply. Thanks for that (once I've figured it out).