Communications of the ACM
Last byte
Finding October
Credit: Getty Images
Two teams, blue and red, play a game in which Red has a submarine we call October, as in Tom Clancy's novel The Hunt for Red October. The Blue admiral is trying to locate the submarine using helicopter-deployed probes that are dropped in the water (see the Figure here). A probe will detect the submarine if the probe's position is within some distance d of the submarine, returning a message either "detected within d" or "not detected within d."
The Blue admiral's goal is to know the position of the submarine within a distance x over a time period T, using as few probes as possible.
Position knowledge goes stale over time because the submarine can move, but the degree of staleness is bounded by the speed of the submarine.
Position knowledge goes stale over time because the submarine can move, but the degree of staleness is bounded by the speed of the submarine. For example, suppose the submarine must move on a line and at most one kilometer in one minute. If the Blue admiral knows October's position at, say, minute t to be no more than distance e with respect to some position p, and e < x, then October's position is within distance x of point p for at least x − e more minutes.
Figure. A set of range probes dropped into the water over time track the position of the red submarine to a tight interval as it moves.
Warm-Up. If a probe is able to detect October's position within a distance of 20 kilometers from the probe or not, can the Blue admiral use some number of probes to determine whether October's position is now between, say, kilometer 40 and kilometer 45 along a particular line segment?
Solution. Yes. For example, suppose Blue drops one probe A at 60 and another B at 65+epsilon for some tiny epsilon. If probe A detects the submarine, but B does not, then the submarine is in the interval [40.. 45].
Challenge. Suppose the submarine can move only on a line segment of length 100 kilometers, and the probe range d is 20 kilometers. At every moment in time up to time 600 minutes from the starting time 0, the Blue admiral would like to know the location of the submarine within an interval of 10 kilometers. Assume the submarine can move one kilometer in one minute. Can the admiral do this with 65 probes or fewer? If so, show how. For convenience, assume the submarine is always at an integer location.
Solution. Start by deploying probes at 20, 30, 40, 50, 60, and 70 measured from kilometer 0 of the line segment. This would be sufficient to know the submarine's location within an interval of size 10. So, for example, the Blue admiral could know the submarine is within [0..9] if the probe at 20 kilometers detects the submarine but no other. The submarine is within [10..19] if the probes at 20 and 30 kilometers detect the submarine but no others. The submarine is in [20..29] if the probes at 20, 30, and 40 detect the submarine but no others. The submarine is in [30..39] if the probes at 20, 30, 40, and 50 detect the submarine but no others. The submarine is in [40..49] if the probes at 30, 40, 50, and 60 detect the submarine (and possibly the probe at 20, too) but no higher ones. The submarine is in [50..60] if the probes at 40, 50, 60, and 70 (and possibly the probe at 30 too) detect the submarine. The submarine is in [61..70] if the probes at 50, 60, and 70 detect the submarine. The submarine is in [71..80] if the probes at 60 and 70 detect the submarine. The submarine is in [81..90] if the probe at 70 detects the submarine. If no probes detect the submarine, then October is in [91..99].
The Blue admiral could know that the submarine is within [0..9] if the probe at 20 kilometers detects the submarine but no other.
At the end of the probing the Blue admiral knows the submarine is at some location [L..L+10]. The admiral now waits 15 minutes, at which point the submarine is in the interval [L-15..L+24], then puts probes at locations L-26, L+25, andL+35.The submarine is at [L-15..L-6] if only probe L-26 detects it. The submarine is at [L-5..L+4] if no probes detect it. The submarine is at [L+5..L+14] if L+25 detects it, but L+35 does not. The submarine is at [L+15..L+24] if L+25 and L+35 both detect it. The admiral can do this probing every 15 minutes so would need nine probes initially, then three probes every 15 minutes. The admiral would thus need 6 + 19 x 3 = 63 probes.
Upstart 1. On a line segment of length M, a detection radius d, and time T, find an algorithm that uses the minimum number of probes so at every moment of time up to time T, the Blue admiral achieves a precision of x; that is, at every moment in time, the admiral knows some position p such that the submarine is in the interval [p-x..p+x] [p-x..p+x].
Upstart 2. Generalizing upstart 1 to two dimensions, now consider an area of size M by M, detection radius d, and time T, and find an algorithm that uses the minimum number of probes the Blue admiral would need so at every moment of time up to time T, the admiral achieves a precision of x; that is, at every moment in time, the admiral knows some position p such that the submarine is in the circle of radius x around p.
Upstart 3. Generalize the two earlier upstarts to k dimensions to achieve a precision on a hypersphere of dimension k and radius x.
Upstart 4. How do these first three upstarts change if the Blue admiral can specify for each probe its detection distance just before deploying it? For example, the admiral can drop a first probe with detection radius 20 kilometers and then another probe with detection radius eight kilometers.
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2018 ACM, Inc.
No entries found