A ship is sailing at a constant, integral speed along the number line. At time = 0 it is located at position 100, but you do not know its speed or direction. Starting at time = 1 second you can begin dropping one bomb every second at locations you specify in advance. Can you be guaranteed of hitting the ship?
Monday, January 24, 2011
Integer bombing
A ship is sailing at a constant, integral speed along the number line. At time = 0 it is located at position 100, but you do not know its speed or direction. Starting at time = 1 second you can begin dropping one bomb every second at locations you specify in advance. Can you be guaranteed of hitting the ship?
Subscribe to:
Post Comments (Atom)
21 comments:
Blaming a spine-gnawing Carl Jung for weird synchronicity is kind of played out, but there's some next-meta-level bidness going on here.
Not 30 minutes ago I came across this *exact* *same* *problem* on some nerd site somewhere and thought "Hey, that might be a good one for Tha Nuts". And, of course, this comes on the recent heels of the forgotten mystery synch from the archives. "It's little Jungs all the way down".
Did you obfuscate the source for this problem? The statement I saw was slightly different in the particulars.
I was going to lay in wait for a response to my easier expression of the problem then leap out with the generalized submarine version and a link to the source.
In fact, I was about to post a comment on the original post, with one of those cross-pollinating backtrack links to CTN. It wouldn't be hard, because the comment form provides the solution to the botproofing question "What is the derivative of 2x (with respect to x)?"
If that's any indication of the level of reader they enjoy, maybe we're better off here without them.
I didn't look at any comments or even really think about the problem until you posted it here.
--If you know the direction the ship is sailing the problem is trivial:
Assume WLOG that the ship is sailing plus-wise. Let the initial position be P. Then at time t = 1 drop a bomb at P + 1, at t = 2 drop a bomb at P + 4, and in general drop a bomb at P + (t^2) for each t.
--If you don't know the direction then things get trickier. It looks like this works, though:
Let d(t) = P + (-1)^(t+1) * ceil(t/2) * t, where ceil(x) is the ceiling function (i.e. the smallest integer >= x).
...and I now see that I encountered this on the same site that Steve did. First time I'd been to it, though, and I don't remember the path I took to get there.
Oh, wait, now I do. It involved Usenet. I bet Steve's didn't.
I thought I was using a dying technology to find that site. What's Usenet?
Your function looks correct to me. It drops bombs based on an assumed speed of +1, -1, +2, -2, +3 etc.
And now to drop the anticlimatic bomb. You don't know the initial position. (And it's a submarine.)
It would be agreeable if someone could sweep up this case where the initial position is unknown. Then we could consider some interesting questions like:
What if the submarine moves at a constant, integral speed in a two-dimensional Cartesian plane instead of along a number line?
What if the submarine is at a constant, unknown integral depth which must be matched with a calibrated depth charge?
What if the submarine has an unknown, integral mass which we must exactly match with a properly-sized bomb?
What if the submarine is in any one of a large number of oceans, on a large number of planets?
And what, pray tell, if the submarine of unknown mass begins at an unknown position and moves at a constant unknown speed at a constant unknown depth in an unspecified ocean on an unspecified planet and all these constant values are not necessarily integers but any rational numbers?
Very nice generalization of the problem Steve. It was fun imagining.
I couldn't precisely formulate mathematically but I will try anyway.
Starting with the simplest case, as Rasalom pointed out earlier:
x(t) = d(t) * v(t)
where d(t) = {-1 if t%2 == 0, 1 otherwise} and v(t)=t.
Basically, for every variation (depth, mass, planet etc.) we add a term that enumerates the possibilities. If possibilities are finite enumeration just continues from the beginning (like d(t)), if it is infinite enumeration continues (increases infinitely for integral speed case).
Since there are infinitely more rational numbers than integers (integers are subset of rational numbers), rational numbers are not enumerable, there is no solution for that case I think.
You're on the right track, bitkidoku, but a precise mathematical formulation is exactly what we need to be sure we will hit the submarine.
Suppose we back up a bit and consider only whole number values for each of the variables. Suppose further that we restrict the variables to the range 1 to 100. So the submarine can start at any position from 1 to 100 and will travel at constant speed in one direction from 1 to 100. Ten thousand bombs will do the job, but how do you decide where and when to drop them?
Time marches on, gentlemen! No ideas on my simplified expression of the problem?
I'm afraid I'll forget the technique I used during Oracle training and will have to take that boring class again.
I will try to remember to work on this problem during my next long training run.
Wait, what? Did you mean "will travel at constant speed in one direction from either its starting point to 100 or its starting point to 1"? Or "will travel at constant speed, reversing direction when it reaches 1 or 100"?
I.e., does it start somewhere, move in either direction and stop when it reaches either 1 or 100; or does it start somewhere and just keep bouncing back and forth?
If it's the former, what happens if the sub starts at, say, 60 and travels at a speed of 25 units/second? does it stop at 100 or at 110?
I need clarification of the simplified case.
There is an article missing in my simplified statement. Let me try again:
The starting position is an integer from 1 to 100, inclusive.
The speed is a constant integer from 1 to 100, inclusive.
The direction is always "to the right" i.e. in the direction that increases the position value. The submarine never stops or changes direction or speed.
So if the starting position is 25 and the speed is 50, you will have to drop a bomb at position 75 when t=1, or 125 when t=2, etc.
Well, for that you can just enumerate the cases.
Let (i, s) be the initial position and speed of the sub.
First consider the case when s = 1 and i ranges from 1 to 100. To take out all of these potential subs, letting t = time elapsed, you would drop bombs at position 2t for 1 <= t <= 100.
Then consider all the (i, 2) cases. At time 101 the (1, 2) sub is at 203, so you can get these by dropping bombs at 3t - 100 for 101 <= t <= 200.
Then for (i, 3) you drop at 4t - 200 for 201 <= t <= 300, and in general for (i, n) you drop at t(n + 1) - 100(n - 1) for 100s - 99 <= t <= 100s.
The simplified problem was trickier than I realized -- I never actually worked out an algorithm myself. But your approach is obviously effective. It's easy enough to calculate where the sub will be at any time with any given starting parameters. The trick is to enumerate all the possibilities.
Clearly your technique will work if we increase the ranges from 1-100 to 1-200. But what happens if we make the range of one of the parameters unlimited? Thus:
The starting position is a positive integer.
The speed is a constant integer from 1 to 100, inclusive.
Ceteris paribus.
Easy enough, you just enumerate all the possibilities again. Start with i = 1 and let s range from 1 to 100. Then at time t you drop at t^2 + 1.
Then let i = 2 and let s range from 1 to 100.
Meh, I think we can jump straight to the formula:
at time t, drop a bomb at:
c(t/100) + t * (t - 100 * f((t - 1)/100))
where c(x) is the integer ceiling of x and f(x) is the integer floor of x.
I think that works.
Excel confirms your formula [=CEILING(A3/100,1)+A3*(A3-100*(FLOOR((A3-1)/100,1))) where column A contains time values] for several hundred values; it looks good to me. Given any initial position and speed, you can calculate the time at which a bomb will hit the sub.
Now, suppose both parameters are unlimited?
The starting position is a positive integer.
The speed is a constant positive integer.
Let the sub be described by a set of attributes, (a1, a2, a3,...,ak), where ai is an integer for all 1<= i <= k. If you like, let a1 be initial position and a2 be velocity.
Then consider the set, S, of all possible such subs. S has a well-ordering, and that basically solves the problem.
But I will expand a little.
We assume that S is well-ordered (I offer an ordering in my next comment). Then for t = tx we calculate the position of hypothetical sub Sx and drop a bomb so as to hit it. Since our actual sub is at some position, Sz in the ordering, it will be hit at time tz. QED.
A well ordering of the set S:
Let Sj = (aj1, aj2, ..., ajn), Sk = (ak1, ak2, ..., akn) be elements of S.
Let |Sm| be the magnitude of the vector (am1, am2, ..., amn). I.e., SQRT(am1^2 + am2^2 + ... + amn^2).
Then we say that Sj < Sk if |Sj| < |Sk|.
If |Sj| = |Sk|, then Sj < Sk if aj1 < ak1.
If aj1 = ak1, then Sj < Sk if aj2 < ak2.
................
If aj(n-1) = ak(n-1), then Sj < Sk if ajn < akn.
S clearly has a unique least element at (0, 0, 0, ..., 0), which we can use as our first bombing target at t0.
This sounds like a solution to me! But I will still pick a nit.
The fact that a well-ordering of the possible subs exists does not prove that it will be possible to find that well-ordering, without which we won't know where to drop bombs when t > 1.
To crack the nut, we should be able to prove that the sub will be hit for any given list of initial conditions. Rasalom's method requires enumerating all the possible lists of initial conditions that have a magnitude equal or less than that of the given list of initial conditions. This is doable, though perhaps not perfectly intuitive.
My approach is subject to the same constraint, but I think it is easier to visualize. First consider the case where the initial position and speed are positive integers, and call a combination of the two the attitude of a sub. Write the possible initial positions (0, 1, 2, 3 ...) across the top of a paper. Then write the possible speeds down the side. We can then enumerate all the possible combinations using a diagonal pattern, resulting in a well-ordered list of attitudes: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), etc. (When the time comes to consider negative integers, we can extend up and to the left on the paper and use a spiral instead of diagonal pattern, or else switch to an alternating pattern on each axis: 0, 1, -1, 2, -2, 3....)
To respond to a challenge attitude, extend the grid until it is large enough that the diagonal method will intercept the given attitude. It may be a large grid, but it is clearly always finite, and we can see (and count, if we want) the attitudes that we will encounter on the way to meeting the challenge.
When a new variable, such as depth, is introduced, we simply write the well-ordered list of attitudes we found earlier across the top of the page, and the depth values down the side. The diagonal method gives us a well-ordered list of attitude-depth combinations, and we can extend the method for any number of variables.
Irrational variables can be expressed as reduced fractions using two integers, so they require two applications of the diagonal method, but you can skip the negative integers for one of them to save some time.
I thought I gave an explicit construction of my well-ordering, but it's possible I didn't.
I think our methods amount to much the same thing. Instead of taking the magnitude, I could take the sum of the absolute values of the ais, and then I think the two constructions turn out to be pretty much identical.
But if I keep the magnitude I can still construct an enumeration of the tuples pretty easily - simply add a new attribute, ak0 = |Sk|, to the front of each Sk in S, and then order them by a0, a1, a2, ..., an. Since a0 is always non-negative, there is only one Sk with a0 = 0, and there are only a finite number of Sks for any given ak0, this provides total ordering with a unique first element.
Also, we can visualize the magnitudes as concentric circles, spheres, hyperspheres, etc., with radii 0, 1, SQRT(2), SQRT(3), .... Then (in the 2d case) we simply move around the circle starting at theta = 0 and stopping at each of the finite set of points (x, y) where x and y are both integers.
In the case of the sphere and above, you would have some kind of spiral action, but there would still be a set of points with a well-defined order through which you would be swinging that raster.
Post a Comment