Efficient Purity

Dr. Dobb's Journal December, 2004

By Dennis E. Shasha

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 DrEcco@ddj.com.
Solution to November Dr. Ecco

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.

  1. 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.
  2. How few gratings do you need to get 10 grams of Amflam in a solution that is 90 percent pure Amflam?
  3. 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?
  4. Can you prove the optimality of your strategies?

DDJ