|
Help Sheriff Brandt catch a speeding fugitive.
November 01, 2004
URL:http://www.drdobbs.com/dr-ecco-solution/184405911
1. Yes, leave a black square empty next to (say, in a clockwise direction) every empty red square in the same concentric square. When Red places a piece on a square, place a piece having a number one higher in the next empty position in a clockwise direction unless the piece just placed is already covered by another black piece. In Figure 1, Red piece h is covered by h+ (usually h+1), Red piece j is covered by j+, and g is covered by g+. Because every square having 2n squares is even on all sides, this assures dominance by Black.
2. No fixed k works. To see why, call two red squares (i,j) and (i',j') well separated if they share no black squares as neighbors and each has four black squares as neighbors.
In Figure 2, n and n-1 are well separated. Consider a collection of well separated red squares and put the highest red pieces on them. The red square having n on it must have two black pieces neighboring it having numbers greater than n on them. The red square having n-1 on it may have a black piece with n on it, but also another one greater than n. Each well-separated red square must, therefore, consume a black piece value greater than n. Note that the diagonals containing well-separated red squares (i) alternate between well-separated red squares and others; and (ii) must be surrounded by diagonals of red squares that have no well-separated red squares. Therefore, the number of well-separated red squares increases with n/4. Black must use n/2 pieces to cover those, half of those (n/4) must be greater than n and the others must be at least 3n/4. So, these n/2 black pieces must have greater values than any other red pieces. We call those black pieces the high dominators. Further, Black can arrange it so that every empty red square is the neighbor of at least one high dominator. So any piece put on an empty (not well separated) red square can be covered by the high dominator already placed as a neighbor plus one other black piece having a value less than n. Therefore, k is c+n/4, where c is a small constant independent of n. In fact, I conjecture that c is about 2.
DDJ
Back to Article
Dr. Dobb's Journal November, 2004
Dennis is a professor of computer science at New York University. His latest books include Dr. Ecco's Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives (W.W. Norton, 2002) and Database Tuning: Principles, Experiments, and Troubleshooting Techniques (Morgan Kaufman, 2002). He can be contacted at [email protected].
Sheriff Brandt seemed to carry desert dust in his sunbeaten face. He wasn't chewing tobacco, though his mouth moved as if he were. He came quickly to the point:
"A fugitive—a white-collar criminal of great reknown—will drive his Porsche on a flat, straight, lonely six-kilometer desert road sometime tonight.
He prefers to travel on the road because it is faster and he can use cruise control (he's been up for nearly two days). On the other hand, the only hope we police have of trapping him is on that road, because once he crosses the border at the end of the road, he will be hidden by his friends. Also our sensors won't find him in the desert.
"On the road, we have sensors at every kilometer, though the fugitive neither knows this nor can see them. The bad news is that they are not very capable. When queried, each sensor reports either: The car has already passed, or the car has not yet passed. It won't give a precise time.
"For a sensor to report, it must be queried from police headquarters (otherwise, it remains silent). Because the batteries on the sensors run low at night, each sensor can report at most once, though many can be queried simultaneously.
"Also, at each kilometer sensor it's possible to send a signal that raises netting from the road floor. If it's done no more than 10 seconds before the time the car is about to cross that section of the road, then we will trap the rich boy. If done too early, the fugitive will see it, drive into the desert, and we may never get him.
"One of my assistants at the start of the road will report to us the second the fugitive's vehicle passes. We don't think he'll be able to record the fugitive's speed, however. We know the fugitive's sport's car cannot travel faster than 360 kilometers per hour nor will the fugitive drive slower than 30 kilometers per hour.
"To summarize, because of cruise control the fugitive always travels at a constant speed between 30 and 360 kilometers per hour. The fugitive drives along the road at this constant speed unless he sees netting deployed for more than 10 seconds ahead of him. (He can see very far and, once the netting is deployed, we can't get rid of it.) In that case, he would go into the desert and escape.
"We want to capture him as early on the road as possible, so we would like to know his speed."
Warm-Up: If the fugitive travels at either 30, 40, 50, 60, 70, 80, or 90 kilometers per hour, then how many kilometers will it take to know his exact speed?
Solution to Warm-Up: 61 seconds after he arrives at kilometer 0, ask whether the car has passed at kilometer 1. If so, then it is going at 60, 70, 80, or 90; otherwise, it is going slower. Suppose it is going faster: If it is going 80 or 90 kph (or 80/60 or 90/60 kilometers per minute), it passes kilometer 2 at time 120/80 minutes (90 seconds). So, at 91 seconds, see whether the car has passed the sensor at two kilometers. We can use binary search in this way to ensure that by the 3-kilometer sensor, the police can know the speed precisely.
"That was pretty easy," Tyler complained.
The sheriff nodded and said, "Here are some tougher challenges, young man:
Liane and Tyler answered the questions but the sheriff still looked upset. He spoke: "We have so far enjoyed the rather artificial condition that the speeds could be only multiples of 10. Suppose all you knew was that his speed ranged from 30 to 360 kilometers/hour but any intermediate speed is possible. Can you still catch the fugitive by the end of the road without exceeding the 10 second warning time? If not, how much longer would the road have to be?
"For the last question (where any speed between 30 kph to 360 kph is possible), it might help to have sensors that could report over 10 seconds. So the sensor would then report: has not yet passed, has passed in the last 10 seconds, has passed more than 10 seconds ago. Could you net the fugitive in this case in six kilometers?"
I never heard the answer.
Mark Miller was able to clean the ice in 37 moves for one Zamboni and in only 18 moves when using two Zambonis. Michael Birken improved the solution for one Zamboni by using a mixture of A* search and the Floyd-Warshall Algorithm to 35 moves (http://cs.nyu.edu/cs/faculty/shasha/papers/zamboni1.png). Adam Speight showed some 4 Zamboni solutions where each Zamboni crossed only 9 edges.
DDJ
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.