Categorie: Matematica
Tags: combinazioni niente computer quiz trespoli da bar
Scritto da: Vincenzo Zappalà
Commenti:8
Distanziamento sociale **/***
Il distanziamento sociale può essere anche utile per proporre qualche quiz dai risvolti molto interessanti e generali.
Siamo in un bar all'americana, con i trespoli (io chiamo così quegli sgabelli rotondi e molto alti) davanti al bancone, dove servono birra e super alcolici vari. Ovviamente, la libagione è libera, ma bisogna mantenere le distanze e, quindi, non possono mai sedersi due persone su due trespoli affiancati: ce ne vuole sempre almeno uno libero tra di loro.
Nel nostro caso particolare (che possiamo facilmente generalizzare) ci sono dieci trespoli, come nella figura che segue.
La domanda è:
Quante combinazioni possibili esistono?
Voglio chiarire che nelle combinazioni possibili sono comprese anche quelle in cui ci sono meno avventori della massima capienza davanti al bancone; in altre parole è anche da contare la combinazione di tutte le sedie vuote.
Qui termina il quiz da due asterischi.
Ai più bravi chiedo anche: è possibile calcolare immediatamente il risultato senza fare troppi conti? Ossia, esiste una formula ricorrente che dipenda solo dal numero n di sedie?
Ricordiamoci che il numero finale deve essere, ovviamente, un numero intero!
N.B.: è SEMPRE escluso il computer e/o programmini vari.
QUI la soluzione (ma anche nei commenti)
8 commenti
Se non ho interpretato male:
parto dal caso con soli 2 trespoli, numerandoli con 1 e 2,
2 trespoli vuoti → 1 combinazione
2 trespoli occupati alternativamente dall’avventore A:
A1+A2 → 2 combinazioni,
totale 1+2=3
3 trespoli vuoti → 1 combinazione
3 trespoli occupati alternativamente dall’avventore A:
A1+A2+A3 → 3 combinazioni
2 trespoli occupati da 2 avventori contemporaneamente:
A1, A3 → 1 combinazione,
totale 1+3+1=5
4 trespoli vuoti → 1 combinazione
4 trespoli occupati alternativamente dall’avventore A:
A1+A2+A3+A4 → 4 combinazioni
2 trespoli occupati da 2 avventori contemporaneamente:
A1, A3 → 1 combinazione
A2, A4 → 1 combinazione
A1, A4 → 1 combinazione
totale 1+4+1+1+1=8
Ho provato anche con 5 trespoli (max 3 avventori contemporaneamente) e ho trovato 13 combinazioni.
Ho cercato quale potrebbe essere l’algoritmo che rappresenta il numero di combinazione possibili e ho trovato che, perlomeno fino a 5,
quello che funziona è:
(n k) + k,
dove (n k) = n! / (k!(n – k)!)
con n numero di trespoli e k numero massimo consentito, contemporaneamente, di avventori,
ottenuto come n / 2 se n è pari, e l’intero di n / 2 + 1 se n è dispari.
Quindi, se è questo l’algoritmo, per n = 10, k = 5
10*9*8*7*6*5*4*3*2 / ( (5*4*3*2)(5*4*3*2) + 5 = 30240 / 120 + 5 = 257
Se conto nelle combinazioni anche quelle vuote, mi viene una serie di Fibonacci che parte da 2.
Effettivamente da 6 in avanti, l'algoritmo che avevo ipotizzato non va bene.
Probabilmente sbaglio io, ma per n=6 ho trovato 19 combinazioni.
Supponiamo che le sedie siano s+2 (12 nel nostro caso) di cui la prima e l'ultima virtuali sempre vuote.
Se una persona si siede divide il gruppo di sedie in due insiemi di sedie vuote.
Se due persone si siedono dividono il gruppo di sedie in tre insiemi di sedie vuote.
p è il numero di persone.
In generale ci saranno p+1 insiemi di sedie vuote, ossia p persone individuano p+1 blocchi di sedie vuote.
il numero di sedie vuote sarà sempre uguale al nr di sedie totali meno il numero di sedie occupate.
Per identificare il numero di combinazioni possibili è necessario sapere in quanti modi p persone possono
inserirsi in un gruppo di s+2-p sedie vuote.
Il numero di interstizi, occupato da una sola persona, così individuato è s+2-p -1= s-p +1 .
A questo punto basta calcolare il numero di modi in cui p persone occupano s-p+1 interstizi.
Il numero è il coefficiente binomiale a si dimostra essere uguale a
(s-p+1)! / p! (s-2p+1)!
vedi http://www.infinitoteatrodelcosmo.it/2018/09/21/un-binomio-un-po-strano/
Considerando che con 10 sedie possiamo far sedere al massimo 5 persone non contigue,
ossia con s sedie abbiamo al massimo s/2 persone possibili,
si ottiene la formula completa per le combinazioni totali:
Nel nostro caso sono 144 combinazioni possibili.
Abbiate un pochino di pazienza... il prof si sta godendo qualche giorno di vacanza, prima o poi risponderà
L'espressione per il numero di combinazioni possibili indicata da Leandro è quella che mi ha portato a proporre la serie di Fibonacci per rispondere alla seconda parte del quiz. Enzo chiedeva una formula ricorsiva che utilizzasse solo il numero di trespoli per arrivare alle combinazioni possibili.
Le combinazioni possibili delle posizioni occupate dagli avventori per un certo numero di trespoli n, diciamo C(n), sono le combinazioni per il numero di trespoli inferiore di 1, C(n-1), sommate con le combinazioni per un numero di trespoli inferiore di 2, C(n-2). Quindi C(n)=C(n-1)+C(n-2).
Per 1 trespolo le combinazioni sono 2, C(1)=2, se includiamo anche quella vuota, come chiede Enzo. Per 2 trespoli le combinazioni sono 3, C(2)=3. Posso facilmente calcolare quelle per 3 trespoli applicando la formula ricorsiva. C(3)=C(2)+C(1)=3+2=5. Proseguendo in questo modo si possono calcolare le altre. Ad esempio C(10) posso calcolarla con questa sequenza per n che va da 1 a 10:
C(n)= 2 3 5 8 13 21 34 55 89 144
Questo risultato dipende dalla formula ricorsiva per calcolare i coefficienti binomiali (quella del triangolo di Tartaglia)
e dalla formula indicata da Leandro, cioè in numero di combinazioni possibili per n trespoli e p avventori:
Con quest'ultima formula posso riempire una tabella che ha come elementi le combinazioni possibili per un cenrto numero di trespoli ed un certo numero di avventori.
Nella figura gli elementi della tabella per numero di trespoli da 5 a 8.
seguendo le frecce colorate si vede come applicando la formula ricorsiva vista sopra si ottiene che gli elementi di una riga (ad esempio la 7) sono la somma di elementi delle due righe precedenti ( 6 e 5).
Tradotta in termini numeri la stessa tabella diventa:
Non la conoscevo, ma esiste una formula elegante nota come formula di Binet (dal nome del matematico francese Jacques Binet che la dimostrò nel 1843) che restituisce il valore ennesimo di una successione di Fibonacci, utilizzando il numero aureo (numero al quale tende il rapporto tra l'ennesimo termine e l'ennesimo-1 termine della suddetta successione, per n che tende all'infinito):
Nel caso in questione, la formula di Binet leggermente modificata, restituisce il numero di combinazioni possibili in base solamente al numero p di sedili:
Per p=10,^{-11}&space;\cdot&space;\phi^{-12}&space;+\phi^{12}&space;}{\sqrt{5}}&space;=&space;144)
chiedo scusa a tutti e vi ringrazio... Sono in vacanza per ancora una settimana e faccio fatica a collegarmi... In ogni modo avete raggiunto l'obiettivo. La serie è quella di Fibonacci e la seconda parte consiste nel dimostrare la formula di Binet. Bravissimi! Nel sito dovrebbe anche esserci la dimostrazione (articolo di Umberto...)