Sedersi al cinema

[dodo3]

Mi servirebbe una mano con questo problema del corso base per la preparazione alle Olimpiadi della Matematica.

Un gruppo di 10 amici deve sedersi su 10 sedili al cinema: a ogni persona sarebbe assegnato un posto, ma lo può occupare con un margine di +- 1 posto (es: se a Tizio è assegnato il posto n.4, può occupare il 3,4,5).
Trovare il numero di modi in cui i 10 amici possono disporsi.

[Luca Milanese]

Dovrebbe essere

Testo nascosto:

[math]89

Se mi confermi che è corretto, posto il procedimento.

[dodo3]

Si

[Luca Milanese]

Dimostro che la successione [math]a_n, che associa a [math]n posti a sedere e spettatori il numero di disposizioni possibili, si comporta come la successione di Fibonacci.
Osserviamo dapprima che [math]a_1=1 e [math]a_2=2. Dopodiché, per induzione, supponiamo che per [math]n-1 posti siano possibili [math]a_{n-1} disposizioni e che per [math]n posti se ne abbiano [math]a_n. Supponiamo di aggiungere l'[math]n+1esimo spettatore a destra della fila degli [math]n spettatori già presenti. Questo spettatore può occupare il posto [math]n o [math]n+1. Quando si trova al posto [math]n+1, sono possibili [math]a_n disposizioni (quelle che si ottengono facendo variare gli altri [math]n spettatori). Quando si trova al posto [math]n, necessariamente l'[math]nesimo spettatore si trova al posto [math]n+1, e allora sono possibili [math]a_{n-1} disposizioni (facendo variare gli altri [math]n-1 spettatori). Per [math]n+1 spettatori abbiamo dunque [math]a_{n+1}=a_n+a_{n-1}. Conoscendo [math]a_1 e [math]a_2, troviamo facilmente [math]a_{10} per somme successive.

[dodo3]

Grazie mille per la spiegazione. Una cosa però non mi è ancora chiara, ossia perché quando aggiungiamo l'(n+1)-esimo spettatore nel posto n, l'n-esimo spettatore deve spostarsi necessariamente nel posto n+1 e non in quello n-1

[dodo3]

Ah, dovrebbe essere perché se l'n-esimo spettatore si siede in n-1 e l'n+1-esimo in n, nessuno si potrebbe sedere in n+1, quindi alla fine qualcuno resterebbe in piedi.

[Luca Milanese]

Sì, esatto. Dato che il margine è di più o meno un posto, l'n+1 esimo posto può essere occupato solo dall'n esimo o dall'n+1 esimo spettatore.