1 Weighing 5 Fake Coin Types

This puzzle presents a collection of bags of coins, each bag internally consistent but potentially different from the others, and a precise digital scale that can be used only a limited number of times. The candidate must decide how to sample coins from each bag and how many scale readings are necessary to infer, without ambiguity, which weight type each bag contains. It is a classic information-efficiency question: how much can you learn from a single, perfectly accurate measurement, and how should you design that measurement to encode as much information as possible?

Solving it leans on discrete encoding ideas, especially positional number systems and counting arguments about how many possible configurations must be distinguishable. Strong answers typically formalize the mapping from unknown bag types to measurement outcomes, recognize that each outcome must be unique, and reason about the range of achievable total weights. Interviewers listen for candidates who can move beyond ad hoc guesswork to a systematic scheme, articulate why their construction is injective, and connect the puzzle to broader themes of information, coding, and optimal experimental design.

What it tests

This problem class is governed by the principle of positional (base) encoding, where each bag's coin type is treated as a digit in a base-$k$ number, with $k$ being the number of possible types per bag. By choosing the number of coins from each bag as successive powers of $k$, the total weight becomes a unique linear combination that encodes the identity of each bag's coin type. The reason this works is that the sum of weighted deviations (from a reference weight) forms a base-$k$ representation, ensuring that each possible combination of coin types maps to a unique total. This approach leverages the fact that the range of possible sums (from the minimum to the maximum) exactly matches the number of possible type combinations, allowing for perfect distinguishability in a single measurement. The underlying structure is that of information encoding, where each measurement outcome corresponds to a unique configuration, much like reading a number in base-$k$.