You have five coins, apparently alike, but actually of different weights. You also have a two arm scale.
Can you manage to sort the coins in ascending order, using the scale only seven times?
Bonus question: can it be done in fewer weighings?
(In reply to
solution by Charlie)
At each step in the process (each weighing), a computer program assisted in listing the remaining permutations, and in determining what split each of the possible weighings would produce. The program, shown with a portion of the comparisons commented out (with an apostrophe marking the beginning of comment, to the end of line), is shown commented back to a stage showing the 15 possibilities after the first three weighings, and showing one side of the split for any proposed weighings:
DECLARE SUB permute (a$)
CLS
a$ = "abcde": h$ = a$
DO
IF INSTR(a$, "a") < INSTR(a$, "b") AND INSTR(a$, "c") < INSTR(a$, "d") AND INSTR(a$, "a") < INSTR(a$, "c") THEN ' AND INSTR(a$, "c") < INSTR(a$, "e") AND INSTR(a$, "d") < INSTR(a$, "e") THEN
PRINT a$
FOR i = 1 TO 4
FOR j = i + 1 TO 5
IF j <> i THEN
ix1 = INSTR(a$, MID$(h$, i, 1))
ix2 = INSTR(a$, MID$(h$, j, 1))
IF ix1 < ix2 THEN compCt(i, j) = compCt(i, j) + 1
END IF
NEXT
NEXT
END IF
permute a$
LOOP UNTIL a$ = h$
FOR i = 1 TO 4
FOR j = i + 1 TO 5
PRINT MID$(h$, i, 1); MID$(h$, j, 1), compCt(i, j)
NEXT
NEXT
(the permute subroutine not shown; it appears elsewhere and just cycles through the permutations of a string)
The result of this stage was:
abcde
abced
abecd
acbde
acbed
acdbe
acdeb
acebd
acedb
aebcd
aecbd
aecdb
eabcd
eacbd
eacdb
ab 15
ac 15
ad 15
ae 12
bc 5
bd 10
be 6
cd 15
ce 8
de 4
so that the 15 permutations remaining after the first three weighings could be shown, and showing that only C vs E had a side of the split that was either 7 or 8, as needed at that stage.
|
|
Posted by Charlie
on 2004-05-31 11:28:03 |
re: solution
