1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
rom datetime import date, timedelta from functools import lru_cache from itertools import count # count the paths from (0, 0) to (s, a) where s >= a @lru_cache(None) def routes(s, a): return 0 if s < a else 1 if not a else routes(s, a - 1) + routes(s - 1, a) # the number of Alan's intersection for n in count(1): # the number of different paths from (1, 1) to (n, n) w = routes(n, n) # date at which all the paths have been used now = date(2018, 1, 1) + timedelta(w) # stop if at or after the teaser publication date if now >= date(2019, 6, 23): break # look for a date in 2019 if now >= date(2019, 1, 1): ds = now.strftime('%a %d %B %Y') print(f"All {w} different routes from (1, 1) to {(n, n)} used before {ds}.") |

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)!}\]

]]>