Teaser 2416: [Path-o-logical]
From The Sunday Times, 11th January 2009 [link]
Recently, Joe repaved his metre-wide front path. He used square slabs with half-metre sides, some of the slabs being pink and the rest grey. He made the first two slabs pink, then he arranged the rest so that the pattern of the four slabs in any square metre was not repeated, as would be seen by anyone walking forward along the path towards the front door. This would not have been possible had the path been any longer.
(a) How long is Joe’s front path?
(b) What are the colours of the last two slabs?
This puzzle was originally published with no title.
[teaser2416]
S2T2 
Jim Randell 9:45 am on 8 July 2026 Permalink |
See also: Enigma 1511, Enigma 1520.
From a fixed viewpoint (so we don’t have to worry about rotations) it is easy to see that there are 4 possible pairs of tiles (“pp”, “pg”, “gp”, “gg”), and these can appear at the top or bottom of a 4×4 unit, so there are 16 possible units. Which if they are all used would lead to 16 tops and 16 bottoms which overlap to fit on a 17×0.5 m = 8.5 m path.
This Python program constructs all possible maximal paths.
It runs in 754ms. (Internal runtime is 704ms).
from enigma import (Accumulator, empty, printf) # possible pairs of slabs pairs = ["pp", "pg", "gp", "gg"] # extend the path <ps> without repeating two pairs def solve(ps, seen=empty): # look for possible next pairs x = ps[-2:] nps = list(p for p in pairs if x + p not in seen) # are we done? if not nps: yield ps else: for p in nps: yield from solve(ps + p, seen.union({x + p})) # [Python 3] # look for maximal length paths r = Accumulator(fn=max, collect=1) for ps in solve("pp"): r.accumulate_data(len(ps), ps) printf("max path len = {n} m", n=r.value * 0.25) printf("-> {ps} [of {n}]", ps=r.data[0], n=len(r.data)) printf("final = {ss}", ss=set(ps[-2:] for ps in r.data))Solution: (a) Joe’s front path is 8.5 m long; (b) The last two slabs are both pink.
For example:
There are 82944 possible maximal length arrangements, and each ends with a double-pink slab (so each arrangement will appear both forwards and backwards). Which means the path could be bent around so the start and end pairs overlapped to give a circular arrangement with all possible 2×2 arrangements. (And the loop can then be broken at an appropriate point to give a path starting with any particular pair).
LikeLike