Teaser 3194: A proper lesson
From The Sunday Times, 10th December 2023 [link] [link]
A maths teacher wrote a sequential list of numbers 1, 2, 3, 4, … on the blackboard and asked her pupils to find a pair of positive fractions adding up to 1. The pair was to have the two numerators and two denominators consisting of four different numbers from her list. They found all possible pairs.
She then told them to group two of the pairs that used eight different numbers from her list, which was just long enough to enable them to do this. The class found all possible groups. One of the groups contained some fractions that were not used by any other group.
Which of the teacher’s numbers were not used by that group?
[teaser3194]
Frits and 
GeoffR and 
Hugo, 
Ender Aktulga are discussing. 
S2T2 
Jim Randell 4:56 pm on 8 December 2023 Permalink |
This Python program considers increasing maximum values written on the blackboard, and collects new pairs of fractions as they become available, until it is possible to form groups consisting of 2 pairs that use 8 different numbers in the fractions.
It then examines the groups found to determine which of them contain fractions that only occur in that group, and these groups provide the answer.
It runs in 53ms. (Internal runtime is 519µs).
Run: [ @replit ]
from enigma import ( irange, inf, fraction, multiset, subsets, flatten, diff, chunk, join, sprintf as f, printf ) # format a list of numbers as fraction sums fmt = lambda ns: join((f("{a}/{b} + {c}/{d} = 1") for (a, b, c, d) in chunk(ns, 4)), sep="; ") # collect possible pairs of fractions a/b + c/d = 1 ps = list() # consider increasing 1..n values for n in irange(4, inf): np = len(ps) # add in a/b, c/n pairs for c in irange(1, n - 1): (a, b) = (p, q) = fraction(1, 1, -c, n) while b < n: ns = (a, b, c, n) if len(set(ns)) == 4: ps.append(ns) a += p b += q if n < 8 or len(ps) == np: continue # find possible groups, and count occurrences of fractions (gs, m) = (list(), multiset()) for ns in subsets(ps, size=2, fn=flatten): if len(set(ns)) == 8: printf("[n={n}: {ns}]", ns=fmt(ns)) gs.append(ns) m.update_from_seq(chunk(ns, 2)) if not gs: continue # find groups that contain fractions that only occur in one group for ns in gs: if any(m.count(x) == 1 for x in chunk(ns, 2)): # output solution ans = diff(irange(1, n), ns) printf("unused = {ans} [{ns}]", ans=join(ans, sep=", ", enc="()"), ns=fmt(ns)) # we only need the smallest n that forms groups breakSolution: The unused numbers are 7 and 8.
The teacher wrote the numbers 1 .. 10 on the board.
This gives 17 possible pairs of fractions that sum to 1:
Note that fractions do not have to be in their lowest terms, so 1/2 and 3/6 are considered to be different fractions (with the same value).
These can be formed into 9 groups that use 8 distinct numbers in the fractions:
And it is not possible to form any groups using 1 .. 8 or 1 .. 9, so 1 .. 10 is the smallest set of initial numbers on the blackboard.
Of the fractions used in these groups, only 4/5 and 2/10 appear in only one group [*], and this group is:
And so the 2 numbers on the blackboard that are not used in any of these four fractions are 7 and 8.
LikeLike
Frits 10:50 am on 9 December 2023 Permalink |
# numbers 1, 2, 3, ..., n, we need 2 groups with in total 8 different numbers n = 8 while True: # determine numbers (a, b, c, d) do that a/b + c/d = 1 with c > a abcd = set((a, b, c, d) for a in range(1, n // 2 + n % 2) for b in range(a + 1, n + 1) for c in range(a + 1, n + 1) if c != b and \ not (dm := divmod(b * c, b - a))[1] and \ c < (d := dm[0]) <= n and d != b) # find 2 groups of <abcd> entries that use 8 different numbers among them two_groups = [(s1[:2], s1[2:], s2[:2], s2[2:]) for s1 in abcd for s2 in abcd if s1[0] < s2[0] and len(set(s1 + s2)) == 8] if not two_groups: n += 1 # try numbers 1, 2, 3, ..., n continue # one of the groups contained some fractions # that were not used by any other group all_fractions = [f for g2 in two_groups for f in g2] unique_fractions = {f for f in all_fractions if all_fractions.count(f) == 1} for g2 in two_groups: # does a fraction in <g2> only occur in our <g2>? if any(f for f in g2 if f in unique_fractions): used = set(y for x in g2 for y in x) print(f"unused numbers: " f"{[i for i in range(1, n + 1) if i not in used]}") breakLikeLike
Frits 12:36 pm on 9 December 2023 Permalink |
Slower but more compact.
from itertools import permutations n = 8 while True: # determine different numbers (a, b, c, d, e, f, g, h) so that # a/b + c/d = 1 and e/f + g/h = 1 with c > a, g > e and a < e abcdefgh = [((a, b), (c, d), (e, f), (g, h)) for a, b, c, d, e, f, g, h in permutations(range(1, n + 1), 8) if a < b and c < d and e < f and g < h and a < c and e < g and a < e and a * d + b * c == b * d and e * h + f * g == f * h] if not abcdefgh: n += 1 # try numbers 1, 2, 3, ... for a higher n continue # one of the groups contained some fractions # that were not used by any other group all_fractions = [fr for f4 in abcdefgh for fr in f4] unique_fractions = {f for f in all_fractions if all_fractions.count(f) == 1} for f4 in abcdefgh: # does a fraction in <f4> not occur in any other <abcdefg> entry? if any(f for f in f4 if f in unique_fractions): used = set(y for x in f4 for y in x) print(f"unused numbers: " f"{[i for i in range(1, n + 1) if i not in used]}") break # we are doneLikeLike