No Equal Weighings (Posted on 2016-04-18)

	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
	Puzzle Answer	K Sengupta	2023-09-20 00:29:41
	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