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

Home > Logic > Weights and Scales
Yet one more coin sorting problem (Posted on 2004-05-31) Difficulty: 3 of 5
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:

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information