even harder coin problem
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)
Thursday, June 06, 2002
No. If the left hand side stays down every time, you don't know whether it's 1 or 11
Sunday, June 09, 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"
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?
Tuesday, June 11, 2002
Yep, this work work. Checking it took me some time. :-)
Wednesday, June 19, 2002
Fog Creek Home