Sunday Times Teaser 3338 – Any Way But Back

by BRG on 13 September 2026

by Howard Williams

Published Sunday September 13 2026 (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.

What is the smallest number of obstacles that can be in the box?

From → Uncategorized

3 Comments Leave one →

BRG permalink


from functools import cache

# count the total number of paths from (0, 0) to (m, n) in a 
# rectangular grid when North, West and North-West directions
# of travel are allowed (see Delannoy numbers)
@cache
def paths(m, n):
  if m == 0 or n == 0:
    return 1
  return paths(m - 1, n) + paths(m, n - 1) + paths(m - 1, n - 1)

# consider a rectangular <m> by <n> grids
area, sols = 1, set()
while not sols:
  area += 1
  # consider rectangular grids with this area
  for n in range(1, area):
    m, r = divmod(area, n)
    if r:
      continue
    if n > m:
      break
    # count the number of paths with all tunnels open
    np = paths(m, n)  
    # check for an integer reduction in the total number 
    # of paths when one diagonal path is closed
    npt, r = divmod(7 * np, 89)
    if not r:
      # find the number of paths through a tunnel at (mc, nc)
      for mc in range(1, m):
        for nc in range(1, n):
          # is the target reduction achieved if this tunnel is closed?
          if paths(mc, nc) * paths(m - mc - 1, n - nc - 1) == npt:
            print(f" {m = }, {n = } {np} paths, {npt} less if closed @({mc}, {nc})")
            # store the number of obstacles
            sols.add(m * n)

for sol in sols:
  print(f"{sol} obstacles")

from functools import cache

# count the total number of paths from (0, 0) to (m, n) in a

# rectangular grid when North, West and North-West directions

# of travel are allowed (see Delannoy numbers)

@cache

def paths(m, n):

if m == 0 or n == 0:

return 1

return paths(m - 1, n) + paths(m, n - 1) + paths(m - 1, n - 1)

# consider a rectangular <m> by <n> grids

area, sols = 1, set()

while not sols:

area += 1

# consider rectangular grids with this area

for n in range(1, area):

m, r = divmod(area, n)

if r:

continue

if n > m:

break

# count the number of paths with all tunnels open

np = paths(m, n)

# check for an integer reduction in the total number

# of paths when one diagonal path is closed

npt, r = divmod(7 * np, 89)

if not r:

# find the number of paths through a tunnel at (mc, nc)

for mc in range(1, m):

for nc in range(1, n):

# is the target reduction achieved if this tunnel is closed?

if paths(mc, nc) * paths(m - mc - 1, n - nc - 1) == npt:

print(f" {m = }, {n = } {np} paths, {npt} less if closed @({mc}, {nc})")

# store the number of obstacles

sols.add(m * n)

for sol in sols:

print(f"{sol} obstacles")

Frits permalink

A mixture of Brian’s and Jim’s ideas.


from math import factorial as f
from functools import cache
 
# count the total number of paths from (0, 0) to (m, n) in a 
# rectangular grid when North, West and North-West directions
# of travel are allowed (see Delannoy numbers)
C = lambda m, n: f(m) // (f(n) * f(m - n))
@cache
def D(m, n):  
  return sum(C(m, k) * C(n, k) * 2**k for k in range(min(m, n) + 1))

# generate Delannoy numbers that are multiples of 89
def generate():
  for area, _ in enumerate(iter(bool, 1), 1): # infinite loop
    for a in range(1, int(area**.5) + 1):
      b, r = divmod(area, a)
      if r: continue
      if ((n := D(a, b)) % 89 == 0):
        yield (a, b, n, 7 * n // 89)

for m, n, np, nt in generate():
  # find the number of paths through the tunnel at (mc, nc)
  for mc in range(1, m):
    for nc in range(mc, n):
      # has the target reduction when this path is closed been met?
      if D(mc, nc) * D(m - mc - 1, n - nc - 1) == nt:
        # we don't need other solutions with the same area
        print(f"{m * n} obstacles")
        exit(0)

from math import factorial as f

from functools import cache

# count the total number of paths from (0, 0) to (m, n) in a

# rectangular grid when North, West and North-West directions

# of travel are allowed (see Delannoy numbers)

C = lambda m, n: f(m) // (f(n) * f(m - n))

@cache

def D(m, n):

return sum(C(m, k) * C(n, k) * 2**k for k in range(min(m, n) + 1))

# generate Delannoy numbers that are multiples of 89

def generate():

for area, _ in enumerate(iter(bool, 1), 1): # infinite loop

for a in range(1, int(area**.5) + 1):

b, r = divmod(area, a)

if r: continue

if ((n := D(a, b)) % 89 == 0):

yield (a, b, n, 7 * n // 89)

for m, n, np, nt in generate():

# find the number of paths through the tunnel at (mc, nc)

for mc in range(1, m):

for nc in range(mc, n):

# has the target reduction when this path is closed been met?

if D(mc, nc) * D(m - mc - 1, n - nc - 1) == nt:

# we don't need other solutions with the same area

print(f"{m * n} obstacles")

exit(0)

BRG permalink

I also tested your approach to computing D(m.n) but it didn’t make any difference to the speed on CPython. For reasons I don’t yet understand, your nc loop fails in my version.

Reply

Sunday Times Teaser 3338 – Any Way But Back

by Howard Williams

Published Sunday September 13 2026 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta