Fog Creek Software
Discussion Board




classic weighing

Another solution:
We divide the pills into three sets of four:
1234, ABCD and  abcd .
We put on the balance 1234 versus ABCD

1.    1234 > ABCD (means that either one of the 1234 is the wanted one and is heavier or it’s one of the ABCD and it’s lighter)

We put 12ABC versus abcdD

1.1.    12ABC > abcdD (means that one of the common with the first weighing is the wanted one, or it’s the 1 or 2 and heavier or the D and lighter)

We put 1 versus 2

1.1.1.    1 > 2 (means that it’s 1 and heavier)
1.1.2.    2 > 1 (means that it’s 2 and heavier)
1.1.3.    1 = 2 (means that it’s D and lighter)

1.2.    12ABC < abcdD (means that one of the reversed is the one, which is either A or B or C and lighter)

We put A versus B

1.2.1.    A > B (means that it’s B)
1.2.2.    A < B (means that it’s A)
1.2.3.    A = B (means that it’s C)

1.3.    12ABC = abcdD (means that it’s one of the missing, which is either 3 or 4 and heavier)

We put 3 versus 4

1.3.1.    3 > 4 (means that it’s 3)
1.3.2.    3 < 4 (means that it’s 4)

2.    1234 < ABCD (means that either one of the 1234 is the wanted one and is lighter or it’s one of the ABCD and it’s heavier). The rest is as explained in the previous paragraph (1.), but in the opposite way, don’t expect from me to write It down again.

3.    1234 = ABCD (means that it’s one of the abcd and is heavier or lighter).

We put 123 versus abc

3.1.    123 > abc (means it’s either a, b or c and lighter)

We put a versus b

3.1.1.    a > b (means it’s b)
3.1.2.    a < b (means it’s a)
3.1.3.    a = b (means it’s c)

3.2.    123 < abc (means it’s either a, b or c and heavier)

We put a versus b

3.2.1.    a > b (means it’s a)
3.2.2.    a < b (means it’s b)
3.2.3.    a = b (means it’s c)

3.3.    123 = abc (means it’s either d lighter or heavier)

We put d versus a

3.3.1.    a > d (means it’s d and lighter)
3.3.2.    a < d (means it’s d and heavier)
3.3.3.    a = d (means we’ve been cheated!!!)


As we can see, we can have one common second step instead of alternatives 1.1, 1.2 and 1.3: We put 1A3 versus 2B4.

Another thing: Why not make a solution with AND OR NOT XOR etc?
It might give the solution for the "even harder coin problem". Am I crazy? I'm not a computer engineer (or a programmer), so I leave it to the specialists

Panagiotis Apostolopoulos
Monday, April 18, 2005

CLASSIC WEIGHING PROBLEM


Can you prove mathematically that if there are (3^n -3)/2 coins or balls then n weighings are required to identify it or the vice versa

note counterfeit means it may be heavier or lighter, you never know.

for example to identify a  counterfeit one among  3 coins  you require 2 weighings, a counterfeit one among 12 coins needs 3 weighigs and ofcourse if it between 3 coins and 12 coins i.e 3<x<12 you still would need 3 weighings.

a rigorous proof is highly appreciated.

Abyss
Wednesday, June 15, 2005

CLASSIC WEIGHING PROBLEM -

correction of the abocve statement

Can you prove mathematically that if there are (3^n -3)/2 coins or balls and one of it is counterfeit  then n weighings are required to identify the counterfeit one 

note counterfeit means it may be heavier or lighter, you never know.

for example to identify a  counterfeit one among  3 coins  you require 2 weighings, a counterfeit one among 12 coins needs 3 weighigs and ofcourse if it between 3 coins and 12 coins i.e 3<x<12 you still would need 3 weighings.

a rigorous proof is highly appreciated.

Abyss
Wednesday, June 15, 2005

*  Recent Topics

*  Fog Creek Home