My previous guess about the minimum number of shots needed to shoot n x n subs, call that m, was: m = n ln n Which is way too high. Now that we have a better idea how many shots are needed, I have decided to revise my guess. In order to be "realistic," I need to know the number of distinct "strategies" of m shots, since out of n ^ m possible sequences of moves, many are symmetrical or even identical. So given a function s( n, m ) = the number of distinct strategies for m shots at n x n subs ask, what's the probability for a given m, that none of the possible shooting strategies will shoot all the subs? I get this: ( 1 - ( 1 - ( 1 - 1/n )^m ) ^ (n^2) ) ^ s( n, m ) (If s(n,m) were just n^m, then this expression in C would be pow(1-pow(1-pow(1-1/n,m),pow(n,2)),pow(n,m)) which surely should sink a lot of subs.) The m where this comes out to .5 is the median of where I should expect the minimal m. I calculated for n = 10, using my guess at the s() function: n m s( n, m ) P(success of any strategy) P(failure of all) 10 16 2.1e+12 1.3e-09 0 10 15 4.6e+11 9.7e-11 4.0e-20 10 14 1.0e+11 5.2e-12 0.59 10 13 2.3e+10 1.8e-13 0.996 So, it should probably take more than 14 shots, but not more than 15 (it takes 17). Michael Kleber <michael.kleber@gmail.com> responded to my high guess with something that's stuck with me:
But surely the structure of the problem should give us some leverage and let us do better than that, right?
If my new calculations are plausible, they seem to say the structure of the problem is working against us. http://www.tiac.net/~sw/math-fun/pfailall.c --Steve