Saturday, July 30, 2011

Solution to Weights Puzzle

Here is the question:
 http://good-interview-puzzles.blogspot.com/2011/07/weighing-in-harder-way.html

[1] A = B: C has a heavy or light coin [18 cases]
[2] A < B: A has a light coin or B has a heavy coin [18 cases]
[3] A > B: A has a heavy coin or B has a light coin [18 cases]

[1] Split C into groups of three coins: C1, C2, C3 and weigh C1 vs. C2.

C1 = C2: C3 has a heavy or light coin [6 cases]
Procedure 1:
 Name the C3 coins c3a, c3b, c3c.
c3a = c3b: if c3a </> c3c, then c3c is the heavy / light coin.
c3a < c3b: if c3a </= c3c, then c3a is light / c3b is heavy.
c3a > c3b: if c3a =/> c3c, then c3b is light / c3a is heavy.

C1 < C2: C1 has a light coin or C2 has a heavy coin [6 cases]
C1 = C3: [C2>C1=C3] C2 has a heavy coin.
Apply Procedure 1 to determine the odd one out.
C1 < C3: [C2>C1<C3] C1 has a light coin. Apply Procedure 1 to determine the light coin.
C1 > C3: [C3>C1>C2] Impossible.

C1 > C2: C1 has a heavy coin or C2 has a light coin [6 cases]
C1 = C3: [C1=C3>C2] C2 has a light coin. Apply Procedure 1 to determine the light coin.
C1 < C3: [C2<C1<C3] C1 Impossible.
C1 > C3: [C2<C1>C3] C1 has a heavy coin. Apply Procedure 1 to determine the heavy coin.

[2] Weigh A vs. C

A = C: [A=C<B] B has a heavy coin [9 cases]
Procedure 2:
Split the B coins into groups of three: B1, B2, B3
B1 = B2: B3 has a heavy coin. Apply procedure 1 to determine which.
B1 < B2: B2 has a heavy coin. Apply procedure 1 to determine which.
B1 > B2: B1 has a heavy coin. Apply procedure 1 to determine which.
A < C: [B>A<C] A has a light coin [9 cases] Apply Procedure 2 to determine which.
A > C: [B>A>C] Impossible

[3] Weigh A vs. C

A = C: [A=C>B] B has a heavy coin [9 cases] Apply Procedure 2 to determine which.
A < C: [B<A<C] Impossible
A > C: [B<A>C] A has a heavy coin [9 cases] Apply Procedure 2 to determine which.

No comments:

Post a Comment