John wishes to walk …

Olimpiadi di Problem Solving

John wishes to walk from corner A to corner B through streets as in the following street map.
A route from A to B is a combination only of northward segments and eastward segments; an example is shown in bold on the map ([N,E,E,N,N,N,E,E]).
Note that at any corner John has only two choices; actually he can neither go backward, nor increase the distance from destination.

How many routes are there from A to B available to John?

Soluzione 1

Numero di percorsi per raggiungere ciascun incrocio

Soluzione 2

Numero di percorsi come numero di anagrammi di lunghezza 8 con 4 lettere E e 4 lettere N

$\frac{8!}{4!4!}=70$

Soluzione 3

Con i coefficienti binomiali, numero di posizioni ordinate per 4 passi in direzioni Est su 8 passi

$\displaystyle {8 \choose 4}$ = …