7 submarines are placed on an x, y grid - from negative infinity to positive infinity. They are located on whole numbered locations. Each submarine starts from a location with a given fixed speed and fixed direction, reaching another point on the grid every second. The submarines continuous simultaneously in the given direction and speed thus reaching potentially infinite points of the grid, at the same time each second, if not interrupted.

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.


1 Answer 1


The main thing to do here:

Construct an infinite list of all possible initial states. An initial state consists of a start position and a direction, so each of these states has four "coordinates" (x,y; a,b).
One way you might do this: First, list all the pairs where |x|+|y|+|a|+|b|=0; then all where |x|+|y|+|a|+|b|=1; then all where |x|+|y|+|a|+|b|=2...
Each of these sets is finite, and each possible initial state for a submarine is in one of these sets, so any possible initial state here will be in some finite position on this list.

Now, to execute:

Each turn, take the next element of your list, and shoot the square a submarine that started in that state would be. For instance, if on turn 10 you get the element (0,1;-1,0), you shoot the square (-10,1): that's where a submarine that started at (0,1) and moved (-1,0) each turn would be by now.

This is going to hit each submarine on the turn its state appears on your list. So you will hit all submarines in a finite amount of time. (Additionally, this strategy works in any finite number of dimensions, and with any finite number of submarines!)

  • $\begingroup$ TOO FAST:) could use an approach you draw cubes around the origin as a visual to do the same. $\endgroup$
    – Moti
    Nov 8, 2019 at 3:06
  • $\begingroup$ Since the submarines continue "if not interrupted", and I assume that includes when they have to stop for a submarine that is blocking them, couldn't you miss a submarine if it has to stop and becomes a "different" submarine (in particular, one that you already checked for)? I agree that this is the correct and intended answer but it seems like the question isn't precise enough to exclude this. $\endgroup$
    – hdsdv
    Nov 8, 2019 at 3:42
  • $\begingroup$ You are "correct" that I could be more precise and allow submarines share a grid-point and if they do so, both are killed if hit. $\endgroup$
    – Moti
    Nov 8, 2019 at 4:26
  • $\begingroup$ @Deusovi Actually you did not respond fully/accurately - you should use 5 elements in your "ordering" of shots. $\endgroup$
    – Moti
    Nov 13, 2019 at 3:44
  • 1
    $\begingroup$ @Moti What do you mean by "you miss the two dimension for a direction"? There are four coordinates here: the $x,y$ of the starting position and the $u,v$ of the movement per time-step (the "direction"). These four coordinates uniquely specify the starting state of a ship. $\endgroup$
    – Deusovi
    Nov 13, 2019 at 5:31

Your Answer

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

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