Skip to content

Cheapest way to find an odd coin among ninety

Question

There are 9090 coins, all of equal weight except one counterfeit that may be either heavier or lighter, you do not know which. Each weighing on a two-pan balance costs $100. What plan identifies the fake and tells whether it is heavy or light at the lowest possible cost in the worst case, and what is that cost?

Short answer

$500 (five weighings). There are 180180 possibilities and 34=81<180≤243=353^4=81<180\le243=3^5, so four weighings cannot suffice. Weigh 3030 against 3030: if they balance, the fake is among the other 3030 and the 6060 good coins help four weighings settle it; if not, the 6060 coins each have a known suspected direction, and four weighings resolve these 60≤8160\le81 cases.

Adapted from Crack, Heard on the Street, Q1.18, p.13; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free