Balance puzzle

For the World Puzzle Championship puzzle with numbers, see Balance (puzzle).

An animation of a solution to the a false coin problem involving ten coins. In this example, the false coin is lighter than the others.

A balance puzzle or weighing puzzle is one of a number of logic puzzles based on the balancing of similar-looking items—often coins—to determine which holds a different value within a limited number of uses of the balance scales. These differ from puzzles that assign weights to items, in that only the relative mass of these items is relevant. n weighings are sufficient to find a bad coin among 3ⁿ − 1/2 coins. ^[1]

The nine-coin problem

Solution to the balance puzzle for 9 coins in 2 weighings, where the odd coin is lighter than the others – if the odd coin were heavier than the others, the upper two branches in each weighing decision are swapped

A well-known example has nine (or fewer) items, say coins (or balls), that are identical in weight save for one, which in this example is lighter than the others—a counterfeit (an oddball). The difference is only perceptible by weighing them on scale—but only the coins themselves can be weighed. Is it possible to 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 tested 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 (i.e. the one containing the lighter coin). 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 $\scriptstyle 3\,\times \,3\;=\;9$ .

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.

The twelve-coin problem

A more complex version has twelve coins, at least eleven 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. (This puzzle and its solution first appeared in an article in 1945.^[2]) 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: labeling each coin with a different number of three digits in base three, and positioning at the n-th weightings all the coins that are labeled with the n-th digit identical to the label of the plate (with three plates, one on each side of the scale and one off the scale). Other step-by-step procedures are similar to the following. It is less straightforward for this problem, and the second and third weightings depend on what has happened previously, although that need not be the case (see below).

Four coins are put on each side. There are two possibilities:

1. One side is heavier than the other. If this is the case, remove three coins from the heavier side, move three coins from the lighter side to the heavier side, and place three coins that were not weighed the first time on the lighter side. (Remember which coins are which.) There are three possibilities:

1.a) The same side that was heavier the first time is still heavier. This means that either the coin that stayed there is heavier or that the coin that stayed on the lighter side is lighter. Balancing one of these against one of the other ten coins reveals which of these is true, thus solving the puzzle.

1.b) The side that was heavier the first time is lighter the second time. This means that one of the three coins that went from the lighter side to the heavier side is the light coin. For the third attempt, weigh two of these coins against each other: if one is lighter, it is the unique coin; if they balance, the third coin is the light one.

1.c) Both sides are even. This means that one of the three coins that was removed from the heavier side is the heavy coin. For the third attempt, weigh two of these coins against each other: if one is heavier, it is the unique coin; if they balance, the third coin is the heavy one.

2. Both sides are even. If this is the case, all eight coins are identical and can be set aside. Take the four remaining coins and place three on one side of the balance. Place 3 of the 8 identical coins on the other side. There are three possibilities:

2.a) The three remaining coins are lighter. In this case you now know that one of those three coins is the odd one out and that it is lighter. Take two of those three coins and weigh them against each other. If the balance tips then the lighter coin is the odd one out. If the two coins balance then the third coin not on the balance is the odd one out and it is lighter.

2.b) The three remaining coins are heavier. In this case you now know that one of those three coins is the odd one out and that it is heavier. Take two of those three coins and weigh them against each other. If the balance tips then the heavier coin is the odd one out. If the two coins balance then the third coin not on the balance is the odd one out and it is heavier.

2.c) The three remaining coins balance. In this case you just need to weigh the remaining coin against any of the other 11 coins and this tells you whether it is heavier or lighter.

Variations

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 the scales are only off balance once, then it must be one of the coins 1, 2, 3—which only appear in one weighing. 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 (13 coins one either too heavy or too light is 26 possibilities) except when all weighings are balanced, in which case there is no counterfeit coin (or its weight is correct). 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

(among 12 coins A-L) conclude if they all weigh the same, or find the odd coin and tell if it is lighter or heavier, or
(among 13 coins A-M) find the odd coin, and, for 12 of them, tell if it is lighter or heavier.

The three possible outcomes of each weighing can be denoted by "\" for the left side being lighter, "/" for the right side being lighter, and "-" for both sides having the same weight. The symbols for the weighings are listed in sequence. For example, "//-" means that the right side is lighter in the first and second weighings, and both sides weigh the same in the third weighing. Three weighings give the following 3³ = 27 outcomes. Except for "---", the sets are divided such that each set on the right has a "/" where the set on the left has a "\", and vice versa:

/// \\\

\// /\\
/\/ \/\
//\ \\/

\/- /\-
-\/ -/\
/-\ \-/

\\- //-
-\\ -//
\-\ /-/

/-- \--
-/- -\-
--/ --\

---

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 there is the same number of "\" and "/" symbols in each column (four of each). The rows are then labelled as follows:

\// 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 (13-coin case),
    or all coins weigh the same (12-coin case)

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 (to cause that side to be lighter), 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, "//- G heavy" (right side lighter in the first two weighings, and both sides weigh the same in the third) implies that coin G is the odd one, and it is heavier than the others.^[3]

Generalizations

The generalization of this problem is described in ^[4]

Let $\mathbb {R} ^{n}$ be the $n$ -dimensional Euclidean space, $[{\mathrm {e}}^{1},{\mathrm {e}}^{2}]$ be the inner product of vectors ${\mathrm {e}}^{1}$ and ${\mathrm {e}}^{2}$ from ${\mathbb {R}}^{n},$ For vectors ${\mathrm {e}}=(e_{1},\dots ,e_{n})\in {\mathbb {R}}^{n}$ and subsets $E=\{{\mathrm {e}}^{j}\}\subseteq {\mathbb {R}}^{n},$ the operations $(\cdot )^{{*}}$ and $(\cdot )^{{+}}$ are defined, respectively, as ${\mathrm {e}}^{{*}}=(sign(e_{i}))_{i}$ ; $E^{{*}}=\{({\mathrm {e}}^{j})^{{*}}\}$ , ${\mathrm {e}}^{{+}}=(|sign(e_{i})|)_{i}$ , $E^{{+}}=\{({\mathrm {e}}^{j})^{{+}}\}.$ By $I^{n}$ we shall denote the discrete [−1; 1]-cube in $\mathbb {R} ^{n}$ ; i.e., the set of all sequences of length $n$ over the alphabet $I=\{-1,0,1\}$ The set $I_{t}^{n}=\{{\mathrm {x}}\in I^{n}|w({\mathrm {x}})\leq t\}\subseteq I^{n}$ is the discrete ball of radius $t$ (in the Hamming metric $w()$ ) with centre at the point ${\mathrm {0}}.$ Relative weights of $n$ objects are given by a vector ${\mathrm {x}}=(x_{1},\dots ,x_{n})\in I^{n},$ which defines the configurations of weights of the objects: the $i$ th object has standard weight if $x_{i}=0;$ the weight of the $i$ th object is greater (smaller) by a constant (unknown) value if $x_{i}=1$ (respectively, $x_{i}=-1$ ). The vector ${\mathrm {x}}^{{+}}$ characterizes the types of objects: the standard type, the non-standard type (i.e., configurations of types), and it does not contain information about relative weights of non-standard objects.

A weighing (a check) is given by a vector ${\mathrm {h}}\in I^{n};$ the result of a weighing for a situation ${\mathrm {x}}\in I^{n}$ is $s({\mathrm {x}};{\mathrm {h}})=sign([{\mathrm {x}};{\mathrm {h}}]).$ The weighing given by a vector ${\mathrm {h}}=(h_{1},\dots ,h_{n})$ has the following interpretation: for a given check the $i$ th object participates in the weighing if $h_{i}\neq 0$ ; it is put on the left balance pan if $h_{i}<0$ and is put on the right pan if $h_{i}>0.$ For each weighing ${\mathrm {h}}$ , 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 $r(\mathrm {h} )=[\mathrm {h} ;1,\dots ,1]$ reference objects. The result of a weighing $s({\mathrm {x}};{\mathrm {h}})$ describes the following cases: the balance if $s({\mathrm {x}};{\mathrm {h}})=0$ , the left pan outweights the right one if $s({\mathrm {x}};{\mathrm {h}})=-1$ , and the right pan outweights the left one if $s({\mathrm {x}};{\mathrm {h}})=1.$ 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 $Z\subseteq I^{n},$ which is also called the set of admissible situations, the elements of $z\in Z$ are called admissible situations.

Each weighing h induces the partition of the set $I^{n}$ by the plane (hyperplane ) $[{\mathrm {x}};{\mathrm {h}}]=0$ into three parts $W(s|I;{\mathrm {h}})=\{{\mathrm {x}}\in I|s({\mathrm {x}};{\mathrm {h}})=s\}$ , $s\in I,$ and defines the corresponding partition of the set $Z=W(0|Z,{\mathrm {h}})+W(1|Z,{\mathrm {h}})+W(-1|Z,{\mathrm {h}}),$ where $W(s|Z,{\mathrm {h}})=W(s|I,{\mathrm {h}})\cap Z.$

Definition 1. A weighing algorithm (WA) ${\mathcal {A}}$ of length $m$ is a sequence ${\mathcal {A}}=<{\mathrm {A}}_{1},\dots ,{\mathrm {A}}_{m}>,$ where ${\mathrm {A}}_{j}:I^{{j-1}}\to I^{n}$ is the function determining the check ${\mathrm {h}}^{j}={\mathrm {A}}_{j}(s^{{j-1}});{\mathrm {h}}^{j}\in I^{n},$ at each $j$ th step, $j=1,2,\dots ,m,$ of the algorithm from the results of ${\mathrm {s}}^{{j-1}}=(s_{1},\dots ,s_{{j-1}})\in I^{{j-1}}$ weighings at the previous steps ( ${\mathrm {h}}^{1}={\mathrm {A}}_{1}()$ is a given initial check).

Let $S(Z,{\mathcal {A}})$ be the set of all $(Z,{\mathcal {A}})$ -syndromes and $W(s|{\mathcal {A}})\subseteq I$ be the set of situations with the same syndrome $s$ ; i.e., $W(s|{\mathcal {A}})=\{{\mathrm {z}}\in I^{m}|s(z|{\mathcal {A}})=s\}$ ; $W(s|Z;{\mathcal {A}})=W(s|{\mathcal {A}})\cap Z.$

Definition 2. A WA ${\mathcal {A}}$ is said to: a) identify the situations in a set $Z$ if the condition $|W(s|Z,{\mathcal {A}})|=1$ is satisfied for all $s\in S(Z{\mathcal {A}});$ b) identify the types of objects in a set $Z$ if the condition $|W^{{+}}(s|Z{\mathcal {A}})|=1$ is satisfied for all $s\in S(Z{\mathcal {A}}).$

It is prooved in ^[4] that for so-called suitable sets $Z$ an algorithm of identification the types identifies also the situations in $Z.$

The perfect algorithms with parameters $n$ = 11, $m$ = 5, $t$ = 2 are constructed in,^[4] which correspond to the parameters of the perfect ternary Golay code (Virtakallio-Golay code). A static algorithm (weighing code) with such parameters does not exist.

The Original Parallel Weighings Puzzle

Konstantin Knop invented this puzzle. We have N indistinguishable coins, one of which is fake (it is not known whether it is heavier or lighter than the genuine coins, which all weigh the same). There are two balance scales that can be used in parallel. Each weighing lasts one minute. What is the largest number of coins N for which it is possible to find the fake coin in five minutes?^[5]

References

↑ http://mathworld.wolfram.com/Weighing.html
↑ Grossman, Howard (1945). Scripta Mathematica XI.
↑ http://mathforum.org/library/drmath/view/55618.html
1 2 3 Chudnov, Alexander M. (2015). "Weighing algorithms of classification and identification of situations". Discrete Mathematics and Applications. 25 (2): 69–81. doi:10.1515/dma-2015-0007.
↑ http://arxiv.org/pdf/1310.7268.pdf Solution to the Counterfeit Coin Problem and its Generalization

In literature

Niobe, the protagonist of Piers Anthony's novel With a Tangled Skein, must solve the twelve-coin variation of this puzzle to find her son in Hell: Satan has disguised the son to look identical to eleven other demons, and he is heavier or lighter depending on whether he is cursed to lie or able to speak truthfully. The solution in the book follows the given example 1.c.
Beremiz, the main character from Júlio César de Mello e Souza's book The Man Who Counted, encounters an Indian merchant that challenges him with the standard balance puzzle with 8 identical shaped pearls (one pearl slightly lighter than the rest). Beremiz solves it by explicitly framing all the variables of the problem, using only two weighings.

External links

This article is issued from Wikipedia - version of the 11/22/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.