Anagrammi

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?

Numero di percorsi per raggiungere ciascun incrocio

 

Oppure, numero di anagrammi di lunghezza 8 con 4 lettere E e 4 lettere N

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

2016-11-17 – 14

2016-14William abita molto vicino alla sua scuola.
Nella figura qui sopra, la casa di William è indicata con C e la sua scuola con S.
Il cammino minimo tra la casa e la scuola consiste in sette tratti, per esempio percorrendo il bordo esterno e poi scendendo fino alla scuola.

Ci sono tanti cammini minimi (sono quelli ottenibili andando, a ogni mossa, a destra oppure in basso).
Quanti sono?

19 | 17 | 15 | 18

Soluzione 1

I cammini disponibili da C a S sono

2016-14-1 2016-14-2 2016-14-3 2016-14-4 2016-14-5 2016-14-6 2016-14-7 2016-14-8 2016-14-9 2016-14-10 2016-14-11 2016-14-12 2016-14-13 2016-14-14  2016-14-15 2016-14-16 2016-14-17

Soluzione 2

Il numero di cammini per raggiungere ciascun incrocio è il seguente

 

Soluzione 3

Considera la mappa comprensiva dell’incrocio mancante

Siano B=Basso e D=Destra le direzioni disponibili

Tutti i cammini da C a S  programmabili con 3 B e 4 D sono \frac{7!}{4!3!} = 35

BBBDDDD, BBDBDDD, BBDDBDD, BBDDDBD, BBDDDDB, BDBBDDD, BDBDBDD, BDBDDBD, BDBDDDB, BDDBBDD, BDDBDBD, BDDBDDB, BDDDBBD, BDDDBDB, BDDDDBB, DBBBDDD, DBBDBDD, DBBDDBD, DBBDDDB, DBDBBDD, DBDBDBD, DBDBDDB, DBDDBBD, DBDDBDB, DBDDDBB, DDBBBDD, DDBBDBD, DDBBDDB, DDBDBBD, DDBDBDB, DDBDDBB, DDDBBBD, DDDBBDB, DDDBDBB, DDDDBBB

Osserva: i cammini da C all’incrocio mancante (con 2 B e 2 D) sono \frac{4!}{2!2!} = 6

BBDD, BDDB, BDBD, DBBD, DBDB, DDBB

Osserva: i cammini dall’incrocio mancante a S (con 1 B e 2 D) sono \frac{3!}{2!1!} = 3

BDD, DBD, DDB

I cammini da C a S che passano per l’incrocio mancante sono \frac{4!}{2!2!}\cdot \frac{3!}{2!1!}=6 \cdot 3 = 18

BBDDBDD, BBDDDBD, BBDDDDB, BDBDBDD, BDBDDBD, BDBDDDB, BDDBBDD, BDDBDBD, BDDBDDB, DBBDBDD, DBBDDBD, DBBDDDB, DBDBBDD, DBDBDBD, DBDBDDB, DDBBBDD, DDBBDBD, DDBBDDB

I cammini disponibili da C a S sono \frac{7!}{4!3!} – \frac{4!}{2!2!}\cdot \frac{3!}{2!1!} = 35-18 = 17

BBBDDDD, BBDBDDD, BDBBDDD, BDDDBBD, BDDDBDB, BDDDDBB, DBBBDDD, DBDDBBD, DBDDBDB, DBDDDBB, DDBDBBD, DDBDBDB, DDBDDBB, DDDBBBD, DDDBBDB, DDDBDBB, DDDDBBB