Brain-Teaser 119: Weights
From The Sunday Times, 7th July 1963 [link]
In the time of the Great Caliph a large annual tax was one day levied on shopkeepers for each weight used in their shops. The ingenious Al Gebra contrived to use very few weights but he often had weights in both his scale pans. The exchequer hit back by making it compulsory to make every weighing by using two weights only, one in each pan. Al now contrived with 20 weights to weigh up to 118 lb. in 1 lb. steps. Using 1 lb. as the least weight he found various ways of doing this. “But”, he said, “I’m getting old and I’m going to have the lightest possible set”.
Which set was this?
[teaser119]
Frits are discussing. 
S2T2 
Jim Randell 8:38 am on 11 September 2022 Permalink |
This puzzle was published with a note that the previous weeks puzzle, Teaser 118 (also involving finding a set of weights), had solicited “no correct solution”.
However, as we found, the published solution for Teaser 118 is incorrect.
In this puzzle we are also asked to find a set of weights, and the originally published solution is also incorrect (although a correction was later made with one optimal set of weights, although it turns out this set is not unique).
If the lightest weight is 1 lb, then the heaviest weight we need is 119 lb (to create a difference of 119 − 1 = 118), and the remaining 18 weights can fit in between.
This is equivalent to constructing a sparse ruler [@wikipedia] of length 118, with 20 marks.
And as we want to cover all differences 1 … 118, the ruler must be complete.
I started by writing a program to find complete sparse rulers, and then adapted it to produce rulers with a minimal total sum for the set of marks, and from these we construct sets of weights to solve the puzzle.
For a set of 20 weights weighing values 1 … 118 the program takes 29m28s to find the 5 optimal solutions (although the solutions are found much faster than this (in 5.4s), the rest of the time is spent completing the search to ensure there are no better solutions).
from enigma import (irange, append, diff, empty, reverse, Accumulator, arg, printf) # generate sparse rulers # L = length # M = number of marks # ms = existing marks (as a set) # k = number of remaining marks # xs = distances not yet satisfied (as an ordered list) # zl = left zone # zr = right zone # r = Accumulator (on the sum of the marks) def rulers(L, M, ms, k, xs, zl, zr, r): if k == 0: if not xs: ms = sorted(ms) t = sum(ms) # is the mirror image better? if L * M < 2 * t: ms = reverse(L - x for x in ms) t = L * M - t # record the value r.accumulate_data(t, ms) if r.value == t: printf("[{ms} -> {t}]") else: # perform some early termination checks: # are there too many unsatisfied differences remaining? if xs and len(xs) > (k * (k - 1)) // 2 + k * (M - k): return # is max distance too big? if xs and xs[-1] > max(zr, L - zl): return # will the additional marks exceed the current best? if r.value and sum(ms) + sum(irange(zl, zl + k - 1)) > r.value: return # can we fit k marks in the gaps? if zr - zl + 1 < k: return # extend left zone? if not (zl > L - zr): # try with mark at zl ds = set(abs(m - zl) for m in ms) rulers(L, M, append(ms, zl), k - 1, diff(xs, ds), zl + 1, zr, r) # try without mark at zl rulers(L, M, ms, k, xs, zl + 1, zr, r) else: # try without mark at zr rulers(L, M, ms, k, xs, zl, zr - 1, r) # try with mark at zr ds = set(abs(m - zr) for m in ms) rulers(L, M, append(ms, zr), k - 1, diff(xs, ds), zl, zr - 1, r) # generate complete rulers complete_rulers = lambda L, M, r: rulers(L, M, {0, L}, M - 2, list(irange(1, L - 1)), 1, L - 1, r) # ruler length and marks L = arg(118, 0, int) M = arg(20, 1, int) printf("[L={L} M={M}]") # generate complete rulers with length L, and M marks, and recorded minimal total r = Accumulator(fn=min, collect=1) complete_rulers(L, M, r) # use optimal rulers printf("best = {r.value}") for ss in r.data: printf("-> ruler = {ss}") # make the weights ws = list(x + 1 for x in ss) printf("-> weights = {ws}; total = {t}", t=sum(ws))Solution: There are five possible sets of weights, each set weighs 712 lb:
The originally published solution (with Teaser 120) is:
which is not optimal.
But this was later revised (with Teaser 122) to:
which is the third of the optimal sets I give above.
The puzzle says the tax is levied for each weight, so it may be preferable to use fewer weights.
Each pair of weights corresponds to potential actual value, and C(15, 2) = 105, does not give enough pairs. But C(16, 2) = 120 does. So it is potentially possible that a set of 16 weights could be used to achieve our goal of weighing each of the weights 1 … 118.
I checked sets of 16, 17, 18 (that include a 1 lb weight), but didn’t find any viable sets.
But for a set of 19 weights I found:
This is heavier than the optimal solution sets with 20 weights (sum = 712), but if the tax per weight was high it may be preferable.
However, by using more weights we can come up with a lighter set:
Here are the optimal sets of size 21 to 25:
after which the total weight starts going up again.
So the lightest set of weights is one of the sets of size 25.
But presumably, the intricacies of the tax system have led Al Gebra to conclude that the extra weight for an optimal set of 20 weights is offset by the difference in tax on the lighter set of 25 weights.
LikeLike
Frits 2:08 pm on 11 September 2022 Permalink |
The numbers 20 and 118 were probably chosen as it leads to a solution which it is relatively easy to check for completeness.
in this case we can formulate L + 1 as (n + 1) * n + n - 1 where n = M / 2 1-n n+1 - 2n 2n+2 - 3n+1 (n-1)n+n-1 - n*n+n-2 1,2,3,..., n , 2n+1, 3n+2, ....... , n*n+n-1, (n+1)n+n-1 We can already start with minimum n*(n+1)//2 + ((n+2)*(n+1)//2 - 1)*n + n*(n+1)//2 - 1 = M**3 / 16 + 5*M**2 / 8 + M / 2 - 1 = 759 ( originally published solution)LikeLike
Frits 12:19 pm on 12 September 2022 Permalink |
This program runs in 11.5 seconds with PyPY (with inc set to 3).
I am not sure if we can rely on the weights always to contain number 1 so we have to see this program as a way to get a low total weight.
from itertools import combinations M = 20 L = 118 # can we make number 1,...,N with numbers from <seq> def check(seq): s = set() for c1, c2 in combinations(seq, 2): d = c2 - c1 if 0 < d < L + 1 and d not in s: s.add(d) if len(s) == L: return True return False # pick one value from each entry of a <k>-dimensional list <ns> def pickOneFromEach(k, ns, s=[]): if k == 0: yield s else: for n in ns[k - 1]: yield from pickOneFromEach(k - 1, ns, s + [n]) n = 10 M = 20 break_next = 0 # assume the first sequence of consecutive weights is 1,2,3, ..,m # then the last 2 weight must be L + 1 - m, L + 1 # we have to choose M - m - 2 weights between m and L + 1 - m best = 99999 inc = 3 # allowed deviance from calculated middle value for m in range(17, 0, -1): print() print("suppose the first consecutive weights are", list(range(1, m + 1))) print("then the last 2 weight must be", [L + 1 - m, L + 1]) print("we have to choose", M - m - 2, "weights between", m, "and", L + 1 - m, "with", M - m - 1, "intervals") # calculate groups of allowed values per missing weight ws = [[m + i + x * (L + 1 - 2 * m ) // (M - m - 1) for i in range(-inc, inc + 1)] for x in range(1, M - m - 1)] print("choose weights from", *ws) for p in pickOneFromEach(M - m - 2, ws): # rebuild full set of weights ns = list(range(1, m + 1)) + sorted(p) + [L + 1 - m, L + 1] if sum(ns) > best: continue # check if we can make all numbers 1 - 118 if not check(ns): continue best = sum(ns) print(ns, "with total weight", sum(ns)) if break_next: break if best < 99999: # we assume that a lower <m> results in a higher total weight # perform one extra run with a lower <m> anyway break_next = 1LikeLike
Jim Randell 5:07 pm on 12 September 2022 Permalink |
We are told in the puzzle text that the lowest weight is 1lb.
Even if we weren’t told, given any set of weights all that matters is the set of differences. So all the weights can be reduced (or increased) by the same amount to give another set.
Specifically if we reduce the lowest weight to 1 we will get the minimal possible set based on the original set.
In fact we can reduce the lowest weight to 0, and then we end up with the corresponding ruler.
LikeLike