## Teaser 2848: Coffee breaks

**From The Sunday Times, 23rd April 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?

[teaser2848]

## Jim Randell 8:47 am

on24 September 2019 Permalink |I considered coffee shops that are located somewhere on the roads between the intersection points of the grid. (If we consider coffee shops at the intersections there are no solutions where the two shops are not on the same road).

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. It runs in 76ms.

Run:[ @repl.it ]Solution:Only one route passes both coffee shops.There are 7 N-S roads.

(The coffee shops are indicated by stars. The single route is shown in red).

The number of routes on an

xbyygrid is given by:C(x + y, x), orC(x + y, y).In this case

y = 2, soxmust be in the the range 3 … 12 in order for the number of routes to be a 2-digit number.For the number of routes to be exactly divisible by 4 we must have

x = 6 or 7.If

x = 7the number of routes is 36, and there are no segments that are used in exactly 36/4 = 9 shortest routes.If

x = 6the number of routes is 28, and only the two vertical segments shown in red on the diagram have 28/4 = 7 shortest routes using them. So these give the locations of the coffee shops, and there is only one shortest route that uses both of them together.If we require the coffee shops to be at intersections, then we find the only possible positions are shops at (0, 1) and (6, 1), but these both lie on the

y = 1road, so does not provide a viable solution. Although potentially it does allow a solution where one of the coffee shops is at one of these intersections, and the other one is on a segment between intersections, but it doesn’t change the answer to the puzzle.The restriction on there being a 2-digit number of shortest paths limits the range of

xto a small number of values, but even without this restriction I didn’t find any further candidate solutions (with segments lying on one quarter of the total number of paths) forxup to 5000.However there are further candidate locations if the coffee shops are allowed on the intersections. For example with

x = 47we could have shops at (6, 1), (41, 1), and withx = 286we could have shops at (41, 1), (245, 1), and withx = 1679we could have shops at (245, 1), (1434, 1). However when choosing 2 shops these all fall foul of the condition that that the shops be on different roads, so don’t provide viable solutions.LikeLike

## Jim Randell 4:49 pm

on24 September 2019 Permalink |Here is a modified version of the program that allows the coffee shops to be on the segments between intersections or at the intersections themselves. Instead of constructing the paths it uses the formula

C(x + y, x)to count the number of paths. The answer to the puzzle is the same, however.Run:[ @repl.it ]One shop is on the line (0, 0) – (0, 1) and the other is on the line (6, 1) – (6, 2), all locations are acceptable apart from (0, 1) together with (6, 1), as then the shops are both on the

y = 1road.LikeLike