Sunday Times Teaser 2980 – Egyptian Weights and Measures
by Susan Bricket and John Owen
Published November 3 2019 (link)
We were wondering why ancient Egyptians chose to represent arbitrary fractions as sums of distinct unit fractions of the form 1/n (thus 5/7 = 1/2+1/5+1/70). One of us recalled long ago watching our greengrocer use four brass weights of 1/2, 1/4, 1/8, 1/16 lb to weigh any number of ounces up to 15 by stacking some of them on one side of her balancing scales. We wanted to make a metric equivalent, a set of distinct weights of unit fractions of a kilo, each weighing a whole number of grams, to weigh in 10g steps up to 990g.
Naturally, we wanted to use as little brass as possible, but we found that there were several possible such sets. Of these, we chose the set containing the fewest weights.
List, in increasing order, the weights in our set.
-
Brian Gladman permalink1234567891011121314151617181920212223242526272829303132333435363738394041from itertools import combinations, chain# from Python itertools documentation - the set of subsetsdef powerset(s):return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))# if we can make the weights from 10 to 240 grams in 10 gram# steps, we can then make the weights 250, 260, ... 980, 990# by adding 250 and/or 500 grams (1/4 and 1/2 Kgs) as neededtarget = set(x for x in range(10, 250, 10))# find all weights in grams less than 250 grams that are# unit fractions of 1000 gramsweights = set(x for x in range(1, 250) if 1000 % x == 0)# for storing minimal valuesmin_wght, min_lnth, min_wset = None, None, None# pick a subset of the possible weightsfor wset in powerset(weights):# can all target weights be made?if target <= set(sum(wts) for wts in powerset(wset)):# the full set of weights, their number and weightwsetx = tuple(sorted(wset)) + (250, 500)lnth, wght = len(wsetx), sum(wsetx)# is this set of weights lighter than any already found?if min_wght is None or wght < min_wght:min_wght, min_lnth, min_wset = wght, lnth, wsetx# is this set of weights the same total weight but less in# number than that already found?if min_wght is not None and min_wght == wght:if lnth < min_lnth:min_lnth, min_wset = lnth, wsetxprint(f"{min_lnth} weights weighing {min_wght} grams: {min_wset}")