In a pile, there are 11 coins: 10 coins of common weight and one coin of different weight (lighter or heavier). They all look similar.

Using only a balance beam for only three times, show how you can determine the 'odd' coin.

Open problem (i cannot solve this myself): how many more coins (with the same weight as the ten) can we add to that pile so that three weighing still suffices? My conjecture is zero, though my friend guessed that adding one is possible. The best bound we can agree upon is < 2.

Three piles A,B,C of 4 coins each. 1st weighing: A1,A2,A3,A4 (A) vs B1,B2,B3,B4 (B); 2nd weighing: A1,A2,A3,B4 (left) vs A4,C1,C2,C3 (right)
If A > B then:
If left > right, A1,A2, or A3 is heavier. 3rd weighing: A1 vs A2: if A1 > A2, A1 is heavier; if A1 = A2, A3 is heavier; if A1 < A2, A2 is heavier.
If left = right, B1,B2, or B3 is lighter. 3rd weighing: B1 vs B2: if B1 > B2, B2 is lighter; if B1 = B2, B3 is lighter; if B1 < B2, B1 is lighter.
If left < right, either A4 is heavier or B4 is lighter. 3rd weighing: A4 vs A1: if A4 > A1, A4 is heavier; if A4 = A1, B4 is lighter; A4 < A1 is impossible.
If A = B then:
If left > right, C1,C2, or C3 is lighter. 3rd weighing: C1 vs C2: if C1 > C2, C2 is lighter; if C1 = C2, C3 is lighter; if C1 < C2, C1 is lighter.
If left = right, C4 is either heavier or lighter. 3rd weighing: C4 vs C1 : if C4 > C1, C4 is heavier; C4 = C1 is impossible; if C4 < C1, C4 is lighter.
If left < right, C1,C2, or C3 is heavier. 3rd weighing C1 vs C2: if C1 > C2, C1 is heavier; if C1 = C2, C3 is heavier; if C1 < C2, C2 is heavier.
If A < B then:
If left > right, either A4 is lighter or B4 is heavier. 3rd weighing: A4 vs A1: A4 > A1 is impossible; if A4 = A1, B4 is heavier; if A4 < A1, A4 is lighter.
If left = right, B1,B2, or B3 is heavier. 3rd weighing: B1 vs B2: if B1 > B2, B1 is heavier; if B1 = B2, B3 is heavier; if B1 < B2, B2 is heavier.
If left < right, A1,A2, or A3 is lighter. 3rd weighing: A1 vs A2: if A1 > A2, A2 is lighter; if A1 = A2, A3 is lighter; if A1 < A2, A1 is lighter.

Posted by Sanjay on 2003-05-11 03:28:22