Teaser 3133: Primary road network
From The Sunday Times, 9th October 2022 [link] [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?
[teaser3133]
GeoffR, 
Hugh Casement, 
NigelR, 
Frits, and 1 other are discussing. 
S2T2 
Jim Randell 4:31 pm on 7 October 2022 Permalink |
This is an exercise in the properties of planar graphs [@wikipedia].
We can use Euler’s formula:
where:
This Python program runs in 93ms. (Internal run time is 38.6ms).
Run: [ @replit ]
from enigma import (primes, distinct_chars, ordered, printf) # consider V = the number of towns, it is prime for V in primes.between(3, 1000): if distinct_chars(V) is None: continue # consider A = the number of enclosed areas, it is also prime for A in primes.between(5, 2 * V - 5): if distinct_chars(V, A) is None: continue # calculate E = the number of roads E = V + A - 1 if E > 3 * V - 6: continue if distinct_chars(V, A, E) != 10: continue # output solution ns = ordered(V, A, E) printf("{ns} [V={V} A={A} E={E}]")Solution: The three numbers are: 607, 829, 1435.
We can construct a viable map as follows:
Consider the following diagram:
If the central area is an odd n-gon, coloured with the first colour, then it is surrounded by n regions, and as n is odd we require an additional 3 colours to colour these. So at least 4 colours are required, and the 4-colour theorem tells that we don’t need more than 4 colours.
And together the central and surrounding areas contribute:
And adding p petals (we may add multiple layers of elongated petals if necessary), adds:
And a stalk of length s adds:
So using: n = 413, p = 193, s = 3, gives a graph with:
Which provides a viable map.
LikeLike
Jim Randell 8:33 am on 8 October 2022 Permalink |
Using the formula:
where p and q are primes, and (E, p, q) is pandigital, we see that E must be 4-digits, so p and q can only be (2, 4) or (3, 3) digits.
And without further planarity checks there is only one candidate solution, which we can find using the [[
SubstitutedExpression()]] solver from the enigma.py library.The following Python program runs in 83ms. (Internal runtime is 28.4ms)
Run: [ @replit ]
from enigma import (SubstitutedExpression, sprintf as f, printf) # symbols for the digits (terms, result) = ("ABCDEF", "GHIJ") # consider (2,4) and (3, 3) digit terms for i in (2, 3): (x, y) = (terms[:i], terms[i:]) exprs = [ f("is_prime({x})"), f("is_prime({y})"), f("{x} + {y} - 1 = {result}") ] if len(x) == len(y): exprs.append(f("{x} < {y}", x=x[0], y=y[0])) p = SubstitutedExpression(exprs, answer=f("({x}, {y}, {result})")) for ans in p.answers(verbose=0): printf("{ans}")LikeLike
Frits 12:31 am on 8 October 2022 Permalink |
This program considers up to 9999 number of towns.
I stopped programming when the run time got under 10ms.
NB The final P4 list is always logically empty, I didn’t remove the code to process 4-digit number of towns .
from itertools import combinations # formula E = V + A - 1 # V = the number of towns # A = the number of enclosed areas # E = the number of roads sols = set() P = [3, 5, 7] P += [x for x in range(11, 33, 2) if all(x % p for p in P)] P += [x for x in range(33, 1000, 2) if all(x % p for p in P)] # if V has 3 digits then E must be 1xxx # E must have at least 4 digits so V + 2V - 5 - 1 > 999 --> 3V > 1005 # 3-digit primes P3 = [p for p in P if p > 335 and len(s := str(p)) == len(set(s)) and '1' not in s] # first process 3-digit number of towns for V, A in combinations(P3, 2): if V + A < 1024: continue E = V + A - 1 if len(set(str(1000000 * E + 1000 * A + V))) != 10: continue sols.add(tuple(sorted([V, A, E]))) P = [3, 5, 7] P += [x for x in range(11, 100, 2) if all(x % p for p in P)] # if V has 4 digits then the 2nd digit of V, E must be resp 9, 0 # if A ends in 1 then V and E will end in the same digit # 2-digit primes P2 = [p for p in P if p > 9 and all(y not in (s := str(p)) for y in "019") and len(s) == len(set(s))] # 4-digit primes P4 = [x for x in range(1001, 10000, 2) if all(x % p for p in P)] # if V has 4 digits the 2nd digit must be a nine (and may not use a zero) # otherwise E will use some of the same digits # if V ends in 1 then A and E will end in the same digit P4 = [p for p in P4 if (s := str(p))[1] == '9' and '0' not in s and len(s) == len(set(s)) and s[-1] != '1'] # numbers in P2 and P4 always end in 3 or 7 (1, 5, and 9 are not allowed) # so E must end in 9 P2 = [p for p in P2 if '9' not in (s := str(p)) and p not in {37, 73}] P4 = [p for p in P4 if '9' not in (s := str(p)) and all(y not in s[:-1] for y in "37")] # process 4-digit number of towns for V in P4: # if V has 4 digits (x9yz) then A must be at least 101 - yz for A in [p for p in P2 if p >= 101 - V % 100]: E = V + A - 1 if len(set(str(1000000 * E + 1000 * A + V))) != 10: continue sols.add(tuple(sorted([V, A, E]))) # print solutions for s in sols: print(s)LikeLike
Hugh Casement 6:32 am on 9 October 2022 Permalink |
I too had the idea of using Euler’s formula. At first I thought that a town with only a single road leading to it would spoil things, but then realized that they cancel out.
Most unlikely that there would be a four-digit number of towns and only a two-digit number of regions between the roads, or vice versa. In any case, three plus three quickly yields a solution.
I’ll spare you my program code, but Basic’s ability to handle strings was useful in determining whether all ten digits are present.
LikeLike
GeoffR 11:44 am on 9 October 2022 Permalink |
I based my program on (3/3) and (2/4) digit splits for towns/areas, with 4 digits for roads.
from enigma import nsplit, is_prime # form lists of 2, 3 and 4 digit primes # with non-repeating digits to check digit splits pr2 = [n for n in range(11, 99) if is_prime(n) \ and len(set(str(n))) == 2] pr3 = [n for n in range(100, 999) if is_prime(n) \ and len(set(str(n))) == 3] pr4 = [n for n in range(1000, 9999) if is_prime(n) \ and len(set(str(n))) == 4 ] # check if (town/area) digits split is (3, 3) for town in pr3: A, B, C = nsplit(town) for area in pr3: if area == town:continue D, E, F = nsplit(area) if len(set((A, B, C, D, E, F))) != 6:continue roads = town + area - 1 if roads in pr4: continue if roads < 1000 or roads > 9999:continue R1, R2, R3, R4 = nsplit(roads) if len(set((A,B,C,D,E,F,R1,R2,R3,R4))) == 10: if town < area: print(f"1.The three numbers were {town}, {area} and {roads}.") # check if (town/area) digits split is (2,4) for town2 in pr2: a, b = nsplit(town2) for area2 in pr4: c, d, e, f = nsplit(area2) if len(set((a, b, c, d, e, f))) == 6: roads2 = town2 + area2 - 1 if roads2 < 1000 or roads2 > 9999: continue R5, R6, R7, R8 = nsplit(roads2) if len(set((a,b,c,d,e,f,R5,R6,R7,R8))) == 10: print(f"2.The three numbers were {town2}, {area2} and {roads2}.")LikeLike