Percorsi sulla scacchiera

[giannirecanati]

In una scacchiera \(\displaystyle 8 × 8 \) le righe sono numerate da \(\displaystyle 1 \) a \(\displaystyle 8 \) e le colonne sono contrassegnate con le lettere che vanno dalla \(\displaystyle a \) alla \(\displaystyle h \). Una pulce, situata inizialmente nella casella \(\displaystyle b_2 \), si sposta saltando: i salti ammessi sono solo quelli tra due caselle adiacenti, cio`e due caselle distinte aventi un lato in comune. Determinare quanti sono i percorsi che portano la pulce dalla casella \(\displaystyle b_2 \) alla casella \(\displaystyle g_7 \) che sono composti esattamente da \(\displaystyle 12 \) salti e che non passano mai due volte per la stessa casella.

Purtroppo ho solo il risultato numerico e non il procedimento. Il problema comunque non l'ho risolto perché non riesco mai a considerare tutti i casi.

[xXStephXx]

Questo problema l'avevo visto tempo fa, viene dalla gara di Tor Vergata mi sembra.. I passi da seguire sono:

- Con quanti salti, al minimo, la pulce può arrivare a destinazione?
- Quanti sono i percorsi possibili se la pulce arrivasse a destinazione facendo il minimo di salti con cui la può raggiungere?
- Considerando che i salti che fa sono 12, quanti ne fa in più rispetto al minimo?
- In che modo la pulce può "perdere tempo" facendo salti in più rispetto al minimo?
- Considerando che non può passare due volte sulla stessa casella, ci sono dei salti obbligati da fare dopo che ha fatto il salto per "perdere tempo"?