Sunday Times Teaser 2848 – Coffee Break

by Victor Bryant

Published April 23 2017 (link)

The roads on our estate form a grid consisting of three roads running west-to-east with a number of other roads running south-to-north from the bottom road across the middle road to the top road. I live at the south-west corner of the grid and I work at the north-east corner. Each day I walk to work by one of the various shortest possible routes along the roads: there is a two-figure number of such routes. One quarter of my possible routes pass Caffee Claudius, and one quarter of my routes pass Spenda Coffee (which are on different roads).

How many of my routes pass both the coffee shops?

2 Comments Leave one →

Brian Gladman permalink

If we have a rectangular grid of size \(m\) by \(n\) (with \(m+1\) and \(n+1\) roads), to move from the lower left to the upper right point by a shortest path we will always have to travel \(m\) units in one direction and \(n\) units in the other, the order in which we make these steps being immaterial. Hence in \(m+n\) steps we can choose \(m\) positions for the steps in the \(m\) direction, giving: \[\frac{(m+n)!}{m! n!}\] different shortest paths.

When \(m\) is two we hence find \((n+1)(n+2)/2\) shortest paths, which we are told gives a two digits result, giving \(3<=n<=12\). When divided by 4, only two \(m\) values, 6 and 7, give integer results so the number of north-south roads is either 7 or 8 and we are looking for coffee shop locations that lie on either 7 or 9 shortest paths.

If a coffee shop lies on the leftmost north-south road, but south of the middle east-west road, then the path to the end point can go along any of the upper halves of the north-south roads. Hence, if there are 7 north south roads, there are seven shortest paths running past this coffee shop. The same is also true if a coffee shop lies on the rightmost north-south road but north of the middle east-west road. However, a seven wide grid with eight north-south roads has no points through which there are nine shortest paths.

Hence we know that there are seven north-south roads and where the two coffee shops lie so we can see immediately that there is only one shortest path that passes both of them.

However, there is an ambiguity in this teaser in the handling of shops at intersections. Consider, for example, the two statements ‘the shops are on the same road’ and ‘the shops are on different roads’ for shops located on the same east-west road but different north-south roads. Since both statements are true, the constraint that the shops are on different roads can be interpreted as being met since this is true in one direction even though it is not true in the other. Fortunately the ‘two digit’ limit on the number of shortest paths eliminates this ambiguity since there are no solutions within this range but, without it, there would be additional solutions as shown below.

For a rectangular grid of roads from the point (0, 0) to point (2, n), there are \((n+1)(n+2)/2\) shortest paths between points (0, 0) and (2, n). For a shop at point (1, s), there are \((s+1)\) shortest paths to it from (0, 0) and \((n-s+1)\) from it to (2, n), which gives \((s+1)(n-s+1)\) shortest paths in total through this point. So we have: \[(s+1)(n-s+1) = (1/4)(n+1)(n+2)/2\] which can be manipulated to give: \[(2n+5)^2 – 2(4s-2n)^2 = 1\] which is a quadratic Diophantine equation that can be solved using my number theory library. If the point (1, s) gives a solution then the point (1, n – s) also gives a solution, there being only one shortest path between these two points. But there are \((s+1)\) paths from both (0, 0) to (1, s) and from (1, s) to (2, n) giving \((s+1)^2\) shortest paths that pass through both points.


from number_theory import Qde

print('Grid Width    Coffee Shops Shortest Paths')

for x, y in Qde(2, 1).solve(limit=10):
  if x <= 5:
    continue
  # compute the resulting n and s values 
  n, r1 = divmod(x - 5, 2)
  s, r2 = divmod(y + 2 * n, 4)
  if r1 or r2:
    continue
  s = min(s, n - s)
  print(f'{n:>10} {s:7} {n-s:7} {(s + 1) ** 2:>14}')

from number_theory import Qde

print('Grid Width Coffee Shops Shortest Paths')

for x, y in Qde(2, 1).solve(limit=10):

if x <= 5:

continue

# compute the resulting n and s values

n, r1 = divmod(x - 5, 2)

s, r2 = divmod(y + 2 * n, 4)

if r1 or r2:

continue

s = min(s, n - s)

print(f'{n:>10} {s:7} {n-s:7} {(s + 1) ** 2:>14}')

This show that a 2 x 47 grid (with 48 north-south roads) has a solution with coffee shops on the middle east-west road at sixth and forty-first intersections (counting from 0). There are a total of 1176 shortest paths, each shop is on 294 of them and 49 shortest paths pass both of them.

Here is a program that can be used to investigate solutions for other grid sizes and other positions of the two shops:


from itertools import combinations, combinations_with_replacement, product
from collections import defaultdict
from math import factorial

# the maximum dimension of the grid of roads to be considered
max_d = 100

# the fraction of the total number of shortest paths from (0, 0)
# to (m, n) that pass through intermediate points (either those
# at intersections and/or those between intersections)
ratio = (1, 4)

# points can be at junctions (JN), or on N-S (NS) or E-W (EW) road
# segments betwwen junctions - set MODE by combining the following
# values to specify which types of points to be considered 
#
#   NS   points on North-South roads between intersections
#   EW   points on East-West roads between intersections
#   JN   points at road intersections

NS, EW, JN = 1, 2, 4 
MODE = NS | EW | JN

# The number of shortest paths between points (0, 0) and (x, y) 
ncr = lambda x, y : factorial(x + y) // (factorial(x) * factorial(y))

# consider a grid (0, 0) to (m, n) with n >= m
for m, n in combinations_with_replacement(range(1, max_d), 2):
  # the number of shortest paths between (0, 0) and (m, n)
  mn = ncr(m, n)
  # compute the target number of paths at intermediate points
  trs, r = divmod(mn * ratio[0], ratio[1])
  lrs = []
  if not r:
    if MODE & JN:
      # the number of shortest paths through the junction (r, s)
      for r, s in product(range(m + 1), range(n + 1)):
        if ncr(r, s) * ncr(m - r, n - s) == trs:
          lrs.append((r, s, 'JN'))   
    if MODE & NS:
      # the number of shortest paths through the road north of (r, s)
      for r, s in product(range(m), range(n + 1)):
        if ncr(r, s) * ncr(m - r - 1, n - s) == trs:
          lrs.append((r, s, 'NS'))   
    if MODE & EW:
      # the number of shortest paths through the road east of (r, s)
      for r, s in product(range(m + 1), range(n)):
        if ncr(r, s) * ncr(m - r, n - s - 1) == trs:
          lrs.append((r, s, 'EW'))

    # now consider all pairs of locations
    for (r, s, t), (u, v, w) in combinations(lrs, 2):
      # the number of shortest paths from (0, 0) to (r, s), the intersection if
      # on one or to the intersection south or west of the point otherwise 
      np = ncr(r, s)
      # the number of shortest paths from the (r, s) intersection if on one or
      # from the intersection north or east of the point otherwise to the (u, v)
      # intersection if on one or to that south or west of the point if not       
      pr, ps = (r, s) if t == 'JN' else (r + 1, s) if t == 'NS' else (r, s + 1)
      if not (pr <= u and ps <= v):
        continue
      np *= ncr(u - pr, v - ps)
      # the number of shortest paths from the (u, v) intersection if on one or
      # from the intersection north or east of the point otherwise to the (m, n)
      # intersection
      pu, pv = (u, v) if w == 'JN' else (u + 1, v) if w == 'NS' else (u, v + 1)       
      np *= ncr(m - pu, n - pv)
      print((r, s, t), (u, v, w), (m, n), mn, np)

from itertools import combinations, combinations_with_replacement, product

from collections import defaultdict

from math import factorial

# the maximum dimension of the grid of roads to be considered

max_d = 100

# the fraction of the total number of shortest paths from (0, 0)

# to (m, n) that pass through intermediate points (either those

# at intersections and/or those between intersections)

ratio = (1, 4)

# points can be at junctions (JN), or on N-S (NS) or E-W (EW) road

# segments betwwen junctions - set MODE by combining the following

# values to specify which types of points to be considered

# NS points on North-South roads between intersections

# EW points on East-West roads between intersections

# JN points at road intersections

NS, EW, JN = 1, 2, 4

MODE = NS | EW | JN

# The number of shortest paths between points (0, 0) and (x, y)

ncr = lambda x, y : factorial(x + y) // (factorial(x) * factorial(y))

# consider a grid (0, 0) to (m, n) with n >= m

for m, n in combinations_with_replacement(range(1, max_d), 2):

# the number of shortest paths between (0, 0) and (m, n)

mn = ncr(m, n)

# compute the target number of paths at intermediate points

trs, r = divmod(mn * ratio[0], ratio[1])

lrs = []

if not r:

if MODE & JN:

# the number of shortest paths through the junction (r, s)

for r, s in product(range(m + 1), range(n + 1)):

if ncr(r, s) * ncr(m - r, n - s) == trs:

lrs.append((r, s, 'JN'))

if MODE & NS:

# the number of shortest paths through the road north of (r, s)

for r, s in product(range(m), range(n + 1)):

if ncr(r, s) * ncr(m - r - 1, n - s) == trs:

lrs.append((r, s, 'NS'))

if MODE & EW:

# the number of shortest paths through the road east of (r, s)

for r, s in product(range(m + 1), range(n)):

if ncr(r, s) * ncr(m - r, n - s - 1) == trs:

lrs.append((r, s, 'EW'))

# now consider all pairs of locations

for (r, s, t), (u, v, w) in combinations(lrs, 2):

# the number of shortest paths from (0, 0) to (r, s), the intersection if

# on one or to the intersection south or west of the point otherwise

np = ncr(r, s)

# the number of shortest paths from the (r, s) intersection if on one or

# from the intersection north or east of the point otherwise to the (u, v)

# intersection if on one or to that south or west of the point if not

pr, ps = (r, s) if t == 'JN' else (r + 1, s) if t == 'NS' else (r, s + 1)

if not (pr <= u and ps <= v):

continue

np *= ncr(u - pr, v - ps)

# the number of shortest paths from the (u, v) intersection if on one or

# from the intersection north or east of the point otherwise to the (m, n)

# intersection

pu, pv = (u, v) if w == 'JN' else (u + 1, v) if w == 'NS' else (u, v + 1)

np *= ncr(m - pu, n - pv)

print((r, s, t), (u, v, w), (m, n), mn, np)

Jim Randell permalink

This Python 3 program constructively generates the possible paths in a grid, and then looks for segments of the paths that appear in exactly one quarter of a possible paths. We then select two of these segments for the positions of the coffee shops and count how many paths include both the segments.


from itertools import count, combinations
from collections import Counter
from enigma import tuples, contains, printf

# generate paths from (0, 0) to (x, y)
def paths(x, y, s=[]):
  if x == y == 0:
    yield [(0, 0)] + s
  else:
    if x > 0: yield from paths(x - 1, y, [(x, y)] + s)
    if y > 0: yield from paths(x, y - 1, [(x, y)] + s)

y = 2
for x in count(1):

  # the total number of different routes
  # or: t = C(x + y, y)
  ps = list(paths(x, y))
  t = len(ps)
  if t < 10: continue
  if t > 99: break

  (q, r) = divmod(t, 4)
  if r != 0: continue

  printf("[x={x} y={y}] t={t}, q={q}")

  # count the number of paths that use each line segments on the grid
  #ps = list(paths(x, y))
  segs = Counter()
  for p in ps:
    segs.update(tuples(p, 2))

  # find segments that appear q times
  qs = list(k for (k, v) in segs.items() if v == q)
  printf("  qs={qs}")

  # choose two of them
  for (q1, q2) in combinations(qs, 2):
    # and count the paths that include both segments
    n = sum((contains(p, q1) != -1 and contains(p, q2) != -1) for p in ps)
    printf("  n={n} [q1={q1} q2={q2}] (*** SOLUTION ***)")

from itertools import count, combinations

from collections import Counter

from enigma import tuples, contains, printf

# generate paths from (0, 0) to (x, y)

def paths(x, y, s=[]):

if x == y == 0:

yield [(0, 0)] + s

else:

if x > 0: yield from paths(x - 1, y, [(x, y)] + s)

if y > 0: yield from paths(x, y - 1, [(x, y)] + s)

y = 2

for x in count(1):

# the total number of different routes

# or: t = C(x + y, y)

ps = list(paths(x, y))

t = len(ps)

if t < 10: continue

if t > 99: break

(q, r) = divmod(t, 4)

if r != 0: continue

printf("[x={x} y={y}] t={t}, q={q}")

# count the number of paths that use each line segments on the grid

#ps = list(paths(x, y))

segs = Counter()

for p in ps:

segs.update(tuples(p, 2))

# find segments that appear q times

qs = list(k for (k, v) in segs.items() if v == q)

printf(" qs={qs}")

# choose two of them

for (q1, q2) in combinations(qs, 2):

# and count the paths that include both segments

n = sum((contains(p, q1) != -1 and contains(p, q2) != -1) for p in ps)

printf(" n={n} [q1={q1} q2={q2}] (*** SOLUTION ***)")

The program uses some useful routines from the enigma.py library. The tuples() function to get the line segments out of a path (represented as a list of points), and the (recently added) contains() function to check if a line segment appears in a path.

The latest version of the enigma.py library is available at [ https://www.magwag.plus.com/jim/enigma.html ].

Sunday Times Teaser 2848 – Coffee Break

by Victor Bryant

Published April 23 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta