This question evaluates understanding of combinatorial reasoning, information theory, and decision-tree construction for identifying a single counterfeit coin and whether it is heavier or lighter using constrained balance-scale observations.
Using a balance scale with no weights and exactly three weighings, you have 12 visually identical coins, one of which is counterfeit and either heavier or lighter (unknown). Provide a weighing strategy that always identifies the counterfeit coin and whether it is heavier or lighter. Present the full decision tree: for each weighing, which coins go on each pan and how the next step depends on outcomes (left heavy, right heavy, or balance). Prove correctness and minimality of three weighings.
Quick Answer: This question evaluates understanding of combinatorial reasoning, information theory, and decision-tree construction for identifying a single counterfeit coin and whether it is heavier or lighter using constrained balance-scale observations.
hardData ScientistTechnical ScreenStatistics & Math
13
0
The 12-Coin Counterfeit Puzzle (Three Weighings)
You are given 12 visually identical coins. Exactly one of them is counterfeit. The counterfeit coin differs in weight from the genuine coins — it is either heavier or lighter, and you do not know which. All genuine coins weigh exactly the same.
Your only tool is a two-pan balance scale with no reference weights. Each use of the scale tells you only one of three things: the left pan is heavier, the right pan is heavier, or the two pans balance.
Design a procedure that uses at most three weighings and, for every possible situation, identifies (a) exactly which coin is counterfeit and (b) whether that coin is heavier or lighter than a genuine coin.
Your answer must include all three of the following:
The
complete decision tree
— for every weighing, state which coins go on the left pan and which go on the right, and for each of the three outcomes (left heavy / right heavy / balance), give the next weighing or the final identification.
A
correctness argument
showing the procedure resolves all
12×2=24
possible situations to distinct conclusions.
A
minimality argument
showing two weighings can never suffice, so three is the minimum.
Constraints & Assumptions
Exactly
one
coin is counterfeit (not zero, not two).
The counterfeit's weight difference is
detectable
by the scale but its direction (heavier/lighter) is unknown a priori.
The scale is
exact
(no measurement noise) and reports only L / R / balance — it does
not
report the magnitude of the difference.
All 12 coins are candidates; you have
no
coin known to be genuine at the start and
no
external weights.
"At most three weighings" — the procedure may branch, but no path may use more than three.
Clarifying Questions to Ask
Is it guaranteed that
exactly one
coin is counterfeit, or could all 12 be genuine? (This changes whether the "all balance" leaf must still name a coin.)
Must the procedure also report
whether
the coin is heavier or lighter, or only
which
coin? (Reporting the direction is strictly harder and affects the counting bound.)
May the weighing strategy be
adaptive
— i.e., may each weighing depend on the outcomes of previous ones — or must all three weighings be fixed in advance?
Are partial answers acceptable on rare branches, or must the procedure be
guaranteed
correct on every one of the 24 cases?
What a Strong Answer Covers
A concrete, fully specified decision tree
with all three weighings written out, every branch (L / R / balance) resolved, and a clear final identification of both the coin and its direction at every leaf.
Correct sign-tracking
: the candidate distinguishes a "could be heavy" suspect from a "could be light" suspect based on which pan it sat on, and uses this to prune hypotheses correctly across weighings.
Coverage of all 24 cases
with no collisions — ideally demonstrated by a counting/leaf argument, not just a few spot checks.
The information-theoretic lower bound
:
3
outcomes per weighing ⇒
3k
distinguishable results in
k
weighings;
32=9<24≤27=33
, so two weighings are insufficient and three are necessary.
Valid use of known-genuine filler coins
in later weighings, with a justification of why a coin is provably genuine in that branch before it is used as a reference.
Clear communication of the branching logic
— a real interviewer is watching whether the candidate can keep the case analysis organized and unambiguous under time pressure.
Follow-up Questions
Suppose you are told
in advance
whether the counterfeit is heavier or lighter. How many coins can you now handle in three weighings, and why does the number go up?
Generalize: with
w
weighings, what is the
maximum number of coins
for which you can always find the odd one
and
its direction? (Hint: relate it to
23w−3
and explain the "
−3
".)
If you are additionally given
one coin known to be genuine
at the start, does the maximum number of coins you can handle in three weighings change? Explain.
Could a
non-adaptive
strategy (all three weighings fixed before seeing any outcome) solve the 12-coin version? What goes wrong, and what is the largest non-adaptive instance?