Greg Charles wrote:Drat. Murprhey's law strikes again.
Misspelling "Muphry" to add yet another layer of irony was well-played, sir.
Warning: The following post gets into just one little detail of this already-solved puzzle. If you're already bored with the
thread up to this point, this post will only make matters worse.
You've been warned.
Ryan McGuire wrote:If the number of coins, c = (n^3 - 3)/2 for some positive integer value of n, then the solution can be found here.
...
To find the fake coin out of 3 coins in 2 weightings...
1 <--> 2
1 <--> 3
...
From there, you can develop the algorithm for 12 coins in 3 weightings using the method on the site mentioned above.
Actually, with a minor change to the starting c=3, n=2 strategy, the set way of getting from a given n to n+1 becomes a little more symmetric and easy to remember.
For 3 coins and 2 weightings
1 -- 2
2 -- 3
L L - impossible
L B - 1 heavy
L R - 2 light
B L - 3 light
B B - all coins equal
B R - 3 heavy
R L - 2 heavy
R B - 1 light
R R - impossible
For the sake of discussion, let's call the strategy for a give n Sn.
This way, the two "impossible" outcomes are the ones that are all R or all L.
Then use this to shift up to the next value of n:
1. For each coin, x, in Sn-1, replace it with 3x-2, 3x-1 and 3x. e.g. Replace coin 1 from Sn-1 with coins 1, 2, and 3 in Sn.
For S3 ...
1 2 3 -- 4 5 6
4 5 6 -- 7 8 9
So far we can say...
L L - impossible
L B - 1,2 or 3 heavy
L R - 4,5 or 6 light
B L - 7,8 or 9 light
B B - all coins equal
B R - 7,8 or 9 heavy
R L - 4,5 or 6 heavy
R B - 1,2 or 3 light
R R - impossible
2. Add a third weighting that separates the coins in each group of three. e.g. separate 1, 2 and 3.
Just put the first coin from each group on the left and the second on the right.
1 4 7 -- 2 5 8
L L L - impossible
L L B - impossible
L L R - impossible
L B L - 1 heavy
L B B - 3 heavy
L B R - 2 heavy
L R L - 5 light
L R B - 6 light
L R R - 4 light
B L L - 8 light
B L B - 9 light
B L R - 7 light
B B L - impossible
B B B - all coins equal
B B R - impossible
B R L - 7 heavy
B R B - 9 heavy
B R R - 8 heavy
R L L - 4 heavy
R L B - 6 heavy
R L R - 5 heavy
R B L - 2 light
R B B - 3 light
R B R - 1 light
R R L - impossible
R R B - impossible
R R R - impossible
(Remember that c = (3^n - 3)/2)
3. With just c-3 (i.e. 9) coins, there are eight "impossible" outcomes. Use those slots for the three additional coins. Put coin c-2 (10) on the left and coin c-1 (11) on the right for the first n-1 (2) weightings. For the last weighting, put coin c-1 on the left and coin c (12) on the right. That new set of weightings will fill in six of the eight "impossible" slots in the lookup table:
1 2 3 10 -- 4 5 6 11
4 5 6 10 -- 7 8 9 11
1 4 7 11 -- 2 5 8 12
L L L - impossible
L L B - 10 heavy <--
L L R - 11 light <--
L B L - 1 heavy
L B B - 3 heavy
L B R - 2 heavy
L R L - 5 light
L R B - 6 light
L R R - 4 light
B L L - 8 light
B L B - 9 light
B L R - 7 light
B B L - 12 light <--
B B B - all coins equal
B B R - 12 heavy <--
B R L - 7 heavy
B R B - 9 heavy
B R R - 8 heavy
R L L - 4 heavy
R L B - 6 heavy
R L R - 5 heavy
R B L - 2 light
R B B - 3 light
R B R - 1 light
R R L - 11 heavy <--
R R B - 10 light <--
R R R - impossible
The added bonus here is that the LLL and RRR rows still represent the "impossible" outcomes. This is in contrast to the iwriteiam.com page I linked to earlier, where the impossible rows were the RL and LR ones for c=3 and RLL and LRR for c=12.
I can easily grind through the steps to create the list of weightings for S4 (c=39):
1, 2, 3, 4, 5, 6, 7, 8, 9,28,29,30,37 -- 10,11,12,13,14,15,16,17,18,31,32,33,38
10,11,12,13,14,15,16,17,18,28,29,30,37 -- 19,20,21,22,23,24,25,26,27,31,32,33,38
1, 2, 3,10,11,12,19,20,21,31,32,33,37 -- 4, 5, 6,13,14,15,22,23,24,34,35,36,38
1, 4, 7,10,13,16,19,22,25,28,31,34,38 -- 2, 5, 8,11,14,17,20,23,26,29,32,35,39
I'll leave it as an exercise for the interested reader to generate the outcome table. (...because contrary to what Tom Petty would have us believe, the weighting is
not the hardest part.)