Problema sul calcolo combinatorio

[FeDe9806]

Una pulce si trova nella casella in basso a sinistra di una scacchiera $ 8x8 $ e deve andare fino alla casella diagonalmente opposta , effettuando $ 16 $ salti tra caselle contigue (cioè aventi un lato in comune). Quanti sono i diversi percorsi che può fare?

Con $ 14 $ salti l'avrei saputo fare ma con $ 16 $ non so proprio come metterci mano.

[Crispolto]

Il risultato è nelle risposte della prima lezione del mitico corso di base per le olimpiadi della matematica
http://www.problemisvolti.it/CorsoBaseO ... atica.html

Hint 1:

Dopo aver effettuato 7 salti a destra e 7 in alto, quante possibilità ci sono per arrivare a 16 salti?

Hint 2:

I casi sono due, a sinistra e poi di nuovo a destra oppure in basso e poi di nuovo in alto. Si può analizzare solo un caso, per esempio solo il salto a sinistra e poi raddoppiare il numero ottenuto. Quanti modi ci sono per intramezzare un salto a sinistra e uno a destra nel percorso di 7 salti a destra e 7 in alto?

Hint 3:

Siano DDDDDDDD gli otto salti da compiere, posso inserire il salto a sinistra S in 7 posti diversi. A questo punto considero D e S come un movimento generico e conto quanti sono i modi di ordinare 9 movimenti M e 7 spostamenti in alto A.

[FeDe9806]

GRAZIE MILLE! Pero ora ho ancora un dubbio. Dove spieghi "Siano DDDDDDDD gli otto salti da compiere, posso inserire il salto a sinistra S in 7 posti diversi" perchè 7 posti diversi? Non potrebbero essere 14 ovvero il salto sinistra destra non si può intramezzare ad ogni salto che ha compiuto?

[Crispolto]

I vincoli che vanno rispettati sono che prima del salto a sinistra ci sia almeno un salto a destra e dopo il salto a sinistra ci deve essere almeno un salto a destra, mentre sui salti in alto non ci sono vincoli e quindi li conto dopo che ho contato i modi in cui posso costruire un percorso di soli salti a destra e sinistra, che sono appunto 7: DSDDDDDDD, DDSDDDDDD, ..., DDDDDDDSD.
Quando devo contare in quanti modi posso aggiungere i salti in alto non mi interessa più distinguere fra salti a destra e sinistra, quindi conto quante stringhe MMMMMMMMAAAAAAA posso costruire, dove con M indico un salto in orizzontale che può essere D o S. Quindi il numero di percorsi con un salto a sinistra sarà 7 * (9 + 7)! / (9! * 7!).

[FeDe9806]

OK GRAZIE MILLE DI NUOVO!! Ora è tutto più chiaro!!