Shurl and Watts, at a base on Pluto, are in charge of distributing doyles to more distance outposts. Doyels are the size of peas, all identical, each weighing precisely 1 gram. They are indispensable in hyperspace propulsion systems.
Doyles come in cans of 100 doyles each, and shipments are made up of six cans at a time. The Pluto base has a sensitive spring scale capable of registering fractions of milligrams.
One day, a week after a shipment of doyles, a radio message came from the manufacturing company in Hong Kong, “Urgent. One can is filled with defective doyles, each with an excess weight of 1 milligram. Identify the can and destroy its doyles at once.”
“I suppose,” said Watts, “we’ll have to make six weighings, one doyle from each can.”
“Not so, my dear Watts,” said Shurl. “we can identify the can of defectives with just one weighing.” [And then he goes on to explain how this can be achieved using a single weighing.]
“How absurdly simple!” exclaimed Watts, while Shurl shrugged.
A month later, after the next shipment, another message arrived: “Any of the six cans, perhaps all of them, may be full of defective doyles, each 1 milligram overweight. Identify and destroy all defective doyles.”
“This time,” said Watts, “I suppose we’ll have to weight separately a doyle from each can.”
Shurl put his fingertips together and gazed at a picture of Isaac Asimov on the wall. “A capital problem, Watts. No, I think we can still do it in just one weighing.”
What algorithm does Shurl have in mind?
[From Mathematical Puzzle Tales by Martin Gardner]
PS: The solution of the first weighing problem (one defective can) is actually provided in the original text of this puzzle. I’ve removed it for those who are not familiar with the solution and want to give it a shot.