[math-fun] Submarine problem
Hi funsters, A colleague posed the following question: --------- 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? --------- Well, he actually asked about n = one million, but you get the idea. I hadn't seen this before; anyone recognize it? I have a plausibly efficient answer, but no proof that it's optimal. I'll wait a few days before sending my heuristic, to give y'all a chance to think about it without contamination. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
I may have misunderstood something here --- as stated, the answer seems easily to be n --- even if the velocity b _is_ known to the player. For if the scenario be mounted on a conveyor travelling at velocity -b, the target remains stationary: and it now becomes obvious that every cell must be tried! WFL On 10/10/07, Michael Kleber <michael.kleber@gmail.com> wrote:
Hi funsters,
A colleague posed the following question:
--------- 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? ---------
Well, he actually asked about n = one million, but you get the idea. I hadn't seen this before; anyone recognize it?
I have a plausibly efficient answer, but no proof that it's optimal. I'll wait a few days before sending my heuristic, to give y'all a chance to think about it without contamination.
--Michael Kleber
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Fred Lunnon wrote:
I may have misunderstood something here --- as stated, the answer seems easily to be n --- even if the velocity b _is_ known to the player.
If the velocity is known, then I completely agree that you can do it in n shots, and no fewer. There are n possibilities for the sub's trajectory, and they never overlap, so each shot can only take out one. In the actual problem, the answer is *larger* than n. There are n^2 possible trajectories, and you certainly hit n of them with your first shot. But you can only hit n-1 with your second: no matter what first pair of shots you take, there's exactly one sub trajectory that you would have hit with *both* of them, so the union only nets 2n-1 of the n^2 possibilities. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Apologies --- I'll pipe down now. WFL On 10/11/07, Michael Kleber <michael.kleber@gmail.com> wrote:
Fred Lunnon wrote:
I may have misunderstood something here --- as stated, the answer seems easily to be n --- even if the velocity b _is_ known to the player.
If the velocity is known, then I completely agree that you can do it in n shots, and no fewer. There are n possibilities for the sub's trajectory, and they never overlap, so each shot can only take out one.
In the actual problem, the answer is *larger* than n. There are n^2 possible trajectories, and you certainly hit n of them with your first shot. But you can only hit n-1 with your second: no matter what first pair of shots you take, there's exactly one sub trajectory that you would have hit with *both* of them, so the union only nets 2n-1 of the n^2 possibilities.
--Michael Kleber
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Fred lunnon -
Michael Kleber