Fog Creek Software
Discussion Board




SPOILER!!: three predefined weighings

The question was: how to find the one odd-weighted 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^(N-1) : (L > R) ? -(3^(N-1)) : 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 = -1-3+9
coin 6 = +0+3-9 (== -6)
coin 7 = +1-3+9
coin 8 = -1+0+9
coin 9 = +0+0+9
coin 10= -1+0-9 (== -10)
coin 11= +1-3-9 (== -11)
coin 12= +0-3-9 (== -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