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 112
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^(n1) 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^(n1)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
