A solution
When I first heard the submarine puzzle in the post below, I wasn’t able to solve it until I got some hints. The trick, as with many puzzles and even serious math problems, is to replace the problem at hand with one easy enough you can solve it, but which still captures the essential difficulty of the original problem. This tends to be easier said than done, unless you have a great deal of experience and so-called “mathematical maturity”. Sometimes you have to work your way through a series of gradually harder problems until you settle the whole matter.
Step 1: Assume the submarine starts at position 0 and is traveling with positive speed, i.e. from left to right.
Now it would be pretty useless to say “Just bomb 0 immediately!” in this situation, as this provides you no insight to the original problem. Instead you have to decide what you would do if you missed on the first bombing attempt. Well, suppose the submarine’s speed is as simple as possible: 1. Then the strategy would be to bomb position 1 on the next possible occasion. If this bombing fails, we can conclude that the submarine does not travel with unit speed. Perhaps, then, its speed is 2? If so it would have been at position 2 when you bombed position 1, so the next spot you should target is position 4. If this bombing fails, we conclude the speed is different from 2.
Now you should have the idea of what to do in this simplified scenario: the bombing sequence goes (1,4,9,16,25,…,v^2,…). This is guaranteed to eventually hit the submarine, specifically on the vth bombing, at location v^2, where v is the sub’s speed.
Step 2: Assume the submarine starts at position 0 without putting any constraints on the direction of travel.
This is handled with a small modification to the above strategy: we alternatively bomb to the right and the left of the origin. The bombing sequence goes (1,-2,6,-8,15,-18,28,-32,…). This is messier than the last sequence, but not harder to understand; the negative terms are where the sub would be assuming right-to-left travel.
Step 3: Assume the submarine starts at position m, where m is any integer.
Then we simply translate the last bombing sequence by m. There was nothing special about 0 in the above argument.
Now for the truly tricky and interesting part. For convenience, we can represent the situation of the sub starting at position m with velocity v as an ordered pair (m,v). Such an ordered pair is often called a lattice point (or Gaussian integer, when the plane is thought of as a geometric manifestation of the complex numbers).
Step 4: Remember that the lattice points of the plane are countable.
Informally this just means the set of points (m,v) can be listed out in a systematic way that doesn’t miss or double-count a single member. Here’s one way to do it helpful in our situation, using a spiral winding its way out from (1,1):
In this picture, I didn’t bother plotting any points of the form (m,0), because we know the submarine has non-zero velocity.*
So, what’s the bombing plan for the most general situation? Employ the listing of lattice points illustrated above, and when you get to point (m,v) in the list, bomb the location where the submarine would currently be if it had started with velocity v at point m (a situation we fully understand thanks to Step 3 above). This is guaranteed to hit the sub in finite time - though it may take a rather long time if (m,v) is very far from (1,1)!
By the way, the winding spiral above also proves that the set of all rational numbers is countable, if we merely observe that (m,v) may be identified with the fraction m/v, since v is not zero!
*Actually, if the original problem were modified to include the possibility of a motionless submarine, we would still be fine because of this argument.
