Fog Creek Software
Discussion Board




even harder coin problem


I'm suggesting a solution which has a defect: I can't calculate in one case if the coin is lighter or heavier... It is similar to the one I suggested for the 12 pills problem:
First, I'm writing a more detailed explaining of how it was perceived:

We divide the pills (coins, balls whatever) 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 12AB versus bcdD

1.1.    12AB > bcdD (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.    12AB < bcdD (means that one of the reversed is the one, which is either A or B)

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.3.    12AB = bcdD (means that it’s one of the missing, which is either 3 or 4 and heavier or C and lighter)

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)
1.3.3.    3 = 4 (means that it’s C)

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).

We put 12AB versus bcdD

2.1.    12AB < bcdD (means that one of the common with the first weighing is the wanted one, or it’s the 1 or 2 and lighter or the D and heavier)

We put 1 versus 2

2.1.1.    1 > 2 (means that it’s 2 and lighter)
2.1.2.    2 > 1 (means that it’s 1 and lighter)
2.1.3.    1 = 2 (means that it’s D and heavier)

2.2.    12AB > bcdD (means that one of the reversed is the one, which is either A or B and heavier)

We put A versus B

2.2.1.    A > B (means that it’s A)
2.2.2.    A < B (means that it’s B)

2.3.    12AB = bcdD (means that it’s one of the missing, which is either 3 or 4 and lighter or C and heavier)

We put 3 versus 4

1.3.4.    3 > 4 (means that it’s 4)
1.3.5.    3 < 4 (means that it’s 3)
1.3.6.    3 = 4 (means that it’s C)


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

We put 12AB versus bcdD

3.1.    12AB > bcdD (means it’s either b or c or d and lighter)

We put b versus d

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


3.2.    12AB < bcdD (means it’s either b or c or d and heavier)

We put b versus d

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


3.3.    12AB = bcdD (means it’s a lighter or heavier)

3.3.1.    No solution for the weight of a…

We then can make the following steps:
a) 1234 versus ABCD
b) 12AB versus bcdD
c) 1A3b versus 2B4c,

where the third step is the combination of all the above mentioned third steps. So, if we called ">" the case the left to be heavier than the right, "<" the opposite case and "=" the equality, we would have the following:

1) >>> gives 1 heavier
2) >>< gives 2 heavier
3) >>= gives D lighter
4) ><> gives B lighter
5) ><< gives A lighter
6) >=> gives 3 heavier
7) >=< gives 4 heavier
8) >== gives C lighter
9) <>> gives A heavier
10) <>< gives B heavier
11) <<> gives 2 lighter
12) <<< gives 1 lighter
13) <<= gives D heavier
14) < => gives 4 lighter
15) <=< gives 3 lighter
16) <== gives C heavier
17) =>> gives d lighter
18) =>< gives b lighter
19) =>= gives c lighter
21) =<> gives b heavier
22) =<< gives d heavier
23) =<= gives c heavier
23) == gives a but not if heavier or lighter

I guess there is a combination that gives the right solution but I cannot figure it now.
I give up.

Panagiotis
Monday, April 18, 2005


The probable combinations are 3^3=27. we apparently want 24 (12 coins * 2 (heavier or lighter)). Three combinations are inacceptable ><=, <>= and another one because they give contradictory results. ==> and ==< give such results.

Panagiotis
Monday, April 18, 2005

If on turn 1: ABCD = 1234
then on turn 2: weigh ABC ? abc

if ABC > abc, then a or b or c is heavy so weigh b ? c to find out which

if ABC < abc, then a or b or c is light so weigh b ? c to find out which

If ABC = abc, then d is heavy or light so weigh A ? d to find out if it is heavy or light

WanFactory
Tuesday, April 19, 2005

Oh wait, never mind my solution is not deterministic, ignore above post

WanFactory
Tuesday, April 19, 2005

I think I've got it:

(label the balls, 0123456789AB)

round 1: 1234 vs 5678
round 2: 1678 vs 59AB
round 3: 1269 vs 037A

the balance on any round will be (L)eft heavy, (R)ighty heavy, or (B)alanced.

This gives 27 possible triplets of results, 3 of which should be impossible, the remaining 24 of which will pick out a ball and identify it as heavy or light.

Havent done all the details but it looks ok so far

WanFactory
Thursday, April 21, 2005

I must confirm that your solution is correct, giving the following results:
I must tell you that I envy you that you found it...
Bouhou

LLL    1heavy
LLR    impossible
LLB    5light
LRL    7light
LRR    6light
LRB    8light
LBL    2heavy
LBR    3heavy
LBB    4heavy
RLL    6heavy
RLR    7heavy
RLB    8heavy
RRL    impossible
RRR    1light
RRB    5heavy
RBL    3light
RBR    2light
RBB    4light
BLL    Alight
BLR    9light
BLB    Blight
BRL    9heavy
BRR    Aheavy
BRB    Bheavy
BBL    0light
BBR    0heavy
BBB    impossible

Panagiotis
Monday, April 25, 2005

heres another solution, i think, using 1-12

1 2 3 4 v 5 6 7 8
1 4 5 9 v 2 6 11 12
3 7 9 12 v 1 2 6 10

with the solutions:

flat    flat    left        10 is light
flat    flat    right        10 is heavy
flat    left    flat        11 is light
flat    left    left        9 is heavy
flat    left    right        12 is light
flat    right    flat        11 is heavy
flat    right    left        12 is heavy
flat    right    right        9 is light
left    flat    flat        8 is light
left    flat    left        3 is heavy
left    flat    right        7 is light
left    left    flat        4 is heavy
left    left    left        6 is light
left    left    right        1 is heavy
left    right    flat        5 is light
left    right    right        2 is heavy
right    flat    flat        8 is heavy
right    flat    left        7 is heavy
right    flat    right        3 is light
right    left    flat        5 is heavy
right    left    left        2 is light
right    right    flat        4 is light
right    right    left        1 is light
right    right    right        6 is heavy


i hope...

flange
Thursday, May 26, 2005

I heard this problem a long time ago, but it was with 13 balls.  1 was corrupt (i.e. heavier or lighter).  It can be done in 3 weighings, but you cannot determine in all cases whether the ball is heavier or lighter.

Adam Freund
Sunday, June 12, 2005

general solution to the classic weighing problem


in general if you know either the coin is heavier or lighter you can find the coin out in n weighings among  3^n coins (at the maximum). (note: if the number of coins falls between 3^(n-1) and 3^n you would still require n weighings)

however if you just know its a counterfeit one i.e you do not know if its heavier or lighter you can find out the countefeit coin in n weighings among (3^n - 3)/2 coins. (note: if the number of coins falls between (3^(n-1)-3)/2 and (3^n - 3)/2 you would still require n weighings)


can anyone prove either of the above mathematically ..if so please mail me the solution.

Abyss
Wednesday, June 15, 2005

*  Recent Topics

*  Fog Creek Home