Re: [math-fun] Re: Submarine problem
On 10/11/07, Steve Witham <sw@tiac.net> wrote:
... For n = 2, 3 and 4, all of which have one prime factor, 2n-1 is the minimum.
So... one stage per prime factor, plus a cleanup stage?
So, for n=1000000, 2999998 shots?
But for n = 510510 = 2 * 3 * 5 * 7 * 11 * 17 it would be 510510 + 510509 + 510508 ... + 510104 = 3573549? ...
Er, this still doesn't look quite right to me. For composite number n of cells, the problem may be partitioned according to the HCF m of n and the target velocity b. Suppose the factors m_i (including m_1 = 1 and m_k = n) are arranged in increasing order [and define m_0 = 0]. For the subproblem corresponding to a factor m of n, the player must target each of m (consecutive) cells with n/m (possibly nonconsecutive) shots. We might as well choose consecutive blocks of cells, each starting from cell 0. Now it gets rather murky. At stage i > 0, the first m_{i-1} cells have already been targetted; is it possible to schedule the remaining shots so that they do not overlap orbits previously excluded? [This must be possible if we are allowed to miss turns without penalty.] If so, the number of shots is in total \sum_i (m_i - m_{i-1}) n/m_i , summed over (all) the divisors m_i of n. For example for n = pq a product of two primes p < q, this comes to 4n - 2q - p^2. Finally, all the above assumes that we know n and its factorisation; but suppose on the other hand that we don't even know n --- what is a good strategy now? Enough --- no more! [T'is not as sweet as t'were before.] Fred Lunnon
Okay, Fred has pretty much arrived at the solution I wanted to talk about. Let me summarize, and answer his "rather murky" question in the positive. For a submarine with velocity b, let's say it has "step size" s = gcd(b,n): its route eventually passes through every s'th square, with period n/s. (So if you shoot at any square it passes through for n/s, you're guaranteed to hit it.) Therefore, for n=10^6, you can: a) Take n shots at square 1. This hits all subs with s=1. b) Then take n/2 shots at square 2. This hits half of the subs with s=2; the other half were already hit by the more-than-n/2 shots taken at square 1. c) Then take n/4 shots at square 3, followed by n/4 shots at square 4. If n were a multiple of 3, you'd need n/3 shots at square 3, but a million ain't. Etc: pass through the squares in order, shooting at square k for n/d shots, where d is the smallest divisor of n that is greater than or equal to k. If you instead shoot for n/k shots, ignoring the question of which were divisors, you'd end up taking n*ln(n) shots, just as Steve Witham's heuristic predicted. So we're within that upper bound. And note that when n is prime, this reproduces the 2p-1 shots that Fred mentioned earlier: p shots at 1, then one shot at each other square. Now the big question: Is this optimal? I haven't even been able to prove optimality for the prime case, which really feels like it ought to be easy... --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
participants (2)
-
Fred lunnon -
Michael Kleber