Teaser 3338: Any way but back
From The Sunday Times, 13th September 2026 [link] [link]
For her research on insect migration, Sophie has constructed a rectangular flat box in which insects travel from the SW corner to the NE corner. Inside are obstacles, arranged in rows and columns running from West to East and South to North, that the insects have to travel around, moving North or East, or (via a tunnel) diagonally through, moving NE. On each obstacle there is the option of closing the tunnel.
The total number of possible pathways across the box, with all tunnels open, is too big for Sophie’s purposes, but closing just one of the obstacles’ diagonal passages reduces the total number of possible routes by seven eighty-ninths (7/89).
What is the smallest number of obstacles that can be in the box?
[teaser3338]
Ruud van der Ham, 
Frits, and 
Alex.T.Sutherland, 
Hugo, 
S2T2 
Jim Randell 7:12 am on 13 September 2026 Permalink |
(See also: Tantalizer 457).
The following Python program calculates numbers of paths constructively in rectangles of increasing area, until it finds an area where blocking of just one of the tunnels produces the required reduction in the number of paths.
We only check for obstacles in the left-hand half of the grid, as paths are reversible, so the path counts in the right-hand side of the grid are just a rotation of those in the left-hand side.
The program runs in 67ms. (Internal runtime is 706µs).
from enigma import (irange, inf, divisors_pairs, div, cproduct, divc, cache, printf) # count the paths from (x, y) to (0, 0) in a grid # with an optional obstacle at <block> @cache def npaths(x, y, block=None): if x == 0 or y == 0: return 1 k = (x1, y1) = (x - 1, y - 1) r = npaths(x1, y, block) + npaths(x, y1, block) if k != block: r += npaths(x1, y1, block) return r # consider increasing area rectangles for A in irange(1, inf): s = 0 # consider possible width <w> and height <h> for (h, w) in divisors_pairs(A): # count number of paths with no blocks n0 = npaths(w, h) # target number of paths = (82/89) n0 n1 = div(n0 * 82, 89) if n1 is None: continue # block the diagonal path in one of the cells for block in cproduct([irange(divc(w, 2)), irange(h)]): # have we achieved the target? if npaths(w, h, block) == n1: printf("{w} x {h} (area = {A}) -> {n0} paths; block @ {block} -> {n1} paths") s += 1 if s: printf("[{s} solutions]") breakI am assuming that the question is asking for the area of the smallest possible box (where each cell contains an obstacle).
Solution: [To Be Revealed]
LikeLike
Jim Randell 5:22 pm on 13 September 2026 Permalink |
With some analysis:
For a w by h box the number of paths with no blocks is given by the Delannoy Number [@wikipedia]:
And the number of paths that include a blocked diagonal crossing at (x, y) → (x + 1, y + 1) is given by:
(i.e. we choose a path to the start of the tunnel, and then a path from the end of the tunnel to the final destination).
So we can look for the specific reduction we need.
This gives a slightly faster program. It has an internal runtime of 458µs.
from enigma import (irange, inf, C, divisors_pairs, div, cproduct, divc, cache, printf) # calculate Delannoy number D(w, h) @cache def D(w, h): n = min(w, h) return (1 if n == 0 else sum(C(w, k) * C(h, k) * (2**k) for k in irange(0, n))) # consider increasing area rectangles for A in irange(1, inf): s = 0 # consider possible width <w> and height <h> for (h, w) in divisors_pairs(A): # count number of paths with no blocks n0 = D(w, h) # target number of excluded paths = (7/89) n0 nx = div(n0 * 7, 89) if nx is None: continue # block the diagonal path in one of the cells for (x, y) in cproduct([irange(divc(w, 2)), irange(h)]): # have we achieved the target? if D(x, y) * D(w - x - 1, h - y - 1) == nx: printf("{w} x {h} (area = {A}) -> {n0} paths; block @ ({x}, {y}) -> {n1} paths", n1 = n0 - nx) s += 1 if s: printf("[{s} solutions]") breakLikeLike