Balance puzzle

A balance puzzle or weighing puzzle is a logic puzzle about balancing items—often coins—to determine which one has different weight than the rest, by using balance scales a limited number of times.

The solution to the most common puzzle variants is summarized in the following table:

Known	Goal	Maximum coins for n weighings	Number of weighings for c coins
Whether target coin is lighter or heavier than others	Identify coin	${\displaystyle 3^{n}}$	${\displaystyle \lceil \log _{3}(c)\rceil }$
Target coin is different from others	Identify coin	${\displaystyle {\tfrac {1}{2}}(3^{n}-1)}$	${\displaystyle \lceil \log _{3}(2c+1)\rceil }$
Target coin is different from others, or all coins are the same	Identify if unique coin exists, and whether it is lighter or heavier	${\displaystyle {\tfrac {1}{2}}(3^{n}-3)}$	${\displaystyle \lceil \log _{3}(2c+3)\rceil }$

For example, in detecting a dissimilar coin in three weighings (⁠${\displaystyle n=3}$⁠), the maximum number of coins that can be analyzed is ⁠${\displaystyle {\tfrac {1}{2}}(3^{3}-1)=13}$⁠. Note that with ⁠${\displaystyle 3}$⁠ weighings and ⁠${\displaystyle 13}$⁠ coins, it is not always possible to determine the nature of the last coin (whether it is heavier or lighter than the rest), but only that the other coins are all the same, implying that the last coin is the dissimilar coin. In general, with ⁠${\displaystyle n}$⁠ weighings, one can always determine the identity and nature of a single dissimilar coin if there are ⁠${\displaystyle {\tfrac {1}{2}}(3^{n}-3)}$⁠ or fewer coins. In the case of three weighings, it is possible to find and describe a single dissimilar coin among a collection of ⁠${\displaystyle 12}$⁠ coins.

This twelve-coin version of the problem appeared in print as early as 1945 and Guy and Nowakowski explain it "was popular on both sides of the Atlantic during WW2; it was even suggested that it be dropped over Germany in an attempt to sabotage their war effort".