wu :: forums « wu :: forums - Sink The Sub » Welcome, Guest. Please Login or Register. Feb 8th, 2023, 1:29pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Eigenray, Icarus, william wu, SMQ, towr, Grimbal, ThudnBlunder)    Sink The Sub « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Sink The Sub  (Read 16539 times)
- chris
Guest

 Sink The Sub   « on: Jul 31st, 2002, 8:13am » Quote Modify Remove

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

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:

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

 Re: Sink The Sub   « Reply #8 on: Aug 2nd, 2002, 5:25am » Quote Modify Remove

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

 Re: Sink The Sub   « Reply #9 on: Aug 5th, 2002, 12:33pm » Quote Modify Remove

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

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

 Re: Sink The Sub   « Reply #11 on: Aug 5th, 2002, 9:37pm » Quote Modify Remove

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

 Re: Sink The Sub   « Reply #13 on: Dec 11th, 2002, 1:27pm » Quote Modify Remove

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

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

 Re: Sink The Sub   « Reply #19 on: Apr 29th, 2004, 10:06pm » Quote Modify Remove

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: 7522
 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

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
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »