On 10/11/07, Steve Witham <sw@tiac.net> wrote:
From: "Michael Kleber" <michael.kleber@gmail.com> --------- You are shooting at a submarine that is moving through Z/nZ at constant velocity -- that is, its position at time t is a+bt (mod n), for some 0 <= a,b < n -- but you don't know a or b. At each time t=0,1,2,..., you can shoot at one position. How quickly can you hit all possible submarines?
For n = one million, I guess you have to shoot about 13815504 shots -- 1e6 * ln( 1e6 ).
That is how many times you have to shoot at random before the chance that you've still missed is <= 1/1e6.
Glad I don't have to pay Steve's ammo bills! Spoiler below ... Now I really will stop thinking about this irritating problem! WFL || || V Consider the special case n prime: during stage (i), the player aims at cell 0 and fires n times. Provided b is nonzero mod n, he gets lucky at time t = - a b^{-1} mod n [where the multiplicative inverse of b is found in a standard fashion using Euclid's algorithm]. Otherwise, the target is stationary: so during stage (ii) he fires once at every other cell in turn. Total cost (at most) 2n-1 slugs.