With a postage scale that compares a load against a whole number of ounces, how many weighings find which...
logic/weighing/postage.scale New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
With a postage scale that compares a load against a whole number of ounces, how many weighings find which of two bags of 20 coins holds one heavy and one light coin? A normal coin weighs (exactly) 0.999 ounces; a heavy coin weighs 1.049 ounces; a light coin weighs 0.949 ounces. You have a postage scale that you can set for any whole number of ounces, and it will tell you if the load weighs more or less than the set amount. The scale is sensitive enough to detect that a single normal coin weighs less than one ounce. You have two bags of coins. You know that one bag contains 20 normal coins, while the other contains one heavy coin, one light coin, and 18 normal coins; but you don't know which bag is which. How many weighings do you need in order to find out which bag contains the off-weight coins? -- Fred Galvin <galvin@math.ukans.edu>
Show solution
A nice problem with an elegant solution. The answer is 6, as 6 choose 3
equals 20. Just pair up the 20 coins (from one bag) with the 20
3-member subsets of {1,2,3,4,5,6}. The nth weighing will include those
coins whose subsets include n. If a heavy coin is in the bag, one of
the weighings must include it without the light coin.
-- Lucky
Well done! Bonus question: do you know why the numbers 6 and 20 are
optimal, i.e., why 5 weighings wouldn't be enough for the 20-coin bags
in the puzzle, and 6 weighings wouldn't be enough for bags of 21 coins?
It's because of Sperner's Theorem, which says that, if you have an
n-element set, the maximum number of subsets you can choose with none of
the chosen sets being included in another is n choose k, where k is n/2
rounded to an integer. This is obvious if the chosen sets all have to
be the same size; the point is that you can't do any better by mixing
sizes.
-- Fred Galvin <galvin@math.ukans.edu>