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 weighings | Number of weighings for coins |
| Whether target coin is lighter or heavier than others | Identify coin | ||
| Target coin is different from others | Identify coin | ||
| Target coin is different from others, or all coins are the same | Identify if unique coin exists, and whether it is lighter or heavier |
For example, in detecting a dissimilar coin in three weighings, the maximum number of coins that can be analyzed is. Note that with weighings and coins, it is not always possible to determine the nature of the last coin, but only that the other coins are all the same, implying that the last coin is the dissimilar coin. In general, with weighings, one can always determine the identity and nature of a single dissimilar coin if there are or fewer coins. In the case of three weighings, it is possible to find and describe a single dissimilar coin among a collection of 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".
Nine-coin problem
A well-known example has up to nine items, say coins, that are identical in weight except one, which is lighter than the others—a counterfeit. The difference is perceptible only by weighing them on scale—but only the coins themselves can be weighed. How can one isolate the counterfeit coin with only two weighings?Solution
To find a solution, we first consider the maximum number of items from which one can find the lighter one in just one weighing. The maximum number possible is three. To find the lighter one, we can compare any two coins, leaving the third out. If the two coins weigh the same, then the lighter coin must be one of those not on the balance. Otherwise, it is the one indicated as lighter by the balance.Now, imagine the nine coins in three stacks of three coins each. In one move we can find which of the three stacks is lighter. It then takes only one more move to identify the light coin from within that lighter stack. So in two weighings, we can find a single light coin from a set of.
By extension, it would take only three weighings to find the odd light coin among 27 coins, and four weighings to find it from 81 coins.
Twelve-coin problem
A more complex version has twelve coins, eleven of twelve of which are identical. If one is different, we don't know whether it is heavier or lighter than the others. This time the balance may be used three times to determine if there is a unique coin—and if there is, to isolate it and determine its weight relative to the others. The problem has a simpler variant with three coins in two weighings, and a more complex variant with 39 coins in four weighings.Solution
This problem has more than one solution. One is easily scalable to a higher number of coins by using base-three numbering: labelling each coin with a different number of three digits in base three, and positioning at the n-th weighing all the coins that are labelled with the n-th digit identical to the label of the plate. Other step-by-step procedures are similar to the following. It is less straightforward for this problem, and the second and third weighings depend on what has happened previously, although that need not be the case.- Four coins are put on each side. There are two possibilities:
Variations
Given a population of 13 coins in which it is known that 1 of the 13 is different from the rest, it is simple to determine which coin it is with a balance and 3 tests as follows:With a reference coin
If there is one authentic coin for reference then the suspect coins can be thirteen. Number the coins from 1 to 13 and the authentic coin number 0 and perform these weighings in any order:- 0, 1, 4, 5, 6 against 7, 10, 11, 12, 13
- 0, 2, 4, 10, 11 against 5, 8, 9, 12, 13
- 0, 3, 8, 10, 12 against 6, 7, 9, 11, 13
If there is never balance then it must be one of the coins 10–13 that appear in all weighings. Picking out the one counterfeit coin corresponding to each of the 27 outcomes is always possible except when all weighings are balanced, in which case there is no counterfeit coin. If coins 0 and 13 are deleted from these weighings they give one generic solution to the 12-coin problem.
If two coins are counterfeit, this procedure, in general, does not pick either of these, but rather some authentic coin. For instance, if both coins 1 and 2 are counterfeit, either coin 4 or 5 is wrongly picked.
Without a reference coin
In a relaxed variation of this puzzle, one only needs to find the counterfeit coin without necessarily being able to tell its weight relative to the others. In this case, clearly any solution that previously weighed every coin at some point can be adapted to handle one extra coin. This coin is never put on the scales, but if all weighings are balanced it is picked as the counterfeit coin. It is not possible to do any better, since any coin that is put on the scales at some point and picked as the counterfeit coin can then always be assigned weight relative to the others.A method which weighs the same sets of coins regardless of outcomes lets one either
- conclude if they all weigh the same, or find the odd coin and tell if it is lighter or heavier, or
- find the odd coin, and, at 12/13 probability, tell if it is lighter or heavier.
/// \\\
\// /\\
/\/ \/\
//\ \\/
\/– /\–
–\/ –/\
/–\ \–/
\\– //–
–\\ –//
\–\ /–/
/–– \––
–/– –\–
––/ ––\
–––
As each weighing gives a meaningful result only when the number of coins on the left side is equal to the number on the right side, we disregard the first row, so that each column has the same number of "\" and "/" symbols. The rows are labelled, the order of the coins being irrelevant:
\// A light /\\ A heavy
/\/ B light \/\ B heavy
//\ C light \\/ C heavy
\/– D light /\– D heavy
–\/ E light –/\ E heavy
/–\ F light \–/ F heavy
\\– G light //– G heavy
–\\ H light –// H heavy
\–\ I light /–/ I heavy
/–– J light \–– J heavy
–/– K light –\– K heavy
––/ L light ––\ L heavy
––– M either lighter or heavier,
or all coins weigh the same
Using the pattern of outcomes above, the composition of coins for each weighing can be determined; for example the set "\/– D light" implies that coin D must be on the left side in the first weighing, on the right side in the second, and unused in the third:
1st weighing: left side: ADGI, right side: BCFJ
2nd weighing: left side: BEGH, right side: ACDK
3rd weighing: left side: CFHI, right side: ABEL
The outcomes are then read off the table. For example, if the right side is lighter in the first two weighings and both sides weigh the same in the third, the corresponding code "//– G heavy" implies that coin G is the odd one, and it is heavier than the others.
Generalization to multiple scales
In another generalization of this problem, we have two balance scales that can be used in parallel. For example, if you know exactly one coin is different but do not know if it is heavier or lighter than a normal coin, then in rounds, you can solve the problem with at most coins.Generalization to multiple unknown coins
The generalization of this problem is described in Chudnov.Let be the -dimensional Euclidean space and be the inner product of vectors
and from For vectors and subsets the operations and are defined, respectively, as ;,, By we shall denote the discrete -cube in ; i.e., the set of all sequences of length over the alphabet The set is the discrete ball of radius with centre at the point Relative weights of objects are given by a vector which defines the configurations of weights of the objects: the th object has standard weight if the weight of the th object is greater by a constant value if . The vector characterizes the types of objects: the standard type, the non-standard type, and it does not contain information about relative weights of non-standard objects.
A weighing is given by a vector the result of a weighing for a situation is The weighing given by a vector has the following interpretation: for a given check the th object participates in the weighing if ; it is put on the left balance pan if and is put on the right pan if For each weighing, both pans should contain the same number of objects: if on some pan the number of objects is smaller than as it should be, then it receives some reference objects. The result of a weighing describes the following cases: the balance if, the left pan outweighs the right one if, and the right pan outweighs the left one if The incompleteness of initial information about the distribution of weights of a group of objects is characterized by the set of admissible distributions of weights of objects which is also called the set of admissible situations, the elements of are called admissible situations.
Each weighing induces the partition of the set by the plane into three parts, and defines the corresponding partition of the set where
Definition 1. A weighing algorithm of length is a sequence where is the function determining the check at each th step, of the algorithm from the results of weighings at the previous steps.
Let be the set of all -syndromes and be the set of situations with the same syndrome ; i.e., ;
Definition 2. A WA is said to:
a) identify the situations in a set if the condition is satisfied for all
b) identify the types of objects in a set if the condition is satisfied for all
It is proved in that for so-called suitable sets an algorithm of identification the types identifies also the situations in
As an example the perfect dynamic algorithms with parameters are constructed in which correspond to the parameters of the perfect ternary Golay code. At the same time, it is established that a static WA with the same parameters does not exist.
Each of these algorithms using 5 weighings finds among 11 coins up to two counterfeit coins which could be heavier or lighter than real coins by the same value. In this case the uncertainty domain contains situations, i.e. the constructed WA lies on the Hamming bound for and in this sense is perfect.
To date it is not known whether there are other perfect WA that identify the situations in for some values of. Moreover, it is not known whether for some there exist solutions for the equation
which is, obviously, necessary for the existence of a perfect WA. It is only known that for there are no perfect WA, and for this equation has the unique nontrivial solution which determines the parameters of the constructed perfect WA.