For p an odd prime, I give a solution for the size N = 2p submarine problem in 2N-1 = 4p-1 steps using 2N-2 shots. At t = 0, 2, ... , N-2 shoot square 0. At t = 1, 3, ... , N-3 shoot square t+1. At t = N-1 shoot your foot (this shot is not needed for the submarines). At t = N, N+2, ... , 2N-2 shoot square p = N/2. At t = N+1, N+3, ... , 2N-3 shoot square (t+1+p) mod N. This gives a more clearly structured solution for the size 10 problem than my previous message, and corrects a minor typo in that message. It's known that the size 6 problem can be massaged down to 10 steps. I don't know if size 2p for p > 3 can massage out the unused shot. Best, - Scott

Okay, I think I can prove a thing or two that various folks have observed empirically. Thm 1: If n = p^k, then you hit all subs with the 2n-1 shots (0,...,0,1,2,...,n-1) [with n zeros]. Pf: First, the n shots at 0 hit every sub whose velocity is prime to p. So the remaining subs all have velocities that are a multiple of p. Now we do a little induction. Think of the p^k positions as being colored cyclically with p colors -- so the "red" squares are all 0 mod p, and there are p^(k-1) of them. Every remaining sub only lands on squares of a single color (since p divides velocity), so the remaining subs decompose into p independent cohorts. Shooting at (0,1,2,..,n-1) means that I shoot at a red square every pth shot, so a red sub with velocity v travels pv shots between times we shoot at red. Contracting the "red" picture by a factor of p, the situation is isomorphic to that of a sub for n=p^(k-1) that travels with velocity v, a multiple of p, which we're going to hit by shooting at all the squares in order -- by induction, we get all the red subs. The other p-1 colors work the same way, conveniently interleaved with the reds. QED. Note that if n is just a prime, not a prime power, then this proof reduces to the old understanding: all the subs left after the 0...0 have velocity p, and you pick the sitting ducks off one at a time, as if they were subs in a problem of size p^0=1. As Scott Huddleston pointed out for n=10 and Edwin Clark noted for n<500, we can double this p^n strategy for 2p^n: Thm 2: If n=2p^k, you hit all n subs with the following 2n shots: a) Shoot at 0 for the first p^k even-numbered times b) Shoot at 1 for the next p^k even-numbered times c) Shoot at 0,1,2,...,n-1 for the odd-numbered times. Pf: Color the positions alternately black and white. The (a) shots, coming every other time, make a sub starting on black with velocity v into an isomorphic copy of the n=p^k situation with velocity 2v -- so the (a) shots take out all subs that start on black with velocity prime to p, and likewise the (b) shots for subs that start on white. Finally, the subs with velocity a multiple of p work just as above, again sticking to their own color. I suppose I could have shot at them in the order 1,3,5,... and then 2,4,6,... to better match the proof above, but just running through everything in linear order is the same, since everything prime to p is a generator of the group. (Sorry, it's late, this is a little less coherent that it should have been. But the Sox just won their game...) I don't think the n -> 2n proof can be used again inductively to get 4p^k or 2^j p^k -- it relies on the solution for n consisting of two sequences of shots that can be executed independently of one another and that knock out subs partitioned by velocity into two classes, which the scaled-up 2n version doesn't provide. But maybe there's a nicer way to arrange things? So, empirical people, can you find anything that looks generalizable for n=12 or n=15? These constructions, much to my surprise, make me wonder whether you can always do it in time linear in n. Any reason to think not, anyone? --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.