A certain tribe had an interesting kind of annual festival, in which every male member of the tribe (regardless of age) had to contribute a levy of grain into the tribal store. Their unit of weight was roughly the same as our pound avoirdupois, and each tribesman had to contribute one pound of grain for every year of his age.

The contributions were weighed on the tribe's ceremonial scales, using a set of seven ceremonial stones. Each of these weighed an integral number of pounds, and it was an essential part of the ritual that not more than three of them should be used for each weighing, though they need not all be in the same pan.

If ever a tribesman lived to such an age that his contribution could no longer be weighed by using three or fewer stones, the levy of grain would terminate forever. And in the previous year, one old man had died only a few months short of attaining this critical age, greatly to the relief of the headman of the tribe.

It has been determined that the stones can measure the maximum age. What is this age and what were the weights of the seven ceremonial stones?

(In reply to A computer exploration -- solution??? by Charlie)

   1  1
   2  1  -3
   2  3   9 -14
   3  3
   4  1   3
   4  1   9 -14
   5  1   3  -9
   5  9 -14
   6  1  -9  14
   6  3  -9
   7  1  -3   9
   7 40  64 -97
   8  1  -9
   8  3  -9  14
   9  9
  10  1   3 -14
  10  1   9
  10 14  40 -64
  11  1  -3  -9
  11  3 -14
  12  1  -3  14
  12  3   9
  13  1   3   9
  13  1 -14
  14 14
  15  1  14
  15  9  40 -64
  16  1  -3 -14
  17  3  14
  17  9  14 -40
  18  1   3  14
  19 14  64 -97
  20  3  -9 -14
  21  3  40 -64
  22  1  -9 -14
  23  1  40 -64
  23  3  14 -40
  23  9  14
  24  1   9  14
  24  9  64 -97
  24 40 -64
  25  1  14 -40
  25  1 -40  64
  26  3   9  14
  26 14 -40
  27  1 -14  40
  27  3 -40  64
  28  3   9 -40
  29  3 -14  40
  30  1   9 -40
  30  3  64 -97
  31  9 -40
  32  1  -9  40
  32  1  64 -97
  33  9 -40  64
  33 64 -97
  34  1 -64  97
  34  3  -9  40
  35  9 -14  40
  36  1   3 -40
  36  3 -64  97
  37  3 -40
  38  1  -3  40
  38 14 -40  64
  39  1 -40
  40 40
  41  1  40
  41  9  14 -64
  42  1  -3 -40
  42  9 -64  97
  43  3  40
  43 14  40 -97
  44  1   3  40
  45  9 -14 -40
  46  3  -9 -40
  47  3  14 -64
  47 14 -64  97
  48  1  -9 -40
  48  9  40 -97
  49  1  14 -64
  49  9  40
  50  1   9  40
  50 14 -64
  51  1 -14  64
  51  3 -14 -40
  52  3   9  40
  52  3   9 -64
  53  1 -14 -40
  53  3 -14  64
  54  1   9 -64
  54  3  40 -97
  54 14  40
  55  1  14  40
  55  9 -64
  56  1  -9  64
  56  1  40 -97
  57  3  14  40
  57 40 -97
  58  1 -40  97
  58  3  -9  64
  59  9 -14  64
  60  1   3 -64
  60  3 -40  97
  61  3 -64
  62  1  -3  64
  63  1 -64
  63  9  14  40
  64 64
  65  1  64
  66  1  -3 -64
  66  9 -40  97
  67  3  64
  68  1   3  64
  69  9 -14 -64
  70  3  -9 -64
  71 14 -40  97
  72  1  -9 -64
  73  9  64
  73 40 -64  97
  74  1   9  64
  74  9  14 -97
  75  3 -14 -64
  76  3   9  64
  77  1 -14 -64
  78 14  64
  79  1  14  64
  80  3  14 -97
  81  3  14  64
  82  1  14 -97
  83 14 -97
  84  1 -14  97
  85  3   9 -97
  86  3 -14  97
  87  1   9 -97
  87  9  14  64
  88  9 -97
  89  1  -9  97
  90 14 -40 -64
  91  3  -9  97
  92  9 -14  97
  93  1   3 -97
  94  3 -97
  95  1  -3  97
  95  9 -40 -64
  96  1 -97
  97 97
  98  1  97
  99  1  -3 -97
 100  3  97
 101  1   3  97
 101  3 -40 -64
 102  9 -14 -97
 103  1 -40 -64
 103  3  -9 -97
 104 40  64
 105  1  -9 -97
 105  1  40  64
 106  9  97
 107  1   9  97
 107  3  40  64
 108  3 -14 -97
 109  3   9  97
 110  1 -14 -97
 111 14  97
 112  1  14  97
 113  9  40  64
 114  3  14  97

 118 14  40  64
 120  9  14  97
 121 40 -64 -97
 123 14 -40 -97
 128  9 -40 -97
 134  3 -40 -97
 136  1 -40 -97
 137 40  97
 138  1  40  97
 140  3  40  97
 146  9  40  97
 147 14 -64 -97
 151 14  40  97
 152  9 -64 -97
 158  3 -64 -97
 160  1 -64 -97
 161 64  97
 162  1  64  97
 164  3  64  97
 170  9  64  97
 175 14  64  97
 201 40  64  97

shows 115 is the first not to have at least one way of being weighed. The negative signs are merely to show those weights are on the opposite pan from the positive numbers.  Whichever set is lower in absolute value has to be the side that also takes the grain.

A variation of the portion of the program which tests the limit for a given set produces a file of all 189 possible weighings, which can be sorted by weight to show all weights are possible to measure up through 114 (Quick Basic rather than Visual Basic, as PRINT USING was more important than speed):

DECLARE SUB try (lbs!)
DIM SHARED h(7), which, bestH(7), highTot, had(200)

OPEN "c-stones.txt" FOR OUTPUT AS #2

h(1) = 1
h(2) = 3
h(3) = 9
h(4) = 14
h(5) = 40
h(6) = 64
h(7) = 97

  FOR i = 1 TO 7
   hi = h(i)
   had(hi) = 1
   PRINT #2, USING "#### ##"; hi; hi
   FOR j = i + 1 TO 7
    hj = h(j)
    hij = hi + hj
    himj = ABS(hi - hj)
    IF hij <= 200 THEN had(hij) = 1
    PRINT #2, USING "#### ## ###"; hij; hi; hj
    had(himj) = 1
    PRINT #2, USING "#### ## ###"; himj; hi; -hj
    FOR k = j + 1 TO 7
     hk = h(k)
     hijk = hij + hk
     hijmk = ABS(hij - hk)
     himjk = himj + hk
     himjmk = ABS(himj - hk)
     IF hijk <= 200 THEN had(hijk) = 1
     PRINT #2, USING "#### ## ### ###"; hijk; hi; hj; hk
     IF hijmk <= 200 THEN had(hijmk) = 1
     PRINT #2, USING "#### ## ### ###"; hijmk; hi; hj; -hk
     IF himjk <= 200 THEN had(himjk) = 1
     PRINT #2, USING "#### ## ### ###"; abs(hi-hj+hk); hi; -hj; hk
     IF himjmk <= 200 THEN had(himjmk) = 1
     PRINT #2, USING "#### ## ### ###"; abs(hi-hj-hk); hi; -hj; -hk
    NEXT
   NEXT
  NEXT
CLOSE

 

 

Posted by Charlie on 2006-11-14 23:50:02