1 against 2 1 against 3Both of these can have three outcomes: fall to the left (l), fall to the right (r), or balance (b). The following table gives the answer for each of these outcomes:
outcome fake coin: ----------------------- l l 1 too heavy l b 2 too light l r (not possible) b l 3 too light b b no fake coin b r 3 too heavy r l (not possible) r b 2 too heavy r r 1 too light
1 2 3 against 4 5 6 1 2 3 against 7 8 9We know which group of three coins ({1,2,3}, {4,5,6} and {7,8,9}) contains the fake coin (if there is one) and whether it is heavier or lighter. By means of a simple weighing, we can determine which one is the fake coin, by putting one coin of each group on the left, and one the right:
1 4 7 against 2 5 8But 9 is three smaller then 12 (= (3^3 - 3)/2). We note however that the outcomes `l r' and `r l' are not possible in the above table. The idea is to use this, by adding another 3 coins to our weighings:
1 2 3 10 against 4 5 6 11 1 2 3 11 against 7 8 9 10 1 4 7 10 against 2 5 8 12We give the table, with only those outcomes for these weightings, that start with `l r', `r l' and `b b' (as all other cases already have been dealt with):
outcome fake coin: ----------------------- l r l 10 too heavy l r b 11 too light l r r (not possible) b b l 12 too light b b b no fake coin b b r 12 too heavy r l l (not possible) r l b 11 too heavy r l r 10 too light
1 4 6 10 against 5 7 9 12 2 5 4 11 against 6 8 7 10 3 6 5 12 against 4 9 8 11for which outcomes `l l l' and `r r r' are not possible. This is a rather symmetric solution.
Open question: how many weighing schema are there? (should be a multiple of 12!, I suspect) Answer.
........... 37 against ........... 38 ........... 38 against ........... 37 ........... 38 against ........... 37 1 4 7 .. 34 38 against 2 5 8 .. 35 39The dots of the first 3 three weighings are filled in using the weighings for n = 3 (where coin c is replaced by 3c-2, 3c-1 and 3c). Notice that we have placed 37 and 38 according to the patrons `l r r' and `r l l' respectively. If we write out the complete table, there will be again two impossible answers.
This proves there can be a weighing strategy for any n > 1, by step-wise induction.
Left Pan Right Pan Weighing I 4 8 10 11 1 2 5 7 Weighing II 2 4 7 12 3 5 6 11 Weighing III 5 6 10 12 7 8 9 11Start with a Sum = 0 in the mind. Perform the 3 weighings, observing the tilt, if any.
Weighing I: Add -1 if tilt is left pan down, +1 if tilt is left pan up. Weighing II: Add -3 if tilt is left pan down, +3 if tilt is left pan up. Weighing III: Add -9 if tilt is left pan down, +9 if tilt is left pan up.The number of the odd ball is the absolute value of Sum, and it is light or heavy depending on its appearance on the light or heavy side.
weigh MADO versus LIKE weigh METO versus FIND weigh FAKE versus COIN
The argument for 1 solution is that any valid solution has the following properties:
Excluding mirror symmetries where the pans of each weighings are exchanged (a factor of 8) there are 5 distinct ways to choose coins from each of the triples, singletons and pairs. If each of these 5 ways of choosing is labeled, then there are 125 ways to choose 3 weighings, but of these only 22 are both distinct and valid and 17 of these are permutations of the other 5. If we allow all 22 variations and all 8 mirror symmetries there are 22 * 8 = 176 solutions for each partitioning of 12 coins into an ordered sets of triples, ordered set of singletons and ordered set of 3 ordered pairs.
There, are of course, 12! ways to partition 12 coins in that way. So, 12! * 22 * 8 = 84304281600 solutions, excluding the 4!^6 trivial variants of each solution generated simply by permuting the coins in each pan.
He wrote a tool in go that allows you to assign a unique number to each solution or given a solution derive a unique number for that solution. So, for example:
$ echo "0 1 4 10 16" | tr ' ' \\012 | ./tools/tools --decode {"weighings":[[[1,4,10,11],[12,5,6,7]],[[2,6,11,12],[10,7,8,9]],[[3,8,12,10],[11,9,4,5]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["p","p","p"],"S":0,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":0} {"weighings":[[[10,11,12,4],[5,6,7,1]],[[2,6,11,12],[10,7,8,9]],[[3,8,12,10],[11,9,4,5]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["q","p","p"],"S":1,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":1} {"weighings":[[[1,4,10,11],[12,5,6,7]],[[11,12,6,8],[10,7,9,2]],[[12,10,4,5],[11,8,9,3]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["p","r","s"],"S":4,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":4} {"weighings":[[[1,4,10,11],[12,5,6,7]],[[11,12,6,8],[10,7,9,2]],[[12,10,11,3],[8,9,4,5]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["p","r","t"],"S":10,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":10} {"weighings":[[[10,11,12,4],[5,6,7,1]],[[11,12,6,8],[10,7,9,2]],[[12,10,4,5],[11,8,9,3]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["q","r","s"],"S":16,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":16}Yields 5 structurally distinct solutions where (1,2,3) are the singletons, ((4,5),(6,7),(8,9)) are the pairs and (10,11,12) are the triples.
While:
cat examples/iwriteiam.json | ./tools/tools --encodeshows that the numbers assigned to 2 of the solutions on this page are:
41981248865 45956768 { "weighings":[ [[1,2,3,10], [4,5,6,11]], [[1,2,3,11], [7,8,9,10]], [[1,4,7,10], [2,5,8,12]] ] } { "weighings":[ [[1,4,6,10],[5,7,9,12]], [[2,5,4,11],[6,8,7,10]], [[3,6,5,12],[4,9,8,11]] ] }For a more detailed description of the analyses, with some Venn-diagrams, see his code project on GitHub.
Bennet Haselton has an interesting page about the following variation: You have a balance scale and 13 coins, 1 of which are counterfeit. The counterfeit weigh less or more than the other coins. Can you determine the counterfeit in 3 weightings, if you do not have determine whether it is heavier or lighter?