7 submarines are placed on an x, y grid - 0 to 111. They are located on whole numbered locations. Each submarine starts from any selected location with a given fixed speed and fixed direction, reaching another point on the grid every second. The submarines continue simultaneously in the given direction and speed thus reaching the border and deflecting by an elastic collision - same angel about the perpendicular to the edge. Assume no collision with a corner. More then one submarine may share the same location/grid-point - if a location includes more than one submarine all are destroyed.

You are armed with a unique gun that kills a submarine with its bullets. You are allowed to use the gun every second, when submarine reaches a grid point. The gun is not limited with its range, the accuracy is absolute, and you are armed with infinite bullets.

Devise a strategy by which you will kill all 7 submarines in a finite time. How long it will take at most?


1 Answer 1


You can do this with the same method as the previous question.

First, enumerate all possible options for starting positions and directions. Then, every time step, take the next position and direction off of your list, and calculate where a submarine that started there would be by now. (This time, you also have to account for collisions too, so the calculation is not simple arithmetic.) Fire there, and repeat. Since all of the submarines' starting states are included, you will hit each submarine when you reach its state in your list. (It's possible that the shot will miss, but this only happens when the submarine already died by crashing into another one.)

There are 111² possible starting positions, and 111² possible starting directions (because each direction must go from a grid point to a different grid point), and so this will take at most 111⁴ timesteps.

  • $\begingroup$ The calculation of deflection is complex? There is an elegant way to deal with it. $\endgroup$
    – Moti
    Nov 13, 2019 at 5:27
  • $\begingroup$ True! You can calculate as if it were infinite, take the result mod 222, then "fold" the top and right halves onto the bottom left. But it's not necessary to know how to do it for this answer -- you just need to know that you can do it. $\endgroup$
    – Deusovi
    Nov 13, 2019 at 5:29
  • $\begingroup$ NOW you got it - no complex calculation required. $\endgroup$
    – Moti
    Nov 13, 2019 at 5:32
  • $\begingroup$ @Moti Yes, I know that it's possible, but it's not necessary for the answer. The answer only requires that it is possible; you do not need to know how to do it to see that this answer works, so I left it out. $\endgroup$
    – Deusovi
    Nov 13, 2019 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.