Percorsi

[gio73]

Questo l'ho trovato in un contest americano, non ho la soluzione, se qualcuno ci riesce mi interessa il ragionamento





bisogna andare da A a U, si hanno a disposizione 10 passi (5 orizzontali e 5 verticali, nn si torna indietro)
quanti sono i possibili percorsi?

[axpgn]

Dovrebbero essere $42$ i percorsi diversi da $A$ a $U$

Cordialmente, Alex

[gio73]

Mi interessa il ragionamento

[ghira1]

Cominci alla fine con "1" su U.

Poi vai verso l'inizio e su ogni incrocio scrivi la somma degli eventuali numeri sopra e a destra.

Ottieni:

				1
		1	1
2	2	1			5
3	1		14	14	9
1	42	42	28	14	5

[axpgn]

gio73

In questa tipologia di quesito, il metodo che conosco è questo: ad ogni punto (A, B, C, ecc.) devi sommare i "numeri" dei punti precedenti che portano a quel nodo, per esempio $P=Q+J$.
Se non ricordo male ...

Cordialmente, Alex

P.S.: Metto sotto spoiler perché magari qualcuno vuole divertirsi

[Stillife]

Io ho ragionato così:

Mettendo da parte i percorsi più banali :

$A, B, C, D, E, F, K, L, M, N, U$

$A, B, G, H, R, Q, S, O, T, N, U$

Restano da vedere i percorsi che partono da $C$ e da $E$. Quelli da $E$ saranno meno numerosi quindi considero prima questi.

In particolare prendo come riferimento i percorsi da $E$ a $U$ che passano per i punti $J, P, O, T.$
Questi saranno $4$, poichè non possiamo nè andare indietro nè passare per i punti $I, Q, S$ in quanto ciò esaurirebbe le mosse.

Partendo ora da $D$ e considerando i percorsi per $I, Q, S$ a $U$ avremo $3$ nuovi precorsi che si moltiplicheranno per quelli precedenti, dunque $3 * 4 = 12$.

Discorso analogo partendo da $C$. Avremo $2$ nuovi percorsi che si moltiplicheranno per precedenti, per cui $ 2*3*4=24$.

Sommando tutto avremo:

$1+1+4+3*4+2*3*4=42$