Bags on a Digital Scale
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?
Related problems & prerequisites
Worth solving first
- Three Switches, One Bulb 5.0/10
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.