Brain-Teaser 118: [Ceremonial weights]
From The Sunday Times, 30th June 1963 [link]
“On our last expedition to the interior”, said the famous explorer, “we came across a tribe who had an interesting kind of Harvest Festival, in which every male member of the tribe had to contribute a levy of grain into the communal 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 weights. 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”.
“We were told that if ever a tribesman lived to such an age that his contribution could no longer be weighed by using three weights only, the levy of grain would terminate for ever. 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”.
“The scientist with our expedition confirmed that the weights had been selected so that the critical age was the maximum possible”.
What was the age of the old man when he died?
And what were the weights of the seven ceremonial weights?
This puzzle was originally published with no title.
[teaser118]
Frits, 
Hugh+Casement, and 
GeoffR, 
Robert Brown are discussing. 
John Crabtree and 
NigelR, 
S2T2 
Jim Randell 12:50 pm on 4 September 2022 Permalink |
I had a look at this puzzle, as according to the published answer: “No correct solution [was] received”.
But the published solution does not seem to be the best answer to the puzzle.
The following program considers sets of weights by increasing total weight. I assumed that all the weights were different (as this seems like an obvious way to increase the number of different combinations we can make, but I don’t want to make too many assumptions, as that might be what tripped up the original setter. Duplicate weights are useful for lower values of the total weight, but not as the total weight increases).
However it is not quick. I left it running overnight, and it checked sets with a total weight of up to 350 lbs.
from enigma import (Accumulator, irange, inf, decompose, subsets, peek, printf) # find the first unreachable weight using weights <ws> def unreachable(ws): # find possible weights using a single weight vs = set(ws) # using 2 weights for (a, b) in subsets(ws, size=2, select="C"): vs.add(b + a) vs.add(b - a) # using 3 weights for (a, b, c) in subsets(ws, size=3, select="C"): vs.add(c + b + a) vs.add(c + b - a) vs.add(c - b + a) vs.add(abs(c - b - a)) # find the first unreachable weight return peek(v for v in irange(1, inf) if v not in vs) # accumulate maximum first unreachable weight r = Accumulator(fn=max, collect=1) # consider possible totals for the 7 weights for t in irange(28, 350): # find values for the 7 weights (all different) for ws in decompose(t, 7, increasing=1, sep=1, min_v=1): # find the first unreachble age v = unreachable(ws) # overall best r.accumulate_data(v, ws) if v == r.value: printf("[t={t}: {v} -> {ws}]") # output best found in range printf("unreachable weight = {r.value}") for ws in r.data: printf("-> {ws}; total = {t}", t=sum(ws))(You might want to reduce the range at line 24 if you run this program. e.g. To find the improved solutions you might want to consider t = 238 … 244, this takes about 40 minutes).
The published solution was that the man was 120 years old when he died (i.e. the first unreachable weight was 121 lbs).
And the seven weights were: 1, 3, 9, 14, 40, 70, 103 lb (total = 240 lb).
However this is not the only set of weights that can allow every amount between 1 and 120 lb to be weighed using up to 3 weights, for example:
So the published solution is not unique.
However, there are combinations of weights that allow us to weigh greater contiguous amounts:
The first of these has a lower total weight than the published solution.
And the final set is the best I have found and gives the following solution to the puzzle:
Solution: The old man was 122 years old when he died. The weights were: 1, 3, 7, 12, 43, 76, 102 lb.
With this set the first unreachable weight is 123 lb, and as this is set is the only set that can weigh 1 … 122 lb the solution is unique.
So it is possible that The Sunday Times may have received correct solutions, it is just that they didn’t match the setters incorrect solution. I checked subsequent Teaser puzzles, but was not able to find an apology or correction.
All the sets that allow weights of (1 … 119) to be made lie between total = (213 … 272), so having checked all totals up to 350 it seems reasonable to assume that this solution may be optimal.
Here is a plot of the first unreachable weight (y) vs. total weight (x). We see that the maximum is achieved at x = 244, and as the total weight increases the first unreachable weight is tending down.
See also: Pages 5-7 of Optima 65 (May 2001) [ PDF ] [ PDF ], which reaches the same conclusion, using a considerable amount of analysis and also computing time. (I found this reference by searching the web for the improved answer found by my program).
LikeLike
Jim Randell 2:56 pm on 4 September 2022 Permalink |
I think I have convinced myself that there is no use having a weight greater than (roughly) 2t/3, otherwise we create a gap at (roughly) t/3.
So we can provide the call to [[
decompose()]] with an argument ofmax_v=divf(2 * t + 2, 3).Which will allow the code to run a little faster.
LikeLike
Hugh+Casement 5:03 pm on 4 September 2022 Permalink |
Hard to believe that a man in what is presumably a village somewhere in Africa (where in the past even 50 counted as very old) could reach an age of 120 or so.
Would we find a more reasonable solution if there were only six weights in the set?
LikeLike
Jim Randell 5:15 pm on 4 September 2022 Permalink |
@Hugh: For 3 out of 6 weights I found the best set is:
which can weigh 1 … 84.
LikeLike
Hugh+Casement 6:51 pm on 4 September 2022 Permalink |
Thanks for the swift reply, Jim.
That looks a much more reasonable solution
— I mean a much more reasonable puzzle.
LikeLike
Frits 11:42 pm on 31 May 2024 Permalink |
Same concept but more efficient (if possible to run with PyPy).
I also tried decompose() with N-2 and N-3 but that was not as efficient.
For 8 weights the best set looks to be:
(1, 3, 9, 14, 21, 59, 108, 148)
which can weigh 1 … 172.
from itertools import combinations from sys import argv N = 7 if len(argv) != 2 else int(argv[1]) tri = lambda n: (n * (n + 1)) // 2 # decompose number <t> into <k> increasing numbers (minimum <mn>) # so that sum(<k> numbers) equals <t> def decompose(t, k=6, mn=1, s=tuple()): if k == 1: if s[-1] < t: yield s + (t, ) else: # can we make <t - n> in <k - 1> decompositions? for n in range(mn if not s else s[-1] + 1, (t - k * (k - 3) // 2) // k): yield from decompose(t - n, k - 1, mn, s + (n, )) def solve(ws, opt): c2 = set() # find possible weights using 2 weights for (a, b) in combinations(ws, 2): c2.update([b + a, b - a]) # possible weights using 1 or 2 weights vs = set(ws) | c2 one_or_two = vs.copy() # using 3 weights for (a, b, c) in combinations(ws, 3): vs.update([c + b + a, c + b - a, c - b + a, abs(c - b - a)]) # number of new numbers to consider extra = 50 if opt < 95 else 10 # unreachable numbersfor all combinations in <ws> missing = [i for i in range(1, opt + 10) if i not in vs] # find an additional higher weight that reaches a lot of unreachable numbers higher_ws = set(range(ws[-1] + 1, max(ws[-1] + extra, opt + extra))) for m in missing: for element in higher_ws: break # get any element from set # which remaining numbers greater than ws[-1] can reach numbers 1...m higher_ws &= {m} | {abs(x * i + m) for i in one_or_two for x in [-1, 1]} if not higher_ws: return (m, element) # number <m> is unreachable # all missing numbers could be reached, try again with more missing numbers return solve(ws, opt + 50) mx, seq = 0, [] # consider possible totals for the first <N - 1> weights for t in range(tri(N - 1), 200): # adapt for different N or a bigger range # find values for the <N - 1> weights (all different) for ws in decompose(t, N - 1): # find the first unreachable age v, k = solve(ws, mx - 1 if mx else t) # overall best if v > mx: seq = ws + (k, ) print(f"[total first {N - 1} weights={t}: {v} -> {seq}]") mx = v # output best found in range print(f"unreachable weight = {mx}") print(f"-> {seq}")LikeLike