Answer to Puzzle #1: 12 Coins, Old Fashioned Balance
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.
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 TheorySteve Mencinsky emails me with a number theory approach. 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 to describe. Below is the email he 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.
© Nigel Coldwell 2004 - – The questions on this site may be reproduced without further permission, I do not claim copyright over them. The answers are mine and may not be reproduced without my expressed prior consent. Please enquire using the link at the top of the page.
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