December, 2004: Wireless Futures and Fractal Shores
Solution to "Cruise Control," DDJ, November 2004.
You need 6 kilometers. The troublesome cases occur when the car goes very fast. So we will concentrate on those. If you test kilometer 1 at 20.5 seconds, then you knock out 30 kph (kilometers per hour) to 170 kph (assuming the car has already passed). If you then test kilometer 2 at 26.6 seconds, you knock out 180 kph to 270 kph. Then test kilometer 3 at 33.22, leaving either 280 kph to 320 kph or 330 kph to 360 kph. The first needs three more kilometers. The second needs only two. No fewer than 6 is possible because there are more than 25 (32) possible answers.
You can net the fugitive in 6 kilometers or less. The reason is that cars going at a fast speed can all be caught early on. This time, test marker 1 at 19.5 seconds. If you don't knock out 30 kph to 180 kph, then notice that there are just 16 possibilities left and so the speed can be determined using 4 more kilometer sensors, at which point, netting at 6 kilometers is no problem. So, let's say we still have 190 kph to 360 kph left. Again, test kilometer 2 at 26.6 seconds, leaving just 8 possibilities. If 190 kph to 270 kph are still possible (i.e., if the car hasn't passed), then 3 more kilometers are enough to catch the fugitive. So, let's say that we are left with speeds between 280 kph to 360 kph (i.e., the car has passed kilometer 2 by 26.6 seconds). Then we can net the car if we spring the net at 29.9 seconds. This is the best solution I know of if one cannot both deploy the net and access the sensor at the same kilometer.
Yes, much better. Just deploy the net at 6 seconds at kilometer 1 and you'll catch the car no matter which speed it goes in this range.
This puzzle was inspired by an idea of Peter Carpenter during a drive through Wales.
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].
The biochemist Bill Smith was back. No beard this time, though. "Comportment rules," he muttered with a slight shake of the head. "I still work for the government, though, and I still analyze dangerous chemicals. As usual, I can tell you only as much as you will need to know."
Ecco looked amused, Liane mildly annoyed, and Tyler as if he had just gotten a starring role in Spy Kids. Smith went on.
"There are two compounds, dubbed by the bad guys as Amflam and Britspit, but we'll just call them A and B. We have a 40-gram mixture of the two of them. Our analysis shows that there are 20 grams of A and 20 grams of B. We have no single means of separating them, but we have developed a diffraction grating method to help. Grating A has the property that it will split any mixture into two portions that we call "left" and "right." Suppose the mixture has x grams of A and y grams of B. The left portion will contain 0.75 x grams of A and 0.5 y grams of B. The right portion will get the remainder. See Figure 1.
"The B grating works similarly: The left portion will get 0.5 x grams of A and 0.75 y grams of B. See Figure 2.
"Our goal is to get solutions that are reasonably pure and contain sizable amounts of A.
Warm-up: Using two gratings, can you get a solution that is 75 percent A and that contains 7.5 grams of A? Think a moment before you look at the solution. See Figure 3.
"Now, a much better goal is a solution that has 10 grams of A and is at least 75 percent A.
How many gratings do you need to do that? What would your design look like?" Liane and Tyler found an answer to that, but Smith presented some other challenges to which I heard no answer.
How few gratings do you need to get 10 grams of Amflam in a solution that is 90 percent pure Amflam?
Each grating takes 1 hour. How many hours is the minimum time you need to get that solution assuming you can use as many gratings as you want?
