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 |
a computerized start
