All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Yet one more coin sorting problem (Posted on 2004-05-31)
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?

 See The Solution Submitted by Federico Kereki Rating: 4.0000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: solution | Comment 8 of 20 |
(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:

`abcdeabcedabecdacbdeacbedacdbeacdebacebdacedbaebcdaecbdaecdbeabcdeacbdeacdbab             15ac             15ad             15ae             12bc             5bd             10be             6cd             15ce             8de             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

 Search: Search body:
Forums (0)