|
||
Title: Sink The Sub Post by - chris on Jul 31st, 2002, 8:13am I can only think of why this riddle cannot be solved - rather than a solution. With: t: time x: positon of the sub p: position of the sub at t=0 s: speed of the sub we get: x(t) = p + st, i.e. a line in the cartesian plane. The solution has to be a formula which gives me a curve that does not fold back on itself (i.e. for each t I can only launch one torpedo), which will intersect the sub's line at *integer*-coordinates, for any integers p & s. I can't even imagine a curve that would do this for p=0 and s>0 (apart from the trivial solution x(0)=0 in this case, of course), let alone for p,s being abitrary (unknown, positive or negative) integers. Anyone got any further on this one? ( ... in principle; I can map the (infinite) cartesian plane into the (infinite) number line, but not with any "speed" - i.e., the sub might well "run away") |
||
Title: Re: Sink The Sub Post by william wu on Jul 31st, 2002, 12:23pm Yea, I'm stuck on this problem. Also gave it to some smart friends, but to no avail. Apparently there exists a solution according to the contributor, [srowen]. I've subjectively moved the riddle to the hard category. Here are my thoughts so far: I thought about sweeping the number line from left to right or right to left, but if the submarine is travelling in the opposite direction of my sweep, I could easily miss it. Or, even if the sub is travelling in the same direction of my sweep, if I try to target every integer along the way, my torpedo firing rate may be too slow to ever catch up to the submarine, because the submarine may already be ahead of me due to its initial positional offset. I suspected it involves randomness. Perhaps a scattered distribution of torpedoes. Something to do with random processes? I haven't taken that class yet. Then I thought, what if I shot a torpedo at a random integer every minute, and that was my algorithm. The problem says "eventually hit" the enemy sub. But then I realized that this still doesn't guarantee that I'll eventually hit the sub, because 1/inf = 0 probability of success. The torpedo moves at a constant rate, integral units per minute. The torpedo's position as a function of time is a linear equation. What if we shot our torpedoes so that their location as a function of time was exponential? According to this pretty graph I drew, we'd hit it. But I guess the graph doesn't really apply here, because the curves actually consist of discrete points, so you could still miss the sub. What if you do a bi-directional binary search kind of shooting: 0, 1, -1, 2, -2, 4, -4 ... well, then you might just miss it (e.g. the sub is at an odd integer when you get there) and never have a chance of hitting it again. After shooting the sub in an exponential manner for some time, can we eventually assert with confidence that we must have missed the sub, and we should start searching backwards? When we can assert that we know what direction the sub is traveling in, if ever? Perhaps we could use the fact that the sub has to hit certain kinds of numbers along the way. For instance, it will have to hit both odd and even numbers along the way, and some multiples of 10. This is a really obvious statement but perhaps it leads somewhere. [srowen] also told me that computer science people were more likely to solve this riddle. I study EECS but I'm still stuck. What CS concepts tie well with this problem? All the search algorithms come to mind. Running times, big-Oh notation, exponential algos overtaking linear ones. I'm also reminded of hashtables, but that's probably just because the word collision reminds of torpedoes. Hints? |
||
Title: Re: Sink The Sub Post by AlexH on Jul 31st, 2002, 12:37pm Actually I think mathematicians have the best background for this problem, but CS people will tend to have exposure too. Medium sized hint: Think about countable infinities. Big hint: The set of possible starting points for the sub is countable. The set of possible speeds for the sub is countable. Therefore their product is countable. Start counting. |
||
Title: Re: Sink The Sub Post by srowen on Jul 31st, 2002, 3:38pm Yeah OK, CS *theory* folks might solve it more easily, that's what I meant I guess. AlexH's hints are good. |
||
Title: Re: Sink The Sub Post by tim on Jul 31st, 2002, 10:10pm Yeah, I thought that this problem was misplaced, since it took me about 5 seconds. The submarine's position is given by A + Bt. If you know A and B, then just plug in the current t to hit the sub. They're both integers, so you just try all combinations in sequence. If you view the space of possible A's and B's as a grid, just spiral outward. They could be any algebraic numbers and you would still hit. For that matter, the motion of the sub could be determined by any finite computer program and you would still hit (though it might take a bit long to try them all, it's still guaranteed eventually :)) |
||
Title: Re: Sink The Sub Post by anshil on Jul 31st, 2002, 11:52pm Is the sub allowed to have speed 0, or negative speed? |
||
Title: Re: Sink The Sub Post by AlexH on Aug 1st, 2002, 12:18am anshil: yes. it doesn't really matter if we allow negative positions and velocities. |
||
Title: Re: Sink The Sub Post by Eric Yeh on Aug 1st, 2002, 7:20am I agree with Tim. Re: Alex's message (which I also agree w), CS ppl who need further help should consider the equivalence of Turing machines and n-dimensional Turing machines. |
||
Title: Re: Sink The Sub Post by - chris on Aug 2nd, 2002, 5:25am OK - counting. Heh. So if the position of the sub x(t)=p+st, we test in the following manner: 1: p=0, s=0 2: p=0, s=1 3: p=0, s=-1 4: p=1, s=0 5: p=1, s=1 6: p=1, s=-1 7: p=-1, s=0 8: p=-1, s=1 9: p=-1, s=-1 10: p=0, s=2 11: p=0, s=-2 12: p=1, s=2 13: p=1, s=-2 14: p=-1, s=2 15: p=-1, s=-2 16: p=2, s=0 17: p=2, s=1 18: p=2, s=-1 ... etcetera - pluggin in the "current" t in each iteration. Aaargh! Yes! It's elementary! (Isn't it nice initially fixating on the insolubility of a problem - it makes the penny drop so much harder when it does) ... thanks, guys. |
||
Title: Re: Sink The Sub Post by Marshall Crumiller on Aug 5th, 2002, 12:33pm If I'm not mistaken, couldn't you simply fire a torpedo at every second spot? There's no way to "jump over" the ship, because it moves each turn. For example, If you were one unit behind it, on the next it would move one forward, you would move two, thus hitting it. If you were two units behind, you would simply end up 1 unit behind it the next turn, in the said scenario. The only reason this solution wouldn't work would be if the ship was travelling in the opposite direction. Is this a one-directional game? |
||
Title: Re: Sink The Sub Post by william wu on Aug 5th, 2002, 1:23pm on 08/05/02 at 12:33:36, Marshall Crumiller wrote:
You're assuming that the submarine moves at a rate of one unit per minute. It could be moving at 2,000,000 units/minute. And then your 2 unit/minute torpedo scan would never catch up. The problem statement says that you don't know the sub's initial position or speed. To make it clearer, I have replaced the word "speed" with "velocity"; velocity is speed with a direction assigned to it. You don't know whether the submarine is moving toward +inf or -inf. BTW, this is a really great riddle, and one of my new favorites. Thanks again to [srowen]. |
||
Title: Re: Sink The Sub Post by Marshall on Aug 5th, 2002, 9:37pm Does anybody have any ideas? It seems to me that oscillations in guesses would be the way to go. That is to say, we do not know the starting location of the ship, and given a first guess, the ship could be on either side going in either direction. As there are no endpoints on the number line, it seems reasonable that our first guess would be random. From there, we have a few possibilities: 1a) the ship is to the right of our guess, moving to the right 1b) the ship is to the right of our guess, moving to the left 2a) the ship is to the left of our guess, moving to the right 2b) the ship is to the left of our guess, moving to the left How can we come up with a solution that would hit each of these possible scenarios, regardless of the spead of the ship? It's too bad our number line isn't circular--could there be some way to treat it as such? |
||
Title: Re: Sink The Sub Post by jeremiahsmith on Aug 7th, 2002, 2:05am Marshall...the solution they just gave would work just fine. :) |
||
Title: Re: Sink The Sub Post by aero guy on Dec 11th, 2002, 1:27pm OK guys, Tim got the answer and Chris illustrated it, but it is sub-optimal (sorry for the pun). If you consider the B-A plane (B in the horiz, A in the vert), where the sub moves via the equation x=A+Bt, then any given shot, represented as an (x,t) pair creates a line in the A-B plane with equation: A=x-Bt. So, every guess takes out an infinite number of possible sub conditions along the line. For instance, a first shot at time 0 at x=0 creates a line along the A axis, taking out any possible sub conditions where the initial position, A, is zero. It can also be seen that as t increases the slope of the line created in the B-A plane moves towards vertical. Thus, with this in mind we see that though each of Chris's guesses take out an infinite number of possible initial conditions, many are targetted at a condition that was already eliminated. It can be said than that the solution would be reached faster if you spiraled from the center of the B-A plane as Tim suggested, but skipped any pairs that were already eliminated. So, this brings me to a new question, Is there an optimal way of doing this? Keeping track of the hits already made and comparing with the new choice at every time step could take more than a minute of computing time as t got large and you would miss your shot. Is there a relatively simple algorithm that could do this while taking advantage of avoiding duplicate shots? |
||
Title: Re: Sink The Sub Post by Rezyk on Mar 1st, 2004, 1:51am It wouldn't always be faster if you skipped eliminated pairs. Those shots aren't wasteful -- they eliminate just as many (infinity) possible sub locations as any other shot. |
||
Title: Re: Sink The Sub Post by aero_guy on Mar 8th, 2004, 3:32pm Be careful saying things like equally many (infinite). I honestly don't know if Icarus, the infinity guru, would agree with you or not. Though it is true that each shot takes out an infinite amount of new points, every point does not have an equal likelihood. For example, submarines have a limit on their velocity. Thus, points closer to the origin (at least for velocity) may be said to have a greater likelihood than those that do not. Therefore it would be beneficial to skip over duplicates in this region. |
||
Title: Re: Sink The Sub Post by Rezyk on Mar 10th, 2004, 4:24am I agree that every point does not have an equal likelihood, but I don't think it's right to make presumptions about which points have greater or lower probability unless they're explicitly stated in the problem. There are potential random distributions where not-skipping works faster, so it's not "sub-optimal" compared to skipping. I also believe the velocities are meant to be taken as limitless. |
||
Title: Re: Sink The Sub Post by aero_guy on Mar 16th, 2004, 5:59am You are right in that I am involving information outside the problem, but this is implied information as they refer to a sub rather than to a purely theoretical phenomenon. My point is that the answer has been found, but that use of intuition can help to solve it faster. There are of course possible answers that would be found faster without skipping, but on average it can expected that the solution would fe found faster. Way back when I originally posited this idea I though it may be possible to develop an algorithm that did it automatically, but I afterwards I was unable to find one and it does not look like one exists. |
||
Title: Re: Sink The Sub Post by william wu on Apr 9th, 2004, 11:26pm It's amusing to note that we could have added any finite number of variables to complicate the original distance equation s = vt + s0, and we'd still be able to sink the sub eventually, as long as 1) each of the variables takes on a countable number of possible values, and 2) the determinstic relation of each variable to the submarine's current position is known. We could baffle the puzzler with a convoluted equation involving mass, water resistance, salinity, submarine furniture feng shui configurations, etc. :) |
||
Title: Re: Sink The Sub Post by ASB on Apr 29th, 2004, 10:06pm Perhaps this can be further generalized using the idea of taylor polynomials. Suppose we only that a sub starts at an arbitrary position and moves along the axis according to an arbitrary function of time. If I remember the idea of taylor polynomials correctly it implies that any function can be aproximated (ultimately to infinite precision) by some polynomial function. We can spiral outwards infinitely guessing values for variables. You can't count unless you know the maximum number of variables that the function can be precisely condensed to. If you don't know and you underestimate the number of variables to properly specify the function then you risk spirally outwards indefinately. This isn't really a problem though since you could have an infinite number of computers (you do have infinite time so why not infinite computers too). Each computer would spiral outward assuming a different number of variables as maximum number of variables neccesary to specify the function. |
||
Title: Re: Sink The Sub Post by grimbal on Apr 30th, 2004, 1:26am It cannot work. The sub could compute the same sequence as you do for fireing torpedoes, and just add 1. |
||
Title: Re: Sink The Sub Post by King_T on May 4th, 2004, 2:54pm It seems to me that since one only knows the track, and not the location or velocity of the sub, that there are only 2 ways to sink the sub: 1) have all torpedoes hit every spot at the same time 2) surround the sub 1: Go to one infinite end of the number line and shoot a torpedo from a distance/velocity such that it hits that infinity at an infinite number of minutes. Repeat for other infinity a minute later. Alternate your way toward the middle one minute at a time, such that all torpedos hit at an infinite number of minutes. In only an infinite number of minutes, the sub will be caught. For those of you old enough to remember it, I call this the "Missile Command" technique. 2: Go to one infinite end of the number line and launch a torpedo directly down the number line. Repeat for the other end. Please use caution using either technique. Because of the brisk speeds of your ship - keep your arm inside the window. |
||
Title: Re: Sink The Sub Post by Three Hands on May 12th, 2004, 11:39am Method 2, unfortunately, won't work within the constraints of the puzzle, since the torpedos are targetted at specific integers on the number line. Also, I don't think the torpedos are designed with that kind of time delay - either that or they're exploding in your tubes, and the enemy sub will be safe for a *very* long time (an infinite amount of time, in fact :) ) |
||
Title: Re: Sink The Sub Post by evergreena3 on May 13th, 2004, 6:37am (warning - bad joke ahead - warning) Is it a Polish submarine? If so, just knock on the door. When they open it to answer...it's sunk! |
||
Title: Re: Sink The Sub Post by towr on May 13th, 2004, 7:00am You have to account for culture there. for us dutch you should replace 'polish' with belgian for the english with irish (I think) for the australians with new zealand for the new zealanders with australian etc We've all got some other country to pick on for 'dumb' jokes (actually, in my experience the last two, australians and new zealanders, more often involve sheep than stupidity..) |
||
Title: Re: Sink The Sub Post by Three Hands on May 13th, 2004, 11:50am No, can't be. We're shooting at an enemy sub, not a "staying neutral" sub ;) If you're going to go with that kind of attitude, though, you might as well just wait at the surface for them to come up for air, supplies, etc. Patrol the number line, especially anywhere where it is going to pass near to a port, and then just wait for a visual on the sub, or, after a year or two, you can just reasonably assume that everyone on the sub has died :P I think that this solution isn't really in the spirit of the puzzle, though ::) |
||
Title: Re: Sink The Sub Post by spazdor on Oct 31st, 2007, 1:02pm The way to attack this sub is to put its possible positions into one-to-one correspondence with the natural numbers. Define the function pos(A, B, C) as the position at time C of a sub if it starts at position A, with velocity B. pos(A, B, C) = A + B*C We note that A and B are unknown integers, and that at all times during the puzzle, C is known. So really we just want a sequence (I'm calling it p) to search through all ordered pairs as possible values for A and B. Let's just count the lattice points in the Cartesian plane, in a spiral, starting from the origin. pn = (an, bn) p0 = (a0, b0) = (0, 0) p1 = (a1, b1) = (1, 0) p2 = (0, -1) p3 = (-1, 0) p4 = (0, 1) p5 = (1, 1) p6 = (2, 0) p7 = (1, -1) p8 = (0, -2) p9 = (-1, -1) p10 = (-2, 0) and so on. this sequence p will eventually produce every single ordered pair (a, b). SO: your nth shot should be aimed at pos(an, bn, n), or an + n*bn. |
||
Title: Re: Sink The Sub Post by spazdor on Oct 31st, 2007, 1:18pm Er, this solution appears already to have been posted. I just kinda skimmed down the thread and saw that people were still arguing about it. :P Oh well. |
||
Title: Re: Sink The Sub Post by Hippo on Oct 31st, 2007, 3:28pm [spam]I didn't reply to this thread as we in Czech use submarines as often as the Swiss ;D, but the solution is of course obvious (surely mentioned several times) ... the submarines movement is determined by 2 parameters (integers). Renumber the countable set of pairs by natural numbers and fire to the submarine position determined by the i-th pair in the i-th attempt. (You can optimize number of fired torpedos if you don't fire to the already sunken pair. But what is this compared to infinity ;) )[/spam] |
||
Title: Re: Sink The Sub Post by Grimbal on Nov 1st, 2007, 9:12am on 10/31/07 at 15:28:35, Hippo wrote:
http://en.wikipedia.org/wiki/Bathyscaphe_Trieste |
||
Title: Re: Sink The Sub Post by Hippo on Nov 1st, 2007, 11:22am Oh oh, bad joke ... wrong example ... :-[ I should rather compare with Nepal. This only illustrates how much I am interested in submarines ... |
||
Title: Re: Sink The Sub Post by NightBreeze on Jun 23rd, 2008, 7:06am It could very well be that noone is interested in this puzzle anymore, but seeing as this thread has undergone breaks of multiple years before, I figured I'd give it a shot. For submarines with integer velocity/position (v,p), the obvious answer would just be the 'spiral' bijection between the natural numbers and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif2. However the point that aero_guy made is a valid one. It should be possible to make the algorithm more 'efficient', even though efficiency might be hard to quantify in this case. I also worked and solved on the case where the sub has real velocity/position and some positive radius. In that case, a bijection is no longer an option and the solution involves covering a square with a finite number of strips. I figured that this might be possible in the integer case as well. So let me just throw out my thoughts so far. A torpedo launched at x at a time t will be denoted by (t,x). As such, all the submarines that it hits will have to satisfy x = vt + p. This is a line in the v,p plane. Now consider a second shot (t2,x2). The subs hit by this shot satisfy x2 = vt2 + p. This is also a line in the v,p plane and because t2 =/= t, it will intersect with the first line. However it is very well possible that this intersection does not occur in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif2 At the point of intersection, both x = vt + p and x2 = vt2 + p must be true. So x - vt = x2 - vt2 and so v = (x2 - x)/(t2 - t) If this is not an integer, then no submarine has been checked twice. Furthermore if this is not an integer, then s is not an integer either. One more thing to note is that the lines created by a shot (t,x) and a particular shot at the next time, (t+1,x) always intersect at an integer. This is because (t+1-t) = 1 divides anything. ----------------------- So I was wondering if it is possible to create a sequence x1, x2, x3, ... such that for any n: (xn - xi)/(n-i) is not an integer for all 1 <= i < n-1 and so that the lines in the v,p plane created by the equations p = xi - i*v cover all of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif2. ----------------------- Another way to describe this would be as follows: ----------------------- Find a sequence x1, x2, x3, ... so that for any n: For all 1 <= i < n-1, xi is not congruent xn (mod n-i) and the lines p = xi - i*t cover all of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif2. ----------------------- If so, then that would be the ultimate optimal solution to this problem I would say, because at any time t, only t submarines have been checked twice. I'm not sure if it's possible to talk about an 'optimal' solution without a clear definition of efficiency, but even so.. I am kind of intrigued with the problem of creating a sequence of shots which keeps double-checking to a minimum. I suspect it's impossible though. I have not been able to create even a reasonably sized finite sequence with that property, let alone extend it to infinity, let alone cover http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif2 with the lines it produces. One last thing to note is that the x's will alternate like this: even even odd odd even even ... because (x_n - x_n-2)/(n-(n-2)) would otherwise be an integer at some point. There are multiple options when the congruency mod 3 is taken into account. I hope someone takes the challenge! |
||
Title: Re: Sink The Sub Post by Eigenray on Jun 25th, 2008, 1:31am Well, one obvious sequence that meets the first condition is 0,0,1,1,2,2,3,3,4,4,..., or, if you want them to be distinct, pick the smallest possibility at each stage, e.g., 0, 1, 3, 2, 6, 7, 9, 4, 20, 5, 15, 46, 10, 11, 21, 8, 24, 41, 27, 58, 94, 31, 17, 188, 12, 61, 55, 118, 50, 35, ... which continues for at least 1000 terms. But these obviously do not cover the plane. I tried ordering the subs, and then at stage n, hitting the smallest unhit sub I could hit without hitting one that was hit more than 1 step previously. Firing at positions 0, 2, -3, 1, -2, 4, -9, 3, -36, 22, 25, 13, 26, 56, -45, 7, -8, -22, -7, 5, ... hits 7 of the first 10 subs, and 48 of the first 100, within the first 1000 stages (though of course this depends on how you order the subs). At least we can arrange it so that each sub is hit only finitely many times: At stage n, aim at the lowest numbered sub that isn't in the same place as any other sub you've already aimed at. Since at stage n, you've only aimed at n subs, it is always possible to do this. Claim: Every sub is aimed at eventually. Otherwise, let K be the number of the smallest sub never aimed at. For each J<K, sub K can be in the same position as sub J only finitely many times, since the motion is polynomial. So after some finite amount of time, subs 1 though K-1 have been aimed at, and K is not in the same position as any of them. It must then be aimed at, a contradiction. Now, for each sub K, eventually subs 1 through K will all have been aimed at. After this point, you will never hit sub K again, so it can only be hit finitely many times. |
||
Title: Re: Sink The Sub Post by Eigenray on Jun 25th, 2008, 2:23am Let T(n) be the first time you hit sub n, and let U(n) = max(T(1),...,T(n)). a) Show that for any numbering of the subs, we can make n - U(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif. b) Show that we can make U(n) go to infinity as slowly as we like. That is, for any function f(n) such that f(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif as n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif, we can number the subs such that U(n)/f(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif 0. c) If order the subs by |p|+|v|, show that we can make liminf [ n - U(n) ]/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 1. d) Much harder (I don't know): With the order as in (c), how small can you make U(n) asymptotically? E.g., [ n - U(n) ]/n1/2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif ? limsup U(n)/n < 1 ? liminf U(n)/n < 1 ? U(n)/n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif 0 ? (There exist C and N such that for any n > N, there is a strategy with n-U(n) > C sqrt(n) log(n), but I don't know if there's a single strategy that works well for all n, or even infinitely many n.) |
||
Title: Re: Sink The Sub Post by Woett on Apr 14th, 2010, 2:11pm Hmm, I found a completely different solution and it amazes me that no one else uses this approach. So it might be totally wrongheaded; Let pt be the t-th prime number. Let It = [1 - pt, pt]. Now, at time t, shoot at i with probability 1/2pt if it's contained in It. If it's not in It, don't shoot at it. (Or shoot at it with probability 0). Because pt/t diverges and the sub is only O(t) steps away from the origin, there must be a time T, for which: iff t > T, then the sub is contained in It. Now, let T be that time, t > T and P(t) the chance that we did not hit the sub after t minutes. Then: P(t) = (1 - 1/2pT+1)*(1 - 1/2pT+2)*..*(1 - 1/2pt) And it's not very hard to show that this last equation goes to 0 if t goes to infinity (it's similar to proving that the sum of the reciprocals of the primes diverges). So the chance that we will hit the sub eventually is 1. Of course it's debatable if "the chance is 1" and "it will happen" are interchangeable, but I don't think that rules out this approach entirely. Thoughts? |
||
Title: Re: Sink The Sub Post by Aryabhatta on Apr 15th, 2010, 10:09am on 04/14/10 at 14:11:40, Woett wrote:
"chance is 1" and "it will happen" are not the same, and so it does rule out the approach. The problem talks about sinking the sub for sure, only thing that is unknown is when. |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |