Sunday Times Teaser 3802 – In the Swim
by Nick MacKinnon
Published Sunday October 17 2021 (link)
Expert mathematicians Al Gritham, Ian Tadger, Carrie Over and Tessa Mole-Poynte have a swimming race for a whole number of lengths. At some point during each length (so not at the ends) they calculate that they have completed a fraction of the distance, and at the finish they compare their fractions (all in the lowest terms). Al says, “My fractions have prime numerators, the set of numerators and denominators has no repeats, their odd common denominator has two digits, and the sum of my fractions is a whole number.” Tessa says, “Everybody’s fractions have all the properties of Al’s, but one of mine is closer to an end of the pool than anybody else’s.”
What were Tessa’s fractions?
-
Brian Gladman permalink1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283from itertools import combinations, countfrom collections import defaultdictfrom math import gcd# primes less than 100pr = {2, 3, 5, 7}pr |= {x for x in range(11, 100, 2) if all(x % p for p in pr)}# return the sum of fractions in <f> [as tuples (n, d)]def fsum(f):nr, dr = 0, 1for n, d in f:nr, dr = nr * d + dr * n, dr * dg = gcd(nr, dr)return nr // g, dr // g# find fractions given the common denominator <d># and the number of pool lengths <nl> in the racedef compose(fr, nl, lc=0, nds=set(), seq=()):if lc == nl:# the sum of the fractions is an integerif fsum(seq)[1] == 1:yield seqelse:# consider the numerators of possible fractionsfor nd in fr[lc]:if not nds.intersection(nd):yield from compose(fr, nl, lc + 1, nds.union(nd), seq + (nd,))# consider the number of pool lengths racedmtc = 0for nl in count(2):fs = []# consider the possible common denominatorsfor d in range(11, 100, 2):# collect possible fractionsfr = []for i in range(d):g = gcd(i, d)nd = (i // g, d // g)if nd[0] in pr:fr.append(nd)# create <fs> such that fs[i] will contain fractions of the length# of the race that are in the (i + 1)'th pool length of the racefl = defaultdict(list)for f in fr:m, r = divmod(nl * f[0], f[1])if r:fl[m].append(f)# find collections fractions with no duplicated numbers# in their numerators and denominators combinedfor s in compose(fl, nl):fs.append(s)# we must have four or more solutions (to allow one for each swimmer)if len(fs) >= 4:# convert a fraction to a percentagef2p = lambda f: round(100 * abs(f[0]) / f[1], 2)mv = []# consider possible solutions for four swimmersfor c4 in combinations(fs, 4):# find the minimum distances of the fractions# from the ends of the poolfor f in c4:m = min(f2p(fsum([a, (-b - i, nl)]))for a, b in zip(f, range(nl)) for i in (0, 1))mv.append((m, f))# Tessa's swim has the minimum distance from a pool endts = "(Tessa's)"for i, (m, s) in enumerate(sorted(mv)):tt = ', '.join(f'{a}/{b}' for a, b in s)print(f"{m:4.2f}% ({tt}) {ts if i == 0 else ''}")else:# count empty resultsmtc += 1# and exit if there are more than two in a rowif mtc > 2:break