You have eight bags, each of them containing 48 coins.

Five of these bags contain only true coins, the rest of them contain fake coins. Fake coins weigh 1 gram less than the real coins.

You do not know what bags have fake coins and what bags have real coins. You do not know also, besides that it is an integer value, the weight of the real coins.

You can use a digital or analog reading scale with precision up to 1 gram.

Making only one weighing and using the minimum number of coins, how can you find the bags containing the fake coins?

(In reply to not quite -- my best by Charlie)

Place the following numbers of coins on the scale (from bags 1 through 8):

0  1  2  4  7  13  24  44

This is 95 coins. So take the remainder of the scale reading mod 95. Then use the table below to determine which set of three bags contained fakes:

1  2  3       92                       2  4  7          66
1  2  4       90                       2  4  8          46
1  2  5       87                       2  5  6          74
1  2  6       81                       2  5  7          63
1  2  7       70                       2  5  8          43
1  2  8       50                       2  6  7          57
1  3  4       89                       2  6  8          37
1  3  5       86                       2  7  8          26
1  3  6       80                       3  4  5          82
1  3  7       69                       3  4  6          76
1  3  8       49                       3  4  7          65
1  4  5       84                       3  4  8          45
1  4  6       78                       3  5  6          73
1  4  7       67                       3  5  7          62
1  4  8       47                       3  5  8          42
1  5  6       75                       3  6  7          56
1  5  7       64                       3  6  8          36
1  5  8       44                       3  7  8          25
1  6  7       58                       4  5  6          71
1  6  8       38                       4  5  7          60
1  7  8       27                       4  5  8          40
2  3  4       88                       4  6  7          54
2  3  5       85                       4  6  8          34
2  3  6       79                       4  7  8          23
2  3  7       68                       5  6  7          51
2  3  8       48                       5  6  8          31
2  4  5       83                       5  7  8          20
2  4  6       77                       6  7  8          14

The program for the above table:

CLS

DATA 1,1,2,3,6,11,20
READ i1
READ i2
READ i3
READ i4
READ i5
READ i6
READ i7

  w(1) = 0
  w(2) = w(1) + i1
  w(3) = w(2) + i2
  w(4) = w(3) + i3
  w(5) = w(4) + i4
  w(6) = w(5) + i5
  w(7) = w(6) + i6
  w(8) = w(7) + i7

  IF w(8) < 99 THEN
    tot = 0
    FOR i = 1 TO 8: tot = tot + w(i): NEXT
    LOCATE 1, 1
    PRINT tot: PRINT
    REDIM taken(10 * tot)
    cl = 1: rw = 3
    bad = 0
    FOR good = 1 TO 1
      FOR ch1 = 1 TO 6
      FOR ch2 = ch1 + 1 TO 7
      FOR ch3 = ch2 + 1 TO 8
        rw = rw + 1: IF rw > 31 THEN rw = 4: cl = 40
        LOCATE rw, cl
        PRINT ch1; ch2; ch3,
        t = good * tot - (w(ch1) + w(ch2) + w(ch3))
        PRINT t;
        IF taken(t) THEN
          PRINT "*****"
          bad = 1:
        ELSE
          PRINT
        END IF
        taken(t) = 1
      NEXT
      NEXT
      NEXT
      PRINT : PRINT
    NEXT
    IF bad = 0 THEN
     LOCATE 34, 1
     FOR i = 1 TO 8
      PRINT w(i);
     NEXT
     PRINT
     'END
    END IF
  END IF

The program that found the appropriate set was:

CLS
FOR i1 = 1 TO 8
FOR i2 = i1 TO 9
'PRINT i1; i2
FOR i3 = i2 TO 12
FOR i4 = i3 TO 15
FOR i5 = i4 TO 16
FOR i6 = i5 TO 19
FOR i7 = i6 TO 21
 
  w(1) = 0
  w(2) = w(1) + i1
  w(3) = w(2) + i2
  w(4) = w(3) + i3
  w(5) = w(4) + i4
  w(6) = w(5) + i5
  w(7) = w(6) + i6
  w(8) = w(7) + i7

  IF w(8) < 49 THEN
    tot = 0
    FOR i = 1 TO 8: tot = tot + w(i): NEXT

    'PRINT tot: PRINT
    REDIM taken(10 * tot)
    cl = 1
    bad = 0
    FOR good = 1 TO 3
      FOR ch1 = 1 TO 6
      FOR ch2 = ch1 + 1 TO 7
      FOR ch3 = ch2 + 1 TO 8
        rw = rw + 1: IF rw > 28 THEN rw = 1: cl = 40
        'LOCATE rw, cl
        'PRINT ch1; ch2; ch3,
        t = good * tot - (w(ch1) + w(ch2) + w(ch3))
        'PRINT t;
        IF taken(t) THEN
          'PRINT "*****"
          bad = 1:
        ELSE
          'PRINT
        END IF
        taken(t) = 1
      NEXT
      NEXT
      NEXT
      ' PRINT : PRINT
    NEXT
    IF bad = 0 THEN
     FOR i = 1 TO 8
      PRINT w(i);
     NEXT
     PRINT
     'END
    END IF
  END IF

NEXT
NEXT
NEXT
NEXT
NEXT
NEXT
NEXT

Posted by Charlie on 2008-10-23 15:57:17