Fog Creek Software
Discussion Board

even harder coin problem

err try..

1-6 vs 7-12

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

1,4,7,10 vs 8,11,3,6    (2,5,9,12 left out)

this right?

Cheradenine Zakalwe
Thursday, June 6, 2002

No. If the left hand side stays down every time, you don't know whether it's 1 or 11

Paul Viney
Sunday, June 9, 2002

ok lets see..

there are 12 coins, each of which can be heavier or
lighter, giving a total of 24 possible results..

this means that at each weigh, there must be coins
off the balance, since in this way it is possible to
represent all the information "encoded" in
the results of the balance

ie, if L R and B are possible at each weigh, there are
3x3x3 = 27 possible results which can "encode"
24 combinations

this leaves us with 3 "extra" combinations. we also
note that each combination has an inverse, implying
the opposite result.. since BBB is its own inverse,
BBB is chosen as one of the extra combinations.

we can also choose LLL and RRR as meaningless,
being inverses (LLL and RRR are easier to verify)

ok, so there are 12 coins at each weigh, but we must
always leave coins out, the natural thing is to
divide all the coins in 3
with 4 coins on the left, 4 on the right, 4 off.
we construct a grid representing this and then
enumerate all the combinations, assigning to
each one a result

eg, LLB implies coin 1 is heavier, LLB => 1H
(RRB automatically inverse, 1L)

LLB => 1H
LLR => 2L
LBL => 3H...

this process (with one conflict) fills the grid giving

1,3,5,7  vs  2,4,6,8    off 9,10,11,12
1,6,8,11 vs  2,7,9,10  off 3,4,5,12
2,3,8,12 vs  5,6,9,11  off 1,4,7,10

hopefully this is closer to correct than my
first cheap attempt?

Cheradenine Zakalwe
Tuesday, June 11, 2002

Yep, this work work. Checking it took me some time. :-)


Paul Viney
Wednesday, June 19, 2002

*  Recent Topics

*  Fog Creek Home