Ho fatto un po' di conti, a me risulta 21905
Io ho ragionato così:
Dato un reticolo n x m, i percorsi minimi (da un vertice a quello opposto) sono quelli che hanno lunghezza pari al semiperimetro del reticolo (n+m)
Questi percorsi sono caratterizzati da una sequenza alternata di svolte a destra e a sinistra in quanto due svolte consecutive nella stessa direzione producono un percorso più lungo del minimo.
Il numero di questi percorsi è dato dalla formula
$P(m,n)=\prod_{k=1}^{m}\frac{n-k}{k}$ (ricavata sperimentalmente)
Ad esempio un reticolo 2x2 ha 6 percorsi minimi (qui in una spartana visualizzazione testuale)
Codice: Seleziona tutto
_ _ _ _ _ _
|_|_| | |_ | |_ _ |_ |
|_|_| | | |_ | |_ |_ _
Consideriamo quindi un reticolo quadrato n x n e analizziamo le interruzioni, indichiamo con M il nodo a monte (quello più vicino al punto di partenza A) e con V il nodo a valle (quello più vicino al punto di arrivo B)
Il punto M delimita un reticolo p x q (rispetto ad A) che ha P(p,q) percorsi minimi (questo è il numero di percorsi che permettono di raggiungere il punto M partendo da A).
Il punto V delimita un reticolo s x t (rispetto a B) che ha P(s,t) percorsi minimi (questo è il numero di percorsi che partono da punto V verso B).
Pertanto ci sono P(p,q) x P(s,t) percorsi che transitano per il tratto interrotto. Questo è il numero da sottrarre al totale dei percorsi possibili.
Se ci sono più interruzioni queste vanno analizzate e conteggiate separatamente considerando quanto segue:
- se ci sono interruzioni a nel reticolo a valle queste sono ininfluenti in quanto a valle dell'interruzione i percorsi sono comunque tutti non percorribili
- se ci sono interruzioni nel reticolo a monte queste vanno considerate per stabilire quanti sono i percorsi effettivamente percorribili prima dell'interruzione in esame.
Ora veniamo al problema:
Un reticolo 9x9 ha 48620 percorsi minimi.
La prima interruzione si trova in riga 1 colonna 2 (partendo da 0)
A monte c'è un reticolo 2x1 con 3 percorsi minimi, mentre a valle c'è un reticolo 7x7 con 3432 percorsi minimi, quindi devo detrarre 3 x 3432 = 10296 percorsi
La seconda si trova in {2,4} a monte c'è un reticolo 4x2 che contiene un'interruzione che riduce i percorsi da 15 a 12, mentre a valle c'è un reticolo 6x5 con 462 percorsi, totale 12 x 462 = 5544
La terza si trova in {4,6} a monte c'è un reticolo 6x4 (210 percorsi) con 2 interruzioni che sottraggono rispettivamente 3 x 15 = 45 e 3 x 12 = 36 percorsi. A valle c'è un reticolo 4x3 (35 percorsi), totale 129 x 35 = 4515
La quarta si trova a {5,8} a monte c'è un reticolo 8x5 (1287 percorsi) con 3 interruzioni, a valle c'è un reticolo 3x1 (4 percorsi) totale 561 x 4 = 2244
L'ultima si trova in {7,6} a monte c'è un reticolo 7x6 (1716 percorsi) con 3 interruzioni, a valle c'è un reticolo 3x1 (4 percorsi) totale 1029 x 4 = 4116
48620 - 10296 - 5544 - 4515 - 2244 - 4116 = 21905
Sempre se non ho sbagliato i calcoli.
EDIT: Ora che ci penso 22mila giorni sono circa 60 anni, non credo che il "vecchio" professor Smith (che è già in pensione) ce la farà a ricominciare il giro.
