## Teaser 2961: Alan and Cat

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

[teaser2961]

## Jim Randell 12:20 pm

on21 June 2019 Permalink |We have encountered problems similar to this before, see:

Enigma 1108.The puzzle can be solved using

Catalan’s Triangle[ link ], hence the names Cat and Alan.This Python program counts the paths constructively. It runs in 95ms.

Run:[ @repl.it ]Solution:The date of the first repeat was 6th March 2019.Instead of counting the paths we can use the formula for Catalan numbers:

LikeLike