# Sunday Times Teaser 2961 – Alan and Cat

### by John Owen

#### Published June 23 2019 (link)

Alan and Cat live in a city which has a regular square grid of narrow roads. Avenues run west/east, with 1st Avenue being the furthest south, while Streets run south/north with 1st Street being the furthest west.

Cat lives at the intersection of 1st Street and 1st Avenue, while Alan lives at an intersection due northeast from Cat. On 1 January 2018, Cat walked to Alan’s house using one of the shortest possible routes (returning home the same way), and has done the same every day since. At first, she walked a different route every day and deliberately never reached an intersection where the Street number is less then the Avenue number. However, one day earlier this year she found that she could not do the same, and repeated a route.

What was the date then?

One Comment Leave one →
The number of paths for the routes from (1,1) to (n, n) is given by a sequence known as the Catalan numbers (see the The On-Line Encyclopedia of Integer Sequences). It has the terms:$C(n)=\frac{(2n)!}{n!(n+1)!}$