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?

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