I wrote a program to look for minimal submarine shooting strategies. For N=3, 4, 5, 7, and 8, the minimal number of shots is 2N-1, and the pattern 0, 0, 0, ..., 0, 1, 2, ..., N-1 (with N 0s) is the lexicographically earliest solution. For N=6, there's a 10-shot minimal solution, 0 0 0 1 0 2 3 4 3 5. The 2N-1 pattern works for N=9, but my program isn't good enough to show minimality in reasonable time. For N=10, the program hasn't found any solutions so far with 19-22 shots. (This doesn't mean much, since the space is huge.) There are a few obvious morphs of a solution: Increment each shot by a constant C; or increment each shot by the number of the shot; or multiply all shots by anything prime to N. This allows me to restrict the search to begin 0, 0, D, with either D=0 or D divides N. There's also a reflect-time morph, but I can't see how to use it to make the program faster. I'm including the program; it's small. The only trick is to retest the previous escaping sub trajectory on the current shooting strategy. Rich ------------------ /* submarine3.c */ /* submarine puzzle */ /* see Math-Fun, Oct 2007 */ /* I can assume any solution begins 0,0,D with D=0 or D a divisor of N */ #define N 10 #define Nshots 22 int shots[100]; int recheck, rchi, rchj; nextshot() { int i; for (i=Nshots-1;i>=0;i--) { a: shots[i]++; if ((i==2) && (N % shots[2])) goto a; if (shots[i]<N) return; #if 1 if (i<=4) printf("%d,%d,%d,%d\n",shots[0],shots[1],shots[2],shots[3]); #endif shots[i]=0; recheck=0; }; } int check() { int i,j,k; for (i=0;i<N;i++) { for (j=0;j<N;j++) { for (k=0;k<Nshots;k++) { if (((i+j*k)%N) == shots[k]) break; }; if (k==Nshots) /* start i, velocity j has no hit */ { rchi=i; rchj=j; recheck=1; return 0; }; }; }; return 1; } main() { int i,v; printf("submarine3 N=%d Nshots=%d\n",N,Nshots); for (i=0;i<100;i++) shots[i]=0; recheck=0; for (;;) { if (recheck) /* see if last failure is fixed */ { if (((rchi+rchj*(Nshots-1))%N)!=shots[Nshots-1]) goto nxsh; }; v = check(); if (v) { printf("win N = %d, Nshots = %d\n", N, Nshots); for (i=0;i<Nshots;i++) printf(" %d",shots[i]); printf("\n"); exit(); }; nxsh: nextshot(); if (shots[1]) { printf("lose N = %d, Nshots = %d\n", N, Nshots); exit(); }; }; }