Author |
Topic: Sink The Sub (Read 16749 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 31st, 2002, 12:03pm by william wu » |
 IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Re: Sink The Sub
« Reply #1 on: Jul 31st, 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 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?
|
| « Last Edit: Jul 31st, 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 31st, 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 31st, 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 31st, 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 31st, 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 1st, 2002, 12:18am » |
Quote Modify
|
anshil: yes. it doesn't really matter if we allow negative positions and velocities.
|
| « Last Edit: Aug 1st, 2002, 12:23am by AlexH » |
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Sink The Sub
« Reply #7 on: Aug 1st, 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 n-dimensional 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 one-directional game?
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: Sink The Sub
« Reply #10 on: Aug 5th, 2002, 1:23pm » |
Quote Modify
|
on Aug 5th, 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 one-directional 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 5th, 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 circular--could 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 7th, 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 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?
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Sink The Sub
« Reply #14 on: Mar 1st, 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 8th, 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 10th, 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 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.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Sink The Sub
« Reply #17 on: Mar 16th, 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 9th, 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 + 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.
|
|
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: 7526
|
|
Re: Sink The Sub
« Reply #20 on: Apr 30th, 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 4th, 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 12th, 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 13th, 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: 13730
|
|
Re: Sink The Sub
« Reply #24 on: May 13th, 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 13th, 2004, 7:26am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove