La matematica in gioco: Reticoli euleriani

In una serie dedicata a Eulero non poteva mancare un articolo dedicato ai reticoli (o cammini) euleriani. Prima di addentrarci nei labirintici percorsi euleriani, vi ricordo che è da pochi giorni on line il 15.mo Carnevale della Matematica: i nostri Rudi amici si occupano, tra le altre cose, del gioco del 15, un particolare quadrato magico ideato nel 1874 dal postino Noyes Palmer Chapman e diffuso nel 1880 da Samuel Loyd.
Torniamo, però, a noi.
Tutto inizia con il problema dei ponti di Königsberg: in questo famoso problema, il solutore deve cercare di trovare l'eventuale percorso che consenta di attraversare ogni ponte una e una sola volta e tornare, alla fine, al punto di partenza. Non solo Eulero determinò che non esisteva alcun percorso di questo genere, ma diede di fatto il via alla teoria dei grafi. In particolare si possono fornire una serie di definizioni che possono aiutare a determinare se un reticolo è euleriano o meno, ma che possono anche aiutare a seguire meglio il ragionamento per la risoluzione del 15.mo problema del Project Euler.
Iniziamo con il definire i nodi:

nodo pari: punto in cui converge un numero pari di archi;
nodo dispari: punto in cui converge un numero dispari di archi.

A questo punto possiamo definire:

Il reticolo contenente nodi pari o al più due nodi dispari è un reticolo euleriano.
Un reticolo euleriano è completamente percorribile e può essere disegnato senza mai staccare la penna dal foglio.

Il problema n.15 del Project ricorda molto da vicino i reticoli euleriani:

Una griglia 2x2 è percorribile attraverso 6 percorsi distinti. Quanti percorsi distinti esistono in una griglia 20x20?

Innanzitutto basta osservare che in tutti i percorsi possibili nel caso 2x2, gli spostamenti verso destra e quelli verso il basso (gli unici possibili partendo dal nodo in alto a sinistra fino a quello in basso a destra) sono in numero uguale (in particolare 2 e 2). Inoltre tutti i percorsi avranno lunghezza 4 = 2x2 e in generale lunghezza $2 \times n$, con $n$ lunghezza del lato. A questo punto il problema si riduce alla risposta alla seguente domanda:

Quanti sono i percorsi lunghi $2n$ costituiti da $n$ passi verso destra ed $n$ passi verso il basso?

La risposta ci viene dal cacolo combinatorio, e in particolare dal coefficiente binomiale, che permette di calcolare in quanti modi posso disporre un certo numero $a$ di oggetti raggruppati in insiemi di, ad esempio, $b$ elementi. \[{a \choose b} = \frac{a!}{(a-b)! b!}\] Nel caso dei nostri percorsi la formula verrà così modificata: \[{2n \choose n} = \frac{(2n)!}{n! n!}\] A questo punto non resta che applicare la formula nel caso $n=20$, che è il nostro, e vedere l'effetto che fa!

---

P.S.: la soluzione è tratta da A square grid path problem.