Sunday Times Teaser 3133 – Primary Road Network
by John Owen
Published Sunday October 09 2022 (link)
I was recently studying a large map that showed all the towns and major roads in a country. Every town had at least one road leading to it and every road led from one town to another. The roads only met at towns and all joined together to make a network with lots of blank areas in between, which I happily coloured in, needing just four different colours.
I counted up the number of areas (excluding the area around the outside of the network) and the number of towns, and discovered that both numbers were prime. Also, when I took these two numbers with the number of roads, the three numbers together used every digit from 0 to 9 precisely once.
In increasing order, what were the three numbers?
-
Brian Gladman permalink1234567891011121314151617181920from itertools import combinationsfrom number_theory import Primes# Since the layout is a simple, planar graph, we can use# Euler's theorem for such graphs which shows that Roads# = Towns + Areas - 1; moreover, for such graphs we can# assume T < A, since if (T, A, R) is a solution then so# is (A, T, R)for T, A in combinations(Primes(1000), 2):tar = (T, A, T + A - 1)star = tuple(str(x) for x in tar)st, sa, sr = sstar = tuple(set(x) for x in star)if any(len(x) != len(y) for x, y in zip(star, sstar)):continueif (st & sa | sa & sr | sr & st) or len(st | sa | sr) != 10:continueprint(tar)