All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 No Equal Weighings (Posted on 2016-04-18)
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?

 Submitted by Brian Smith Rating: 3.0000 (1 votes) Solution: (Hide) I will be using a notation of {x,y,z} to represent a set of coins with x 9g coins, y 10g coins, and z 11g coins. In the 1v1 set of weighings the possible weighings are {1,0,0} vs {0,1,0}, {1,0,0} vs {0,0,1}, and {0,1,0} vs {0,0,1}. Combining these into pairs yields three possible sets: {1,1,0}, {1,0,1}, {0,1,1}. Then in the 2v2 set of weighings the possible weighings are {1,1,0} vs {1,0,1}, {1,1,0} vs {0,1,1}, and {1,0,1} vs {0,1,1}. Combining these into quads yields three possible sets: {2,1,1}, {1,2,1}, {1,1,2}. Repeating this process two more times ultimately yields three possible sets for the whole lot of sixteen coins: {6,5,5}, {5,6,5}, and {5,5,6}. Interestingly, if we are told which of the three distributions the sixteen coins have, then the inequality information can be used to identify the weights of the individual coins. For example, assume the sixteen coins are the {5,5,6} distribution. Then the 8v8 weighing must be {3,2,3} < {2,3,3} (or its reflection). Then the 4v4 weighing for the {2,3,3} set must be {1,2,1} < {1,1,2} and the weighing for the {3,2,3} set must be {2,1,1} < {1,1,2}. Continuing backwards in this fashion ultimately identifies the individual coins.

 Subject Author Date Analytic confirmation Paul 2016-04-20 11:00:42 Good business problem solution 2016-04-19 06:33:21 re: computer solution -- sampling of every 1000th valid sequence Charlie 2016-04-18 15:10:27 computer solution Charlie 2016-04-18 14:55:28

 Search: Search body:
Forums (0)