Skip to main content

Sink the Submarine


An enemy submarine is somewhere on the number line (consider only integers for this problem). It is moving at some rate (again, integral units per minute). You know neither its position nor its velocity.

You can launch a torpedo each minute at any integer on the number line. If the the submarine is there, you hit it and it sinks. You have all the time and torpedoes you want. You must sink this enemy sub - devise a strategy that is guaranteed to eventually hit the enemy sub.

Related Link:
A similar problem we solved some time back was "Finding a Hermit"

Posted by Aaditya Ramdas (CSE, IITB Alumnus working at Tower Research) in comments!!


  1. well I was asked this question in my morgan stanley interview.. didnt get it without a hint. so well im not posting the ans coz its so good!

  2. ok, i have never seen this problem before, it looked very interesting at first, but in a few mins it seemed rather normal :P

    We don't know the initial position I, velocity V. We know that at time t, he is at I+vt.

    So essentially, if we think of his initial position as a point on the plane formed by IxV, we just have to find it sequentially. So, we do it in an outwardly increasing squares search.

    So at t=0, guess his position I+vt as if his (I,v) was (0,0). Then at t=1, guess his position I+vt as if his (I,v) was (0,1). Then (1,0), (0,-1), (-1,0), then move to the outer square of (1,1) to (-1,-1) and so on.

    Ultimately we have to hit (I,v) so we will catch him at that time. Infact it is pretty easy to calculate the exact time at which you will catch (I,v) - it will be while doing the square covering the points abs(I)+abs(v)...

    It's very similar to proving that rationals are countable.

    And also, it is easy to see that if this problem is generalised to I,v,acceleration a, etc it doesnt matter, solution is simply extendable...

  3. @Ramdas.. correct solution (as usual :P) ..

    BTW, Nice observation regarding acceleration :)

  4. can anyone please give a proof that this solution will work

  5. :-o @Ashu..
    The problem is effectively to find values of I and V.

    So, check for all values of I and V. Since the set NXN is countable set {Also used in proving that set of rational numbers is countable}, we can check for I + VT in countable time and hence get the ship.

    Does that clarify?

    In case you don't know what countably infinite set is, read this wikipedia article.

  6. This comment has been removed by the author.

  7. Well, the above solution is correct. But. I have a different view. Maybe it's not correct.

    Since, I have been given the freedom of using any amount of torpedoes. I can use this fact in my arguments.
    Suppose I am at position 0 at t = 0 on the number line. The initial enemy's position can be odd or even and the magnitude of velocity can also be odd or even,
    So, first at t = 0, I launch at all odd positions. If I hit submarine, its good. Else, now I launch torpedoes at every even positions. If I hit, its good. Else now I again launch torpedoes at every even positions. This time I will certainly hit the submarine.
    The reason being if it is not at odd at t = 0. Then , it is at even, If I do not find the subamrine at even positions the second time, then it is moving with odd |velocity|. This means the third time it will be at even.
    Hope this is correct, given the constraints :-P

    1. Consider any one one function from f: Z X Z to N.(it is possible as both are countable). Now if (a,b) is the pair corresponding to initial position and velocity of submarine, it is destroyed at time f((a,b))


Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"

Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Sent to me by Gaurav Sinha

Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?