wu :: forums
« wu :: forums - Sink The Sub »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 1:24am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: william wu, ThudnBlunder, Eigenray, SMQ, towr, Icarus, Grimbal)
   Sink The Sub
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Sink The Sub  (Read 16733 times)
Three Hands
Uberpuzzler
*****





    Reucserru+Oymai


Gender: male
Posts: 715
Re: Sink The Sub  
« Reply #25 on: May 13th, 2004, 11:50am »
Quote Quote Modify Modify

No, can't be. We're shooting at an enemy sub, not a "staying neutral" sub  Wink
 
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  Tongue
 
I think that this solution isn't really in the spirit of the puzzle, though  Roll Eyes
IP Logged
spazdor
Newbie
*





   


Posts: 4
Re: Sink The Sub  
« Reply #26 on: Oct 31st, 2007, 1:02pm »
Quote Quote Modify Modify

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.
IP Logged
spazdor
Newbie
*





   


Posts: 4
Re: Sink The Sub  
« Reply #27 on: Oct 31st, 2007, 1:18pm »
Quote Quote Modify Modify

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. Tongue Oh well.
IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 919
Re: Sink The Sub  
« Reply #28 on: Oct 31st, 2007, 3:28pm »
Quote Quote Modify Modify

[spam]I didn't reply to this thread as we in Czech use submarines as often as the Swiss Grin, 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 Wink )[/spam]
« Last Edit: Oct 31st, 2007, 3:30pm by Hippo » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Sink The Sub  
« Reply #29 on: Nov 1st, 2007, 9:12am »
Quote Quote Modify Modify

on Oct 31st, 2007, 3:28pm, Hippo wrote:
... we in Czech use submarines as often as the Swiss Grin ...

http://en.wikipedia.org/wiki/Bathyscaphe_Trieste
 
IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 919
Re: Sink The Sub  
« Reply #30 on: Nov 1st, 2007, 11:22am »
Quote Quote Modify Modify

Oh oh, bad joke ... wrong example ...  Embarassed I should rather compare with Nepal. This only illustrates how much I am interested in submarines ...
« Last Edit: Nov 1st, 2007, 11:32am by Hippo » IP Logged
NightBreeze
Newbie
*





   
Email

Posts: 26
Re: Sink The Sub  
« Reply #31 on: Jun 23rd, 2008, 7:06am »
Quote Quote Modify Modify

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 2. 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 2
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 2.  
-----------------------
 
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 2.
-----------------------
 
 
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 2 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!
« Last Edit: Jun 23rd, 2008, 7:14am by NightBreeze » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Sink The Sub  
« Reply #32 on: Jun 25th, 2008, 1:31am »
Quote Quote Modify Modify

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.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Sink The Sub  
« Reply #33 on: Jun 25th, 2008, 2:23am »
Quote Quote Modify Modify

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) .
 
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) as n , we can number the subs such that U(n)/f(n) 0.
 
c) If order the subs by |p|+|v|, show that we can make
liminf [ n - U(n) ]/n 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 ?
limsup U(n)/n < 1 ?
liminf U(n)/n < 1 ?
U(n)/n 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.)
« Last Edit: Jun 25th, 2008, 3:05am by Eigenray » IP Logged
Woett
Newbie
*





   


Posts: 1
Re: Sink The Sub  
« Reply #34 on: Apr 14th, 2010, 2:11pm »
Quote Quote Modify Modify

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?
« Last Edit: Apr 14th, 2010, 2:22pm by Woett » IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Sink The Sub  
« Reply #35 on: Apr 15th, 2010, 10:09am »
Quote Quote Modify Modify

on Apr 14th, 2010, 2:11pm, Woett wrote:

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?

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

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board