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.
Answer
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!)
No comments:
Post a Comment