
SPOILER!!: three predefined weighings
The question was: how to find the one oddweighted coin out of 12 with three weighings of a balance scale. The location of the coins must be determined beforehand.
 SPOILER 
The three weighings are labeled N = 1, 2, 3.
For each weighing:
 if the left scale goes down then the value of that weighing is W(N)=(3^N),
 if it balances then the value is W(N)=0,
 otherwise the value is W(N)=(3^N).
Label the coins 1,2,3,..,12 and conduct the weighings as follows:
weighing 1:
left: 1, 4, 5, 11
right: 2, 7, 8, 10
weighing 2:
left: 2, 3, 4, 7
right: 5, 6, 11, 12
weighing 3:
left: 5, 6, 8, 9
right: 7, 10, 11, 12
Add up the values from the three weighings: SUM=W(1) + W(2) + W(3).
The number of the odd coin is: abs(SUM).
The weight difference is given by: sign(SUM) (positive=>heavier) unless the coin is one of {7, 10, 11, 12} in which case it's indicated by sign(SUM).
Here's a related question: obviously there are many other permutations of positions that also solve this problem, can you find a formula that, for all possible permutations, links the heavier coins that will yield negative SUMs (obviously the answer is {7, 10, 11, 12} for the above solution)?
Piers Haken
Thursday, February 07, 2002
Unrelated question  as there are so few Piers Hakens in the world  mind if I ask if you are the Piers Haken who went to Dulwich College up to 1990?
Matt Clark
Thursday, February 07, 2002
Your solution did not work for me.
When N goes from 1..3, the value of W(N) needs to be:
W(N) = (L < R) ? 3^(N1) : (L > R) ? (3^(N1)) : 0
Also, I was getting the same result for coin 5 and coin 7.
The pairings I came up with are:
weighing 1:
left: 1, 4, 7, 11
right: 2, 5, 8, 10
weighing 2:
left: 2, 3, 4, 6
right: 5, 7, 11, 12
weighing 3:
left: 5, 7, 8, 9
right: 6, 10, 11, 12
which changes the "reversed set" to {6, 10, 11, 12}
broken down it looks like:
coin 1 = +1+0+0
coin 2 = 1+3+0
coin 3 = +0+3+0
coin 4 = +1+3+0
coin 5 = 13+9
coin 6 = +0+39 (== 6)
coin 7 = +13+9
coin 8 = 1+0+9
coin 9 = +0+0+9
coin 10= 1+09 (== 10)
coin 11= +139 (== 11)
coin 12= +039 (== 12)
David Woodruff
Tuesday, February 19, 2002
A variant of this one was the first interview question I was ever asked.
There is a much simpler solution.
Divide the 12 coins into 3 groups of 4.
Weigh two of the groups.
It will be obvious what to do next.
Steven T Abell
Monday, March 18, 2002
Recent Topics
Fog Creek Home
