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

 Four Weights (Posted on 2004-07-25)
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.)
 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 2abc v d       / / / / / / / / / / / / / / / / / / / / / / / / 24  0  0ab  v d       \ - - / / / \ - / / / / - / / / / / / / / / / / 18  4  2abd v c       / / / / / / / / / / / / / / / / / / / / / / / / 24  0  0ab  v c       - \ / - / / - \ / / / / / - / / / / / / / / / / 18  4  2ab  v cd      \ \ \ \ / / \ \ \ \ / / \ \ \ \ / / / / / / / / 12  0 12ac  v d       - / \ / - / / / \ / - / / / - / / / / / / / / / 18  4  2a   v d       \ \ \ \ \ \ \ \ \ / \ / \ / \ / / / / / / / / / 12  0 12ad  v c       / - / \ / - / / / \ / - / / / - / / / / / / / / 18  4  2a   v c       \ \ \ \ \ \ \ \ / \ / \ / \ / \ / / / / / / / / 12  0 12a   v cd      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ - - \ \ - - / /  2  4 18acd v b       / / / / / / / / / / / / / / / / / / / / / / / / 24  0  0ac  v b       / / - / \ - / / - / \ / / / / / - / / / / / / / 18  4  2ac  v bd      \ / \ / \ \ \ / \ / \ \ \ / \ / \ \ / / / / / / 12  0 12ad  v b       / / / - - \ / / / - / \ / / / / / - / / / / / / 18  4  2a   v b       \ \ \ \ \ \ / / \ \ \ \ / / / / \ \ / / / / / / 12  0 12a   v bd      \ \ \ \ \ \ \ \ \ \ \ \ \ - \ - \ \ - / \ / \ -  2  4 18ad  v bc      / \ / \ \ \ / \ / \ \ \ / \ / \ \ \ / / / / / / 12  0 12a   v bc      \ \ \ \ \ \ \ \ \ \ \ \ - \ - \ \ \ / - / \ - \  2  4 18a   v bcd     \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  0  0 24bc  v d       / / / / / / - / - / / / \ / \ / / / - / - / / / 18  4  2b   v d       \ \ \ / / / \ \ \ / / / \ \ \ / / / \ \ \ / / / 12  0 12bd  v c       / / / / / / / - / - / / / \ / \ / / / - / - / / 18  4  2b   v c       \ \ / \ / / \ \ / \ / / \ \ / \ / / \ \ / \ / / 12  0 12b   v cd      \ \ \ \ \ \ \ \ \ \ - - \ \ \ \ / / \ \ \ \ - -  2  4 18c   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

 Search: Search body:
Forums (0)