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

Home > Logic > Weights and Scales
Four Weights (Posted on 2004-07-25) Difficulty: 3 of 5
You have 4 weights weighing 2,3,5 and 7 pounds. The problem is none of them are marked. What is the fewest number of weighings you need using a balance scale figure out which weights are which?

See The Solution Submitted by Brian Smith    
Rating: 3.5000 (8 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips a computerized start | Comment 3 of 33 |

The chart below shows the results of all possible weighings for all possible orders of weights a, b, c and d being the given weights:

            a 2 2 2 2 2 2 3 3 3 3 3 3 5 5 5 5 5 5 7 7 7 7 7 7
            b 3 3 5 5 7 7 2 2 5 5 7 7 2 2 3 3 7 7 2 2 3 3 5 5
            c 5 7 3 7 3 5 5 7 2 7 2 5 3 7 2 7 2 3 3 5 2 5 2 3
            d 7 5 7 3 5 3 7 5 7 2 5 2 7 3 7 2 3 2 5 3 5 2 3 2
abc v d       / / / / / / / / / / / / / / / / / / / / / / / / 24  0  0
ab  v d       \ - - / / / \ - / / / / - / / / / / / / / / / / 18  4  2
abd v c       / / / / / / / / / / / / / / / / / / / / / / / / 24  0  0
ab  v c       - \ / - / / - \ / / / / / - / / / / / / / / / / 18  4  2
ab  v cd      \ \ \ \ / / \ \ \ \ / / \ \ \ \ / / / / / / / / 12  0 12
ac  v d       - / \ / - / / / \ / - / / / - / / / / / / / / / 18  4  2
a   v d       \ \ \ \ \ \ \ \ \ / \ / \ / \ / / / / / / / / / 12  0 12
ad  v c       / - / \ / - / / / \ / - / / / - / / / / / / / / 18  4  2
a   v c       \ \ \ \ \ \ \ \ / \ / \ / \ / \ / / / / / / / / 12  0 12
a   v cd      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ - - \ \ - - / /  2  4 18
acd v b       / / / / / / / / / / / / / / / / / / / / / / / / 24  0  0
ac  v b       / / - / \ - / / - / \ / / / / / - / / / / / / / 18  4  2
ac  v bd      \ / \ / \ \ \ / \ / \ \ \ / \ / \ \ / / / / / / 12  0 12
ad  v b       / / / - - \ / / / - / \ / / / / / - / / / / / / 18  4  2
a   v b       \ \ \ \ \ \ / / \ \ \ \ / / / / \ \ / / / / / / 12  0 12
a   v bd      \ \ \ \ \ \ \ \ \ \ \ \ \ - \ - \ \ - / \ / \ -  2  4 18
ad  v bc      / \ / \ \ \ / \ / \ \ \ / \ / \ \ \ / / / / / / 12  0 12
a   v bc      \ \ \ \ \ \ \ \ \ \ \ \ - \ - \ \ \ / - / \ - \  2  4 18
a   v bcd     \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  0  0 24
bc  v d       / / / / / / - / - / / / \ / \ / / / - / - / / / 18  4  2
b   v d       \ \ \ / / / \ \ \ / / / \ \ \ / / / \ \ \ / / / 12  0 12
bd  v c       / / / / / / / - / - / / / \ / \ / / / - / - / / 18  4  2
b   v c       \ \ / \ / / \ \ / \ / / \ \ / \ / / \ \ / \ / / 12  0 12
b   v cd      \ \ \ \ \ \ \ \ \ \ - - \ \ \ \ / / \ \ \ \ - -  2  4 18
c   v d       \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / 12  0 12

A / indicates the left side is heavy; a - indicates the sides are equal and a \ indicates the right side is heavy.

At the right are given the number of possibilities in that row in which the left side is heavy, the two sides are equal, and the right side is heavy.

The trick now is to find the least combination of rows that will produce unique vertical identities (sequences of / - and \) for each of the 24 possible permutations of the weights.

 

The program to produce the above is:

DECLARE SUB permute (a$)
CLS
a$ = "abcd": ha$ = a$
w$ = "2357": hw$ = w$
FOR p = 1 TO 4
  w$ = hw$
  PRINT TAB(13); MID$(ha$, p, 1); " ";
  DO
    PRINT MID$(w$, p, 1); " ";
    permute w$
  LOOP UNTIL w$ = hw$
  PRINT
NEXT p

FOR a = -1 TO 1
 FOR b = -1 TO 1
  FOR c = -1 TO 1
   FOR d = -1 TO 1
     l = d
     IF c THEN l = c
     IF b THEN l = b
     IF a THEN l = a
     t1 = a + b + c + d
     t2 = ABS(a) + ABS(b) + ABS(c) + ABS(d)
     IF ABS(t1) <> t2 THEN
      IF l < 1 THEN
        IF a = -1 THEN PRINT "a";
        IF b = -1 THEN PRINT "b";
        IF c = -1 THEN PRINT "c";
        IF d = -1 THEN PRINT "d";
        PRINT TAB(4); " v ";
        IF a = 1 THEN PRINT "a";
        IF b = 1 THEN PRINT "b";
        IF c = 1 THEN PRINT "c";
        IF d = 1 THEN PRINT "d";
        PRINT TAB(15);
        w$ = hw$
        lCt = 0: rCt = 0: eCt = 0
        DO
         leftSide = 0: rightSide = 0
         IF a < 0 THEN leftSide = leftSide + VAL(MID$(w$, 1, 1))
         IF a > 0 THEN rightSide = rightSide + VAL(MID$(w$, 1, 1))
         IF b < 0 THEN leftSide = leftSide + VAL(MID$(w$, 2, 1))
         IF b > 0 THEN rightSide = rightSide + VAL(MID$(w$, 2, 1))
         IF c < 0 THEN leftSide = leftSide + VAL(MID$(w$, 3, 1))
         IF c > 0 THEN rightSide = rightSide + VAL(MID$(w$, 3, 1))
         IF d < 0 THEN leftSide = leftSide + VAL(MID$(w$, 4, 1))
         IF d > 0 THEN rightSide = rightSide + VAL(MID$(w$, 4, 1))
         IF leftSide < rightSide THEN PRINT "\ "; : rCt = rCt + 1
         IF leftSide = rightSide THEN PRINT "- "; : eCt = eCt + 1
         IF leftSide > rightSide THEN PRINT "/ "; : lCt = lCt + 1
         permute w$
        LOOP UNTIL w$ = hw$
        PRINT USING "## ## ##"; lCt; eCt; rCt
       END IF
     END IF
   NEXT
  NEXT
 NEXT
NEXT

SUB permute (a$)
DEFINT A-Z
 x$ = ""
 FOR i = LEN(a$) TO 1 STEP -1
  l$ = x$
  x$ = MID$(a$, i, 1)
  IF x$ < l$ THEN EXIT FOR
 NEXT

 IF i = 0 THEN
  FOR j = 1 TO LEN(a$) \ 2
   x$ = MID$(a$, j, 1)
   MID$(a$, j, 1) = MID$(a$, LEN(a$) - j + 1, 1)
   MID$(a$, LEN(a$) - j + 1, 1) = x$
  NEXT
 ELSE
  FOR j = LEN(a$) TO i + 1 STEP -1
   IF MID$(a$, j, 1) > x$ THEN EXIT FOR
  NEXT
  MID$(a$, i, 1) = MID$(a$, j, 1)
  MID$(a$, j, 1) = x$
  FOR j = 1 TO (LEN(a$) - i) \ 2
   x$ = MID$(a$, i + j, 1)
   MID$(a$, i + j, 1) = MID$(a$, LEN(a$) - j + 1, 1)
   MID$(a$, LEN(a$) - j + 1, 1) = x$
  NEXT
 END IF
END SUB

 


  Posted by Charlie on 2004-07-25 11:58:17
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