Efficient Purity

Solution to "Cruise Control," DDJ, November 2004.

1. 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 2⁵ (32) possible answers.
2. 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.
3. 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.

DDJ