Sunday Times Teaser 2511 – No Title
by Danny Roth
Published November 7 2010 (link)
I have a collection of silver medallions, each of which weighs an exact whole number of grams. If I take pairs of them in every possible combination, I can weigh out an almost complete sequence of 16 consecutive weights, with only two weights, 100 grams and 101 grams, missing from the sequence. Even so, I can still manage an unbroken sequence of 13 weights, with only one of them, a prime number of grams, duplicated.
What, in ascending order, are the weights in grams of my medallions?
One Comment
Leave one →
-
Brian Gladman permalink123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960from itertools import count, combinationsfrom number_theory import is_prime# return the position and length of the maximum# sub-sequence of consecutive integers in the# input sequencedef max_subseq(s):i_max, l_max, ic, lc = 0, 0, 0, 1for i in range(len(s) - 1):if s[i + 1] - s[i] == 1:lc += 1else:if lc > l_max:i_max, l_max = ic, lcic, lc = i + 1, 1return i_max, l_max# we need six weights to make 15 different pairs and# we are looking for a sequence of six integers that# when added in pairs can make 13 consecutive values# with only one duplicated and one separated value# select six values from an increasing range of values# until we find values that match the form neededfor n in count(7):# try all combinations of six valuesfor c in combinations(range(1, n), 6):# form the number sequence when added in pairsv = tuple(sum(p) for p in combinations(c, 2))sv = sorted(set(v))# find the position and length of the maximum# sequence of consecutive valuesix, lx = max_subseq(sv)# look for sequences of the correct formif lx == 13 and len(sv) == 14:# find the isolated value and the adjacent valuev0, v1 = (sv[0], sv[1]) if ix else (sv[-1], sv[-2])# ... and the duplicate in the sequencedup, *rest = tuple(x for x in sv if v.count(x) > 1)# there must be two missing values and one duplicateif abs(v1 - v0) == 3 and not rest:# now find an offset that puts the missing values# at 100 and 101; since each weighing involves# two weights, the offset for the weights is one# half that for the weighed valuesofs, r = divmod(99 - min(v0, v1), 2)if not r:weights = tuple(x + ofs for x in c)dup += 2 * ofs# check that the duplicate is a primeif is_prime(dup):s1 = f'{v0 + 2 * ofs}'if v0 > v1:v1 = v1 - lx + 1s2 = f'{v1 + 2 * ofs}..{v1 + 2 * ofs + lx - 1}'ss = f'({s1}, {s2})' if v0 < v1 else f'({s2}, {s1})'print(f'weights {weights} can weigh {ss}, {dup} two ways.')exit()