Sunday Times Teaser 2848 – Coffee Break

by Victor Bryant

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?

1. 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.

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:

2. 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.

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 ].