Qm
BrainteasersJane StreetOptiver

Ten coins, one heavy, fewest weighings

weighingbalance-scaleinformationternary

You have ten coins that look identical. Nine weigh exactly the same; one is slightly heavier. You have a two-pan balance scale that only tells you which pan is heavier, or that they balance.

What is the smallest number of weighings that guarantees you find the heavy coin, no matter how unlucky you are? Give the number and a procedure that achieves it, and explain why fewer can never be enough.

Show a hint

One weighing has only three possible outcomes: left pan down, right pan down, or balanced. How many different "stories" can two weighings tell apart?

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Adaptive Versus Pre-Committed Weighing StrategiesBalance-Scale Weighing ProblemsOptimal Card Guessing When You Count What Is GoneHat-Colour ProblemsFinding the Odd Ball Without Knowing If It Is Heavy or Light

Related questions

Find the heavy ball among 27 in three weighingsThe scale that only says equal or not equalHow many coins can five weighings handle?How many weighings to find one heavy coin in 80?Eight coins, and maybe none of them is fake
All questions →