3.50 (2 votes)
Loading...
An easy puzzle with a sweet-ass graphic I whipped up:
A submarine is located
at an integer somewhere along the number line. It is moving at some
integral velocity (an integral number of units per second). Every second you may drop a bomb which will destroy the submarine if the submarine is at that location.
Can you be guaranteed of destroying the submarine? If so, what strategy would you use?
We know that when we throw the first bomb it’s at R, and when we throw the 2nd bomb it’s at R+v (where v is the velocity). So on the Nth bomb, it’s at R+v(N-1).
We know what N is, and so we only need to figure out what are the integers R and v. Let’s try them all!
As we all know, Q (the set of all rational numbers) is countably infinite, and there’s an ordered “path” to traverse all of them. Since all the elements in the set are of the form m/n where m is an integer greater than 0, and n is an integer, we can treat this set as a collection or ordered pairs.
Using the same ordered “path” as used to traverse the set of the rational, we can go over all the possible values for R and v.
That’s basically it. We try all the (R,v) pairs in order. On the Nth pair, we throw a bomb at R+v(N-1). We are guaranteed to hit the sub since we’re checking all the possibilities (well, I could prove this rigorously, but it seems trivial. Proof by negation.)
Or intuitively: we know how many steps the submarine has taken, and since its speed is constant, our aiming point will eventually move faster than it does.
This looks suspiciously similar to a question on a problem sheet I had a couple of months ago…
Using a similar method to Shalom’s, I get this sequence:
0,1,3,3,3,-1,-7,-7,-7,-7,1,13,26,27,28,29,30,15…
There are obviously many other sequences that would work.
Just do it the engineering way: build a big enough orbital strike canon and blast the entire number line in one go ;D
Doesn’t it depend on whether you know the speed and/or the initial location?
If you know one or the other, you can obviously just try every combination, though it could take infinitely long.
One possible problem I see with shalom’s proof of possibility, if I understand what he’s trying to say (using R and v as m and n to get a rational number), is that R and v could be 0 in this problem, and division by 0 takes you out of the real numbers. Or intuitively, yes the aiming point will be moving faster, but it could easily overshoot the target and then continue to stay ahead of it forever.
Shalom’s proof is completely fine. It is exactly what I had in mind as well.
Let me clarify a little. We can completely forget about the “rational number” business. I think it is stated to trigger our memory of the classical proof that the Rationals is countable. The proof involves writing down two countable sets as the indices of a grid, and then traversing the cartesian product in some sort of fashion to cover them all. (See, e.g., the first Google search result of “rationals is countable.”)
The exact same technique can be used here, since R and v are both integers, they are countable. Write them down somehow on the two edges of a grid. (For instance, write “0, 1, -1, 2, -2, 3, -3, …” both vertically and horizontally.) Now we have a grid of all possible (R,v) pairs. Pick a path that covers all (R,v) pairs (as in the proof above). If (R,v) is the N-th pair on that path, drop a bomb at R+v(N-1) at the N-th step. Voila. If one would like, we could even write down explicitly a function f(N) that gives a solution, but I think that would be less instructive than this proof.