Solution
Bags on a Digital Scale
Show the problem again
You have n bags, each containing plenty of coins. Every coin in a given bag is either genuine (exactly 10 g) or counterfeit (exactly 9 g), and any combination of bags may be counterfeit, including none or all. You have a digital scale that reports the exact total weight of whatever is placed on it, and you may use it exactly once. You choose how many coins to take from each bag, but you can take at most 30 coins from any single bag. What is the largest n for which you can always tell, from the one reading, exactly which bags are counterfeit?
Worked solution
The answer is 6. If you take k_i coins from bag i, the deficit from the all-genuine total is the sum of k_i over the counterfeit bags. For the reading to identify the set, all 2^n subset sums of (k_1, ..., k_n) must be distinct, so the k_i must be distinct positive integers forming a set with distinct subset sums. The powers of two 1, 2, 4, 8, 16 work with n = 5, but the Conway-Guy sequence does better: {11, 17, 20, 22, 23, 24} has all 64 subset sums distinct and a largest element of 24 ≤ 30. For n = 7 the smallest possible largest element is 44, so 30 coins are not enough; an exhaustive search over all sets of positive integers up to 30 confirms that no 7-element set has distinct subset sums, while 6-element ones exist. Hence n = 6.
Source: Digital-scale variant of the classic coin-weighing puzzle; rests on the distinct-subset-sums problem of Erdos and Conway-Guy. Statement written for AxiomIQ.