I have a batch of 16 coins, each coin weights either 9g, 10g, or 11g. I split the pile into halves and compare each half on a balance scale and the result is unequal.
Then I take each pile of 8 and perform the same process: split each pile in half and compare the halves from that pile. Both times I get unequal results.
I then repeat the process with the four piles of 4. Again all four weighings are unequal.
I keep going to make eight more weighings comparing the individual coins in each pair formed previously. Again all weighings are unequal.
What are the possible compositions of the original pile of 16 coins?
Just consider a set of 8 to start, one of the two in the first step. What composition can it have?
There can't be five or more of the same type. If there were, at least one of the final four pairs would be a pair of the same type, by the pigeonhole principle.
But there can't be four of the same type either. Suppose the types were a, b, and c, and there were 4 a's. Then the final four pairs must all be either ab or ac (since an 'aa' pair would balance). But two "sibling" pairs (pairs decended from the same quad) can't both be ab (or both ac) or they'd have balanced in the previous step, so they must be one of each. But this is equally true for the other "sibling" pairs, so they both descend from quads with the same composition and THOSE quads would have balanced.
So, the only way a group of 8 can meet the criteria in the puzzle is if the most common type appears 3 times. (It couldn't be less than 3 or there wouldn't be a way to reach 8 total.) And the only way three integers sum to 8 where the largest is 3 is 3 + 3 + 2, so all octets that meet these constraints are 3 of two types and 2 of the third type.
But the two octets in the first weighing can't have the same composition, or they'd balance, so they must have different choices for which type appears only twice. And that means that those two types appear a total of 5 times (3 on one side and 2 on the other) and the remaining type appears 6 times, 3 on each side.
So the only plausible compositions are those that are 6, 5, and 5  which is consistent with Charlie's excellent simulation work.

Posted by Paul
on 20160420 11:00:42 