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


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


Il numero di cammini per raggiungere ciascun incrocio è il seguente

 


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