[A-L] (20 Giugno 2024) Esercizio 1

[FeddyLix17]

Gli archi nella figura rappresentano i corridoi di una casa.

L’ingresso è nel vertice superiore e si possono percorrere i corridoi solo dall’alto verso il basso.

I vertici in basso contrassegnati da lettere sono le porte di uscita. A ogni incrocio si può scegliere se muoversi a destra o a sinistra.

1. Quanti sono i percorsi dall’ingresso a una delle porte di uscita? [1.5 punti]

2. Quanti percorsi dall’ingresso a una porta contengono esattamente due mosse a sinistra? [1.5 punti]

3. Quanti percorsi dall’ingresso a una porta contengono almeno due mosse a sinistra? [2 punti]

[FeddyLix17]

1. Partendo dal vertice su superiore si avrà una sola biforcazione, e di conseguenza 2 possibili percorsi tra cui scegliere.

   Per ogni scelta presa, ci si ritroverà nuovamente davanti a una biforcazione (quindi i percorsi possibili diventeranno 4, 8, e cosi via fino ad arrivare al "livello delle porte di uscita", che, contrassegnando quello del vertice superiore come il primo, sarà il quinto)

$$ \Large \prod_{k=1}^{5} 2 = 2^k = 2^5 = 32 $$

---

2. Considerando ogni percorso come una sequenza binaria di lunghezza 5 $\Large X_1X_2X_3X_4X_5$, dove $\Large X \in \{0, 1 \}$, con 0 = mossa a sinistra

   e 1 = mossa a destra, $\Large \binom{5}{2}$ saranno i percorsi contententi esattamente due mosse a sinistra ($\Large \binom{5}{2}$ rappresenta il numero di modi

   possibili di scegliere 2 mosse a sinistra nelle 5 della sequenza, impostando a destra tutte le altre)

$$ \Large \binom{5}{2} = \frac{5!}{2!(5-2)!} = \frac{5!}{2!3!} = \frac{5 * 4}{2!} = 5 * 2 = 10 $$

---

3. Dato il numero totale di percorsi, bisognerà sottrarci il numero di percorsi in cui la mossa a destra compare esattamente 4 o 5 volte

   (cosi da avere il numero di percorsi in cui la mossa a sinistra compare al più 2 o 3 o 4 o 5 volte)

$$ \Large 32 - (\binom{5}{4} +\binom{5}{5}) = 32 - (\binom{5}{5 - 4} +1) = 32 - (\binom{5}{1} +1) = 32 - 6 = 26 $$

di fatto

$$ \Large \binom{5}{2} +\binom{5}{3} + \binom{5}{4} +\binom{5}{5} = 10 + 10 + 5 + 1 = 26 $$