Teaser 3218: Algorithm Al
From The Sunday Times, 26th May 2024 [link] [link]
On his 35th birthday, maths teacher Al’s three younger half-sisters bought him “The Book of Numbers for Nerds” as a tease. It showed how to find right-angle triangles with whole-number sides using any two unequal odd square numbers. You take half their sum; half their difference; and the square root of their product to get the three sides. Any multiple of such a triplet would also work. He told his sisters this and that their ages were the sides of such a triangle. “Algorithm Al!” they yelled.
Knowing the age of any one sister would not allow you to work out the other ages with certainty, but in one case you could be sure of her place chronologically (youngest, middle or oldest).
Give the three sisters’ ages (youngest to oldest).
[teaser3218]
Frits and 
S2T2 
Jim Randell 5:33 pm on 24 May 2024 Permalink |
(See also: Teaser 3017).
The construction of primitive Pythagorean triples in this way is known as Euclid’s formula [@wikipedia].
This program collects Pythagorean triples with sides less than 35, and looks for triangles where all sides appear in more than one candidate triangle.
Of the selected triangles we look for a side that can only appear in one specific position in the ordering (again, considering all candidate triangles). And this identifies the required answer.
It runs in 63ms. (Internal runtime is 193µs).
Run: [ @replit ]
from enigma import ( defaultdict, pythagorean_triples, multiset, singleton, icount, printf ) # collect possible triangles tris = list(pythagorean_triples(34)) # record positions of each side d = defaultdict(multiset) for tri in tris: for (i, x) in enumerate(tri): d[x].add(i) # check a candidate triangle def check_tri(tri): # each side must appear in multiple triangles if not all(d[x].size() > 1 for x in tri): return printf("tri = {tri}; all sides occur in multiple triangles") # look for sides that can only appear in a single position for x in tri: k = singleton(d[x].distinct_elements()) if k is not None: printf("-> {x} only appears in pos {k}") yield (x, k) # check triangles, exactly one side appears in a single position for tri in tris: if icount(check_tri(tri)) == 1: printf("=> SOLUTION: ages = {tri}")Solution: The three ages are: 15, 20, 25.
There are just five primitive triangles we are interested in:
Candidate triangles are formed from these, along with multiples such that the largest side does not exceed 34.
And the only candidate triangles where every side length occurs in another triangle are:
And of these sides only 25 always appears as the largest side length:
LikeLike
Frits 5:55 pm on 24 May 2024 Permalink |
Following the instructions.
sols = set() # odd squares osqs = [i * i for i in range(1, 68, 2)] for i, a in enumerate(osqs): if a > 33: break for b in osqs[i + 1:]: # calculate sister's ages p = (a + b) // 2 if p > 34: break q = abs(a - b) // 2 r = int((a * b) ** .5) # allow for multiples for k in range(1, 35): if any(x > 34 for x in [k * p, k * q, k * r]): break sols.add(tuple(sorted([k * p, k * q, k * r]))) sides = set(y for x in sols for y in x) # dictionary of age appearing as y/m/o d = {s: [sol.index(s) for sol in sols if s in sol] for s in sides} # group of sisters that qualify gs = [sol for sol in sols if all(len(d[s]) > 1 for s in sol)] for sisters in gs: if sum([len(set(d[s])) == 1 for s in sisters]) == 1: # in one case ... print("answer:", sisters)LikeLike