Teaser 3325: Olive and Don
From The Sunday Times, 14th June 2026 [link] [link]
Olive lives at the southwest corner of a city with a grid of streets (as shown with north at the top). She wants to visit her father Don, who lives at the northeast corner. Olive is trying to work out how many possible routes she can use along the streets, not visiting any intersection more than once, but thinks that there are too many to count. To make the calculation easier, she has decided that she will only travel in the following directions: NW, N, NE, E or SE.
She tells Don the number of possible routes, and he works out that the number is the product of their ages (both of which have two digits).
How old are Olive and Don?
[teaser3325]
Alex.T.Sutherland, and 
Ruud are discussing. 
Frits, 
Hugo, 
GeoffR, 
Tony Brooke-Taylor are discussing. 
Brian Gladman are discussing. 
S2T2 
Jim Randell 6:17 am on 14 June 2026 Permalink |
This Python 3 program generates all possible paths between O and D using the specified directions. And then factorises the number of paths found into two 2-digit numbers.
It runs in 71ms. (Internal runtime is 7.9ms).
from enigma import (icount, divisors_pairs, printf) # the grid of intersections is composed of those points (x, y) = [0..6] * [0..4] # where x and y have the same parity # possible moves (<delta-x>, <delta-y>) which preserve parity moves = [ # parity 0: NW, N, NE, E, SE [(-1, +1), (+0, +2), (+1, +1), (+2, 0), (+1, -1)], # parity 1: NW, NE, SE [(-1, +1), (+1, +1), (+1, -1)], ] # extend path <vs> to <dst> without revisiting a vertex def paths(vs, dst): (x, y) = vs[-1] # are we done? if (x, y) == dst: yield vs else: # consider possible moves for (dx, dy) in moves[x % 2]: v = (vx, vy) = (x + dx, y + dy) if not (vx < 0 or vy < 0 or vx > 6 or vy > 4 or v in vs): yield from paths(vs + [v], dst) # count the number of paths between (0, 0) and (6, 4) n = icount(paths([(0, 0)], (6, 4))) printf("{n} possible paths") # factor n into two 2-digit numbers for (a, b) in divisors_pairs(n): if 9 < a < b < 100: printf("-> {n} = {a} * {b}")Solution: Olive and Don are 49 and 81.
There are 3969 possible routes, and 3969 = 49 × 81.
There is a second candidate solution 3969 = 63 × 63, but I assumed that Olive’s age is less than that of her father.
LikeLike
Jim Randell 10:11 am on 22 June 2026 Permalink |
Here is a manual solution (suggested by John Crabtree [link]):
We draw the diagram like this, so that it consists of 6 levels (L0, …, L5), with one-way roads between the levels, and two-way roads within each level.
To make a path from O to D is to ascend through the 6 levels. Once we leave a level we can never return to it, so a path from O to D is uniquely defined by the choice of blue roads between levels, and every choice defines exactly one path (as there is only one collection of red roads that can link any collection of blue roads).
The number of paths (nP) between O and D is therefore calculated from the product of the number of roads between each level:
And factorising this into a pair of 2-digit numbers we get:
Only the first of which gives a viable answer to the puzzle.
LikeLike
Ruud 11:37 am on 14 June 2026 Permalink |
def search(pos, visited): if pos == (6, 4): yield 1 else: for dir in ((-1, 1), (1, 1), (1, -1)) if pos[0] % 2 else ((-1, 1), (0, 2), (1, 1), (2, 0), (1, -1)): pos_next = tuple(v + d for v, d in zip(pos, dir)) if pos[0] in range(7) and pos[1] in range(5) and pos_next not in visited: yield from search(pos_next, visited | {pos_next}) number_of_routes = sum(search((0, 0), {(0, 0)})) for olive in range(10, 100): if (number_of_routes % olive) == 0 and olive < (don := number_of_routes // olive) < 100: print(f"{number_of_routes=} {olive=} {don=}")LikeLike
Alex.T.Sutherland 8:01 pm on 17 June 2026 Permalink |
Method.
1. Create an Adjacency Matrix (18*18).
This takes care of the no-go directions (S SW W) .
2. I have a ‘graph’ function which will accept the AM
and return the number of paths (with the points
on each path if required).Python has something similar.
In this case the number of paths was a 4 digit number.
3. Using the divisors of this number gave a unique pair
of 2 digit numbers whose product equalled the number
and which can fit the father’s and daughter’s ages
4. My Answer : They are both ‘old-fashioned’.
5. Approx. Times :-
Adjacency Matrix < 1ms; Graph < 3ms ;All Paths < 3ms
Ages determination < 2ms;
LikeLike