Author 
Topic: Sink The Sub (Read 14696 times) 

 chris
Guest

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")

« Last Edit: Jul 31^{st}, 2002, 12:03pm by william wu » 
IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Sink The Sub
« Reply #1 on: Jul 31^{st}, 2002, 12:23pm » 
Quote Modify

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 bidirectional 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, bigOh 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?

« Last Edit: Jul 31^{st}, 2002, 12:31pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



AlexH
Full Member
Posts: 156


Re: Sink The Sub
« Reply #2 on: Jul 31^{st}, 2002, 12:37pm » 
Quote Modify

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.


IP Logged 



S. Owen
Full Member
Gender:
Posts: 221


Re: Sink The Sub
« Reply #3 on: Jul 31^{st}, 2002, 3:38pm » 
Quote Modify

Yeah OK, CS *theory* folks might solve it more easily, that's what I meant I guess. AlexH's hints are good.


IP Logged 



tim
Junior Member
Posts: 81


Re: Sink The Sub
« Reply #4 on: Jul 31^{st}, 2002, 10:10pm » 
Quote Modify

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 )


IP Logged 



anshil
Newbie
Posts: 41


Re: Sink The Sub
« Reply #5 on: Jul 31^{st}, 2002, 11:52pm » 
Quote Modify

Is the sub allowed to have speed 0, or negative speed?


IP Logged 



AlexH
Full Member
Posts: 156


Re: Sink The Sub
« Reply #6 on: Aug 1^{st}, 2002, 12:18am » 
Quote Modify

anshil: yes. it doesn't really matter if we allow negative positions and velocities.

« Last Edit: Aug 1^{st}, 2002, 12:23am by AlexH » 
IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Sink The Sub
« Reply #7 on: Aug 1^{st}, 2002, 7:20am » 
Quote Modify

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 ndimensional Turing machines.


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



 chris
Guest

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.


IP Logged 



Marshall Crumiller
Guest

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 onedirectional game?


IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Sink The Sub
« Reply #10 on: Aug 5^{th}, 2002, 1:23pm » 
Quote Modify

on Aug 5^{th}, 2002, 12:33pm, Marshall Crumiller wrote: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 onedirectional game? 
 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].

« Last Edit: Aug 5^{th}, 2002, 1:24pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Marshall
Guest

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 circularcould there be some way to treat it as such?


IP Logged 



Jeremiah Smith
Full Member
Beep!
Posts: 172


Re: Sink The Sub
« Reply #12 on: Aug 7^{th}, 2002, 2:05am » 
Quote Modify

Marshall...the solution they just gave would work just fine.


IP Logged 



aero guy
Guest

OK guys, Tim got the answer and Chris illustrated it, but it is suboptimal (sorry for the pun). If you consider the BA 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 AB plane with equation: A=xBt. 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 BA 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 BA 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?


IP Logged 



Rezyk
Junior Member
Gender:
Posts: 85


Re: Sink The Sub
« Reply #14 on: Mar 1^{st}, 2004, 1:51am » 
Quote Modify

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.


IP Logged 



aero_guy
Senior Riddler
Gender:
Posts: 513


Re: Sink The Sub
« Reply #15 on: Mar 8^{th}, 2004, 3:32pm » 
Quote Modify

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.


IP Logged 



Rezyk
Junior Member
Gender:
Posts: 85


Re: Sink The Sub
« Reply #16 on: Mar 10^{th}, 2004, 4:24am » 
Quote Modify

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 notskipping works faster, so it's not "suboptimal" compared to skipping. I also believe the velocities are meant to be taken as limitless.


IP Logged 



aero_guy
Senior Riddler
Gender:
Posts: 513


Re: Sink The Sub
« Reply #17 on: Mar 16^{th}, 2004, 5:59am » 
Quote Modify

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.


IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Sink The Sub
« Reply #18 on: Apr 9^{th}, 2004, 11:26pm » 
Quote Modify

It's amusing to note that we could have added any finite number of variables to complicate the original distance equation s = vt + s_{0}, 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.


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



ASB
Guest

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.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7408


Re: Sink The Sub
« Reply #20 on: Apr 30^{th}, 2004, 1:26am » 
Quote Modify

It cannot work. The sub could compute the same sequence as you do for fireing torpedoes, and just add 1.


IP Logged 



King_T
Newbie
Gender:
Posts: 21


Re: Sink The Sub
« Reply #21 on: May 4^{th}, 2004, 2:54pm » 
Quote Modify

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.


IP Logged 



Three Hands
Uberpuzzler
Gender:
Posts: 715


Re: Sink The Sub
« Reply #22 on: May 12^{th}, 2004, 11:39am » 
Quote Modify

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 )


IP Logged 



evergreena3
Full Member
Gender:
Posts: 192


Re: Sink The Sub
« Reply #23 on: May 13^{th}, 2004, 6:37am » 
Quote Modify

(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!


IP Logged 
You're welcome! (get it?)



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Sink The Sub
« Reply #24 on: May 13^{th}, 2004, 7:00am » 
Quote Modify

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..)

« Last Edit: May 13^{th}, 2004, 7:26am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



