Answer to Puzzle #1: 12 Coins, Old Fashioned Balance
1. You are given a set of scales and 12 marbles. The scales are of the old balance variety. That is, a small dish hangs from each end of a rod that is balanced in the middle. The device enables you to conclude either that the contents of the dishes weigh the same or that the dish that falls lower has heavier contents than the other.
The 12 marbles appear to be identical. In fact, 11 of them are identical, and one is of a different weight. Your task is to identify the unusual marble and discard it. You are allowed to use the scales three times if you wish, but no more.
Note that the unusual marble may be heavier or lighter than the others. You are asked to both identify it and determine whether it is heavy or light.
Firstly let me stress that this puzzle is very difficult, and worse the answer is not particularly satisfying. It is not a good way to be introduced to my site. Questions 3 & 5 are quite easy. 9 is accessible and interesting and 13 is my favourite. You have been warned.
My answer is something of an amalgam between the Dr. Math web-site, myself, and various emails I received, including a correction from Ben Cronin. It is now rigorous but as easy to follow as is possible.
Before reading the answer can I interest you in a clue?
Most people seem to think that the thing to do is weigh six marbles against six marbles, but if you think about it, this would yield you no information concerning the whereabouts of the only different marble or the nature of it's difference as we already know that one side will be heavier than the other. It's worth mentioning that if this is used as an interview question this observation, by itself, is likely to get you a good portion of the way there.
So that the plan can be followed, let us number the marbles from 1 to 12. For the first weighing let us put on the left pan marbles 1,2,3,4 and on the right pan marbles 5,6,7,8.
There are two possibilities. Either they balance, or they don't. If they balance, then the different marble is in the group 9,10,11,12. So for our second one possibility is to weigh 9,10,11 against 1,2,3
(1) They balance, in which case you know 12 is the different marble, and you just weigh it against any other to determine whether it is heavy or light.
(2) 9,10,11 is heavy. In this case, you know that the different marble is 9, 10, or 11, and that that marble is heavy. Simply weigh 9 against 10; if they balance, 11 is the heavy marble. If not, the heavier one is the heavy marble.
(3) 9,10,11 is light. Proceed as in the step above, but the marble you're looking for is the light one.
That was the easy part.
What if the first weighing 1,2,3,4 vs 5,6,7,8 does not balance? Then any one of these marbles could be the different marble. Now, in order to proceed, we must keep track of which side is heavy for each of the following weighings.
Suppose that 5,6,7,8 is the heavy side. We now weigh 1,5,6 against 2,7,8. If they balance, then the different marble is either 3 or 4. Weigh 4 against 9, a known good marble. If they balance then the different marble is 3, otherwise it is 4. The direction of the tilts can tell us whether the offending marble is heavier or lighter.
Now, if 1,5,6 vs 2,7,8 does not balance, and 2,7,8 is the heavy side, then either 7 or 8 is a different, heavy marble, or 1 is a different, light marble.
For the third weighing, weigh 7 against 8. Whichever side is heavy is the different marble. If they balance, then 1 is the different marble. Should the weighing of 1,5, 6 vs 2,7,8 show 1,5,6 to be the heavy side, then either 5 or 6 is a different heavy marble or 2 is a light different marble. Weigh 5 against 6. The heavier one is the different marble. If they balance, then 2 is a different light marble.
Number Theory
Steve Mencinsky emailed me with a number theory approach, subsequently Nelson Gimenez da Motta has also been in contact, he took Steve's work and ran with it. It is not my intention that anyone using this site would have to have really any formal advanced maths training. I aspire to be able to explain everything through common sense and logic, even if what we are secretly doing is using a mathematical technique. This number theory approach does introduce an important technique to which I would like to return, the ability to quickly identify if we have enough information to solve a problem.
The first approach, my approach, uses three dependent weighings, that is what we weigh on the second weighing is dependent on the results of the first and so on. He demonstrates that with each individual weighing having 3 possible outcomes, (left, right & balanced,) and there being 3 weighings there are 33=27 possible results in total. Reflections are not useful to us so there is enough information from 3 independent weighings to determine the results for 13.5 marbles. This is an important first step.
The implications of a half marble I'll leave to Steve and Nelson to describe. Below are the emails they sent me.
Hello Nigel. Using number theory to solve this problem gives us one more marble and an unexpected hilarious twist. Your (correct) solution comprises what I would call three "dependent" weighings. That is, the strategy for the second and third weighings depend on the result of the previous weighing(s).
Using number theory, it is possible to create three "independent" weighings.
We proceed as follows. Each weighing has three possible results: Left side down (which I will define as ZERO) , all marbles equal (I define this as ONE) , right side down (TWO). So this is base three (trinary) arithmetic. So with three trinary numbers we get 33 = 27 possible results: 000 through to 222. One of these is a very special case indeed which I discuss at the end.
We place our marbles so that each of the 27 different possible results uniquely identifies each marble. I have found it easiest to split this task into three cases.
Case (1): A marble participates in only one weighing. Place marble A on the right in weighing #1 only, B on the right in weighing #2 only, C on the right in weighing #3 only.
Case (2): A marble participates in two weighings. Place D on the left in weighing #1 and on the left in weighing #2, E on the left in weighing
#1 and on the right in weighing #2. Four more combinations are allowed, weighing six marbles.
Case (3): A marble participates in all three weighings. This gives us four more: left-left-left, left-right-left, left-left-right, left-right-right.
This actually allows us to weigh THIRTEEN marbles, and the 27 resulting trinary numbers uniquely identify each marble and its lighter/heavier status. Using the examples from cases (1) and (2) above:
0 1 1 = A is heavier
2 1 1 = A is lighter
1 0 1 = B is heavier
1 2 1 = B is lighter
1 1 0 = C is heavier
1 1 2 = C is lighter
0 0 1 = D is heavier
2 2 1 = D is lighter
0 2 1 = E is heavier
2 0 1 = E is lighter
But only half of all 27 combinations are allowed! Mirror images are verboten - a kind of Pauli Exclusion Principle for marbles, if you will. This is possibly best illustrated by an example. Suppose for marble X, we have it left-left-left. This then prevents us from putting marble Y as right-right-right, because those would give the same pattern of 0/1/2 results, with of course opposite lighter/heavier status. A simpler example is that left-none-none then forbids right-none-none.
Another way of saying the same thing, is that the placement pattern of any ONE marble will map to TWO of our 27 trinary numbers, depending on whether the marble is lighter or heavier. Thus with 27 possibilities we get 13 AND A HALF weighings.
Here is the amusing part. What, exactly, is half a weighing? Very simple. Half a weighing is a weighing that only gives us half of the information. So, if you do not weigh the 14th marble, and you find that the 13 that you did weigh are all the same (trinary number 1 1 1), then you know that the 14th one, the one that you did not weigh, is the odd one out, but you don't know whether it is lighter or heavier.
Having said all this, there is one "implementation complication". You have to be very careful which one of the two mappings you select, otherwise you end up with too many marbles on either one side or the other. If you wish, I could probably sit down and work out the exact scale loadings and send you those via separate email. I haven't actually done this since about 1982 so it might take me a while.
Steve from Mudgee.
So that's Steve's email, now Nelson's...
Hello, Nigel,
My name is Nelson and I'm from Brazil, so please forgive my English ??
During last week I've been intrigued by the Number Theory explanation of the first puzzle on your website (http://puzzles.nigelcoldwell.co.uk/one.htm). I struggled to understand it, but now I think I've sorted it out. However, I believe some statements made by Steve might be incorrect.
I'll try to explain my logic below.
1) We name each possible result for a given weighing:
Possible results
-1
Left side down
0
Equilibrium
1
Right side down
2) We list every possible trio of results (3 weighings). Then we map each of those triples to a marble. As Steve explained, mirrors must be mapped to the same marble due to heavy/light duality:
Triples
Marble mapped
-1
0
0
or
1
0
0
A
0
-1
0
or
0
1
0
B
0
0
-1
or
0
0
1
C
-1
-1
0
or
1
1
0
D
0
-1
-1
or
0
1
1
E
-1
0
-1
or
1
0
1
F
-1
1
0
or
1
-1
0
G
0
-1
1
or
0
1
-1
H
-1
0
1
or
1
0
-1
I
-1
-1
1
or
1
1
-1
J
-1
1
1
or
1
-1
-1
K
-1
1
-1
or
1
-1
1
L
-1
-1
-1
or
1
1
1
none
0
0
0
none
3) Now we need to arrange the marbles into 3 weighings so that each marble matches one of the triples we assigned to it. I used color codes to make it easier to check which triples were used:
Triples
Marble mapped
-1
0
0
or
1
0
0
A
0
-1
0
or
0
1
0
B
0
0
-1
or
0
0
1
C
-1
-1
0
or
1
1
0
D
0
-1
-1
or
0
1
1
E
-1
0
-1
or
1
0
1
F
-1
1
0
or
1
-1
0
G
0
-1
1
or
0
1
-1
H
-1
0
1
or
1
0
-1
I
-1
-1
1
or
1
1
-1
J
-1
1
1
or
1
-1
-1
K
-1
1
-1
or
1
-1
1
L
-1
-1
-1
or
1
1
1
none
0
0
0
none
Left Side
Right Side
1st Weighing
AGJL
DFIK
2nd Weighing
BHJK
DEGL
3rd Weighing
CIKL
EFHJ
Conclusion: using the results for these three weighings, we are able to find the different marble and determine whether it is lighter or heavier than the others.
Example:
1st weighing = left side down (-1)
2nd weighing = equilibrium (0)
3rd weighing = left side down (-1)
This maps to triple (-1;0;-1), which corresponds to marble "F". This marble is lighter than the others, because the side it was put into 1st and 3rd weighings went up.
Using this logic, we are able to solve the complete problem - which marble is different AND whether it is lighter or heavier - for 12 marbles. But Steve stated that it is possible to solve the complete problem for 13 balls. I would like to challenge that.
At first glance, we can conclude that it's possible to map the unused triple in table above (1;1;1) to a 13th marble. However, it is physically impossible to put an additional marble into all three weighings without messing up the balance. So a 13th marble can only be mapped to triple (0;0;0). Therefore, if this triple is the result of the 3 weighings, we are able to conclude that this 13th marble is different than the others, but because we didn't put it in any weighing, it is impossible to conclude whether it is lighter or heavier than the others.
I'm not able to demonstrate it now, but the formula that seems to describe the number of marbles we are able to identify (complete problem) with "x" weighings is: (3x - 3)/2. For 3 weighings we have (33 - 3)/2 = 12. For 4 weighings we would have (34 - 3)/2 = 39. I think the "-3" part of the equation relates to the unused triples and the "/2" relates to the heavy/light duality.
What do you think of this conclusion? Does it make sense?
Cheers,
--
Nelson Gimenez da Motta
Neither of them got this completely right. Bard came the closest.
If you're curious what Bard made of this puzzle...
Sure, here is a solution to the 12-marble weighing problem.
Step 1: Divide the 12 marbles into 3 groups of 4 each.
Step 2: Weigh Group 1 against Group 2.
Step 3: If the scales balance, then the unusual marble is in Group 3.
Step 4: If the scales do not balance, then the unusual marble is in the heavier or lighter group.
Step 5: If the scales balance, then the unusual marble is in the heavier or lighter group.
Step 6: Weigh the two marbles in the heavier or lighter group against each other.
Step 7: If the scales balance, then the unusual marble is the heavier or lighter marble.
Step 8: If the scales do not balance, then the unusual marble is the heavier or lighter marble.
Here is an example of how the algorithm would work if the unusual marble is heavier than the others:
Divide the 12 marbles into 3 groups of 4 each.
Weigh Group 1 against Group 2.
The scales do not balance. Group 1 is heavier.
Weigh the two marbles in Group 1 against each other.
The scales do not balance. The first marble is heavier.
Therefore, the unusual marble is the first marble, and it is heavier than the others.
The algorithm can be used to identify the unusual marble in any number of marbles, as long as you are allowed to weigh the marbles three times.
If you're curious what ChatGPT made of this puzzle...
The below is left without comment or judgement
To solve this problem, we can use a process of elimination to identify the unusual marble and determine whether it is heavy or light. Here's how we can do it in three weighings:
Weigh four marbles against four marbles. There are three possible outcomes:
If the two sets of marbles balance, then the unusual marble must be in the remaining four marbles. Go to step 2.
If one set of marbles is heavier than the other, then the unusual marble is in the heavier set. Go to step 2.
If one set of marbles is lighter than the other, then the unusual marble is in the lighter set. Go to step 2.
Weigh two of the remaining four marbles against two other marbles. There are three possible outcomes:
If the two sets of marbles balance, then the unusual marble must be one of the two marbles that weren't weighed. Weigh these two marbles against each other in step 3 to determine which one is unusual and whether it is heavy or light.
If one set of marbles is heavier than the other, then the unusual marble must be one of the two marbles in the heavier set. Weigh these two marbles against each other in step 3 to determine which one is unusual and whether it is heavy or light.
If one set of marbles is lighter than the other, then the unusual marble must be one of the two marbles in the lighter set. Weigh these two marbles against each other in step 3 to determine which one is unusual and whether it is heavy or light.
Weigh the two remaining marbles against each other. There are two possible outcomes:
If the two marbles balance, then there is no unusual marble.
If one marble is heavier than the other, then that marble is the unusual one, and its weight will tell you whether it is heavy or light.
In summary, we can identify the unusual marble and determine whether it is heavy or light in three weighings as follows:
Weigh four marbles against four marbles.
Weigh two of the remaining four marbles against two other marbles.
Weigh the two remaining marbles against each other.
PayPal
I always think it's arrogant to add a donate button, but it has been requested. If I help you get a job though, you could buy me a pint! - nigel
This Website Uses Cookies
To increase the functionality of the site. The cookies I apply do not uniquely identify you, by continuing to use this site you agree to let me place a cookie. I also have advert and analytics providers, my advertising provider (Google,) does provide personalised adverts unless you specify otherwise, with them. For more information click here.x