Le (terribili) conseguenze dell'amore!
Mi è stato posto il seguente problema da un mio amico che fa il portiere d'albergo e ora lavora in un hotel a 7 piani.
Ieri mattina diedi al mio aiutante le 7 chiavi diverse che servono ad aprire i 7 ripostigli delle lenzuola di ogni piano.
Come sempre, lui doveva badare a consegnarle alle 7 cameriere che lavorano una per piano.
Quella sciocco (è innamorato di una cameriera) prese le 7 chiavi e se le ficcò in tasca a casaccio, senza badare, e poi le ha distribuite a caso (era tutto impegnato a sorridere alla sua preferita mentre lo faceva).
Lì per lì non ho detto niente, ma, dopo che le cameriere sono andate su ai loro rispettivi piani, mi sono chiesto:
Qual é la probabilità che almeno una cameriera riesca ad aprire il suo ripostiglio?
C'è qualcuno che mi aiuta a risolvere questo problema?
Un mio amico mi ha detto che c'entra il numero $e$ di Nepero, ma non ci credo mica.
Come fa un numero del genere (cioè 2,718281828459045... che é un numero non intero, per giunta irrazionale e trascendente) a fare la sua comparsa in questo problema?
Boh!
Ieri mattina diedi al mio aiutante le 7 chiavi diverse che servono ad aprire i 7 ripostigli delle lenzuola di ogni piano.
Come sempre, lui doveva badare a consegnarle alle 7 cameriere che lavorano una per piano.
Quella sciocco (è innamorato di una cameriera) prese le 7 chiavi e se le ficcò in tasca a casaccio, senza badare, e poi le ha distribuite a caso (era tutto impegnato a sorridere alla sua preferita mentre lo faceva).
Lì per lì non ho detto niente, ma, dopo che le cameriere sono andate su ai loro rispettivi piani, mi sono chiesto:
Qual é la probabilità che almeno una cameriera riesca ad aprire il suo ripostiglio?
C'è qualcuno che mi aiuta a risolvere questo problema?
Un mio amico mi ha detto che c'entra il numero $e$ di Nepero, ma non ci credo mica.
Come fa un numero del genere (cioè 2,718281828459045... che é un numero non intero, per giunta irrazionale e trascendente) a fare la sua comparsa in questo problema?
Boh!
Risposte
[mod="Luca B."]
Ho riportato il titolo del topic in minuscolo
[/mod]
Ho riportato il titolo del topic in minuscolo
[/mod]
Io arrivo a risultato diverso. Suppongo che non ci sia "reimbussolamento" , ossia che le 7 chiavi siano distribuite a caso , ma esattamente 1 per ogni cameriera.
L' evento complementare è che nessuna riceva la chiave giusta.
La probabilità che la prima non riceva la chiave giusta è 6/7
La prob che la seconda non riceva la chiave giusta, posto che la prima non abbia ricevuto la chiave giusta è 5/6
La probabilità che il fallimento riguardi tutte le 7 cameriere è il prodotto delle 7 probabilità e vale
6/7 * 5/6 * 4/5 *3/4 * 2/3 * 1/2 * 1/1 = 1/7 = circa 14,3%
saluti
gino
L' evento complementare è che nessuna riceva la chiave giusta.
La probabilità che la prima non riceva la chiave giusta è 6/7
La prob che la seconda non riceva la chiave giusta, posto che la prima non abbia ricevuto la chiave giusta è 5/6
La probabilità che il fallimento riguardi tutte le 7 cameriere è il prodotto delle 7 probabilità e vale
6/7 * 5/6 * 4/5 *3/4 * 2/3 * 1/2 * 1/1 = 1/7 = circa 14,3%
saluti
gino
siccome stavo cercando anch'io un metodo più semplice, ho da fare una piccola obiezione:
la prima cameriera con probabilità 6/7 riceve la chiave che avrebbe dovuto essere di una delle successive, la seconda può ricevere la chiave della prima oppure di una delle successive, ... quando è il turno di una cameriera la cui chiave è già stata data, la probabilità che abbia una chiave diversa dalla propria è 1, e non sempre (numero di chiavi rimaste - 1)/(numero di chiavi rimaste), fino alla penultima. non credo, quindi si possa ridurre il tutto ad un semplice prodotto.
ciao.
la prima cameriera con probabilità 6/7 riceve la chiave che avrebbe dovuto essere di una delle successive, la seconda può ricevere la chiave della prima oppure di una delle successive, ... quando è il turno di una cameriera la cui chiave è già stata data, la probabilità che abbia una chiave diversa dalla propria è 1, e non sempre (numero di chiavi rimaste - 1)/(numero di chiavi rimaste), fino alla penultima. non credo, quindi si possa ridurre il tutto ad un semplice prodotto.
ciao.
Esatto! Non si può ottenere la risposta con un semplice prodotto usando tra l'altro il metodo progressivo (o "diacronico", come io lo chiamo) proposto da "topi" (il metodo alternativo io lo chiamo, viceversa, "sincronico").
Occorre trovare, cosa di per sé interessante, quante delle $n!$ di permutazioni di $n$ oggetti non lasciano al proprio posto nessuno degli $n$ oggetti. E per far ciò occorre risolvere il problema complementare, cioè:
Quante permutazioni lasciano al suo posto un certo oggetto (a prescindere se altri pure restino al loro posto)?
Quante permutazioni lasciano al suo posto due oggetti fissati (a prescindere da cosa succede agli altri)?
.............. etc.
Ma purtroppo non si possono poi sommare semplicemente questi numeri di permutazioni.
Infatti occorre prendere atto del fatto che i suddetti insiemi di permutazioni formano insiemi non disgiunti ...
E qui interviene la formula (carina di per sé) per trovare l'area di N figure del piano parzialmente (o anche totalmente) sovrapposte, che è bene conoscere, perchè torna utile anche in tanti altri contesti.
PS: Il problema da me formulato come "problema dele 7 chiavi d'albergo" è conosciuto in letteratura come "problema delle coincidenze" e risale, almeno per l'enunciazione, ad un certo Montmort che lo pose intorno alla metà del 18° secolo.
Occorre trovare, cosa di per sé interessante, quante delle $n!$ di permutazioni di $n$ oggetti non lasciano al proprio posto nessuno degli $n$ oggetti. E per far ciò occorre risolvere il problema complementare, cioè:
Quante permutazioni lasciano al suo posto un certo oggetto (a prescindere se altri pure restino al loro posto)?
Quante permutazioni lasciano al suo posto due oggetti fissati (a prescindere da cosa succede agli altri)?
.............. etc.
Ma purtroppo non si possono poi sommare semplicemente questi numeri di permutazioni.
Infatti occorre prendere atto del fatto che i suddetti insiemi di permutazioni formano insiemi non disgiunti ...
E qui interviene la formula (carina di per sé) per trovare l'area di N figure del piano parzialmente (o anche totalmente) sovrapposte, che è bene conoscere, perchè torna utile anche in tanti altri contesti.
PS: Il problema da me formulato come "problema dele 7 chiavi d'albergo" è conosciuto in letteratura come "problema delle coincidenze" e risale, almeno per l'enunciazione, ad un certo Montmort che lo pose intorno alla metà del 18° secolo.
distinguendo i vari casi (dal suggerimenti di topi al mio commento successivo) si può procedere con un diagramma ad albero che riporta al numero 1854 già trovato da Umby e riportato in un altro topic. non è semplice illustrarlo con gli strumenti del forum. ci provo.
si parte da un elemento (ad esempio 1) che si collega ad un altro elemento qualsiasi (ad esempio 2, con 6 possibilità di scelta). a quel punto vanno considerati due casi: o il 2 si ricollega con 1 e rimangono 5 elementi da collegare fra loro (per cui si potrebbe anche usare un risultato già trovato di 44 casi, ma si può tranquillamente andare avanti ad esaminare i vari sottocasi), oppure il 2 si collega con un altro elemento (ad esempio 3, con 5 possibilità di scelta), e si va avanti così.
provo a scrivere solo i numeri relativi alle varie possibilità, mettendo la graffa quando distinguo due casi e la freccia quando considero un solo caso.
$->6{[1->4{[1->2->1], [3{[1->1],[2->1] :}] :}]; [5{[1->3{[1->1],[2->1] :}], [4{[1->2->1],[3{[1->1],[2->1] :}] :}] :}$
esaminando l'anteprima, vedo che inserisce in successione le due parentesi quadre principali, mentre avrebbero dovuto essere le due alternative principali.
spero si capisca. in tal caso il calcolo è il seguente:
$6*1*4*1*2*1+6*1*4*3*1*1+6*1*4*3*2*1+6*5*1*3*1*1+6*5*1*3*2*1+6*5*4*1*2*1+6*5*4*3*1*1+6*5*4*3*2*1=1854$
ciao.
si parte da un elemento (ad esempio 1) che si collega ad un altro elemento qualsiasi (ad esempio 2, con 6 possibilità di scelta). a quel punto vanno considerati due casi: o il 2 si ricollega con 1 e rimangono 5 elementi da collegare fra loro (per cui si potrebbe anche usare un risultato già trovato di 44 casi, ma si può tranquillamente andare avanti ad esaminare i vari sottocasi), oppure il 2 si collega con un altro elemento (ad esempio 3, con 5 possibilità di scelta), e si va avanti così.
provo a scrivere solo i numeri relativi alle varie possibilità, mettendo la graffa quando distinguo due casi e la freccia quando considero un solo caso.
$->6{[1->4{[1->2->1], [3{[1->1],[2->1] :}] :}]; [5{[1->3{[1->1],[2->1] :}], [4{[1->2->1],[3{[1->1],[2->1] :}] :}] :}$
esaminando l'anteprima, vedo che inserisce in successione le due parentesi quadre principali, mentre avrebbero dovuto essere le due alternative principali.
spero si capisca. in tal caso il calcolo è il seguente:
$6*1*4*1*2*1+6*1*4*3*1*1+6*1*4*3*2*1+6*5*1*3*1*1+6*5*1*3*2*1+6*5*4*1*2*1+6*5*4*3*1*1+6*5*4*3*2*1=1854$
ciao.
Deve essere un ragionamento molto interessante, ma, per le possibilità limitate di presentazione esistenti in questo forum, è difficilmente comunicabile altrui. Anche lo schema è difficilmente comprensibile.
Grazie comunque per aver indicato l'esistenza di un'impostazione alternativa.
Grazie comunque per aver indicato l'esistenza di un'impostazione alternativa.
prego.
forse lo schema precedente diventa più chiaro se lo si vede parallelamente ad "una possibile strada": in quello già presentato si vedono le possibilità, nel nuovo i numeri degli elementi da collegare (quando le possibilità sono diverse, si mette un possibile rappresentante, che però poi condizionerà le scelte successive):
$->6{[1->4{[1->2->1], [3{[1->1],[2->1] :}] :}]; [5{[1->3{[1->1],[2->1] :}], [4{[1->2->1],[3{[1->1],[2->1] :}] :}] :}$
$(1->2)->$
$->{[(2->1)->(3->4)->{[((4->3)->(5->6)->(6->7)->(7->1))], [((4->5)->{[((5->3)->(6->7))],[((5->6)->(6->7)->(7->3))] :}] :}] :}$
$->{[(2->3)->{[((3->1)->(4->5)->{[((5->4)->(6->7)->(7->6))],[((5->6)->(6->7)->(7->4))] :}], [(3->4)->{[((4->1)->(5->6)->(6->7)->(7->5))],[((4->5)->{[((5->1)->(6->7)->(7->6))],[((5->6)->(6->7)->(7->1))] :}] :}] :}$
vedendo l'anteprima, in cui non ci capivo neppure io che avevo fatto lo schema, ho dovuto complicare un tantino, ed abbondare in parentesi.
tra parentesi tonde e con le frecce (ad esempio $(1->2)$) intendo le associazioni tra gli elementi:
in questo caso "la chiave del primo piano va alla cameriera del secondo piano".
sono dovuta andare accapo, per cui spero siano visibili le corrispondenze tra i casi possibili del primo schema e le associazioni del secondo schema.
spero di aver reso l'idea.
ciao.
forse lo schema precedente diventa più chiaro se lo si vede parallelamente ad "una possibile strada": in quello già presentato si vedono le possibilità, nel nuovo i numeri degli elementi da collegare (quando le possibilità sono diverse, si mette un possibile rappresentante, che però poi condizionerà le scelte successive):
$->6{[1->4{[1->2->1], [3{[1->1],[2->1] :}] :}]; [5{[1->3{[1->1],[2->1] :}], [4{[1->2->1],[3{[1->1],[2->1] :}] :}] :}$
$(1->2)->$
$->{[(2->1)->(3->4)->{[((4->3)->(5->6)->(6->7)->(7->1))], [((4->5)->{[((5->3)->(6->7))],[((5->6)->(6->7)->(7->3))] :}] :}] :}$
$->{[(2->3)->{[((3->1)->(4->5)->{[((5->4)->(6->7)->(7->6))],[((5->6)->(6->7)->(7->4))] :}], [(3->4)->{[((4->1)->(5->6)->(6->7)->(7->5))],[((4->5)->{[((5->1)->(6->7)->(7->6))],[((5->6)->(6->7)->(7->1))] :}] :}] :}$
vedendo l'anteprima, in cui non ci capivo neppure io che avevo fatto lo schema, ho dovuto complicare un tantino, ed abbondare in parentesi.
tra parentesi tonde e con le frecce (ad esempio $(1->2)$) intendo le associazioni tra gli elementi:
in questo caso "la chiave del primo piano va alla cameriera del secondo piano".
sono dovuta andare accapo, per cui spero siano visibili le corrispondenze tra i casi possibili del primo schema e le associazioni del secondo schema.
spero di aver reso l'idea.
ciao.
Avendo seguito l'intero corso degli interventi, per me questa rappresentazione è chiara.
Se ho ben capito, sei partita da:
$D(n) = (n-1)*[D(n-1) + D(n-2)]$
quindi per n=7
$D(7) = (7-1)*[D(7-1) + D(7-2)]$
ovvero
$D(7) = 6*[D(6) + D(5)]$
poi hai sostituito D(6) e D(5) con
$D(7) = 6*[5*[D(5) + D(4)] + 4*[D(4) + D(3)]]$
e cosi' via ..... fino a raggiungere D1 e D2 (valori conosciuti, e non calcolabili con questo processo..)
Grazie.
Se ho ben capito, sei partita da:
$D(n) = (n-1)*[D(n-1) + D(n-2)]$
quindi per n=7
$D(7) = (7-1)*[D(7-1) + D(7-2)]$
ovvero
$D(7) = 6*[D(6) + D(5)]$
poi hai sostituito D(6) e D(5) con
$D(7) = 6*[5*[D(5) + D(4)] + 4*[D(4) + D(3)]]$
e cosi' via ..... fino a raggiungere D1 e D2 (valori conosciuti, e non calcolabili con questo processo..)
Grazie.
sì, di fatto i due sottoalberi dividono i casi in cui "un cerchio si chiude" e quindi si passa a "due numeri inferiori" e all'altro caso in cui il "cerchio rimane aperto" ed il risultato è assimilabile a quello di "un numero inferiore" però si può ulteriormente "ri-suddividere" il percorso.
in realtà, quando anch'io ho ricavato i numeri 2, 9, 44, studiando le permutazioni di 3,4,5 elementi, lo stavo facendo con un altro scopo.
se hai presente una mia domanda poco chiara sulle permutazioni assimilabili a cicli di lunghezza fissata, anziché trovarmi al calcolo diretto di 265 e 1854 come risultato finale, avrei voluto contare appunto solo le permutazioni cicliche di lunghezza fissata (spero di riuscire a farmi capire), ma mi sono trovata di fronte, ad esempio, a quelle di quattro elementi (4 infatti non è un numero primo) i cui quadrati potevano essere espressi in prodotti di due cicli disgiunti di lunghezza due, e la cosa rendeva praticamente inutile il mio tentativo di trovare quel benedetto numero sottraendo da 7! tutti quei cicli di lunghezza fissa o esprimibili come prodotto di cicli di lunghezza fissa: ecco perché ho provato a scrivere 7 come somma di più addendi.
avendo selezionato tutti gli elementi che permutavano ciclicamente tra loro, considerando gli altri come fissi, con i coefficienti binomiali e/o multinomiali come fattori, avrei dovuto trovare i vari termini da sottrarre a 7!, ma decisamente i numeri avrebbero dovuto essere molto più piccoli di quelli trovati direttamente, e credo che non sia possibile.
se sono riuscita a farmi capire, che cosa ne pensi? hai qualche idea al riguardo?
in realtà, quando anch'io ho ricavato i numeri 2, 9, 44, studiando le permutazioni di 3,4,5 elementi, lo stavo facendo con un altro scopo.
se hai presente una mia domanda poco chiara sulle permutazioni assimilabili a cicli di lunghezza fissata, anziché trovarmi al calcolo diretto di 265 e 1854 come risultato finale, avrei voluto contare appunto solo le permutazioni cicliche di lunghezza fissata (spero di riuscire a farmi capire), ma mi sono trovata di fronte, ad esempio, a quelle di quattro elementi (4 infatti non è un numero primo) i cui quadrati potevano essere espressi in prodotti di due cicli disgiunti di lunghezza due, e la cosa rendeva praticamente inutile il mio tentativo di trovare quel benedetto numero sottraendo da 7! tutti quei cicli di lunghezza fissa o esprimibili come prodotto di cicli di lunghezza fissa: ecco perché ho provato a scrivere 7 come somma di più addendi.
avendo selezionato tutti gli elementi che permutavano ciclicamente tra loro, considerando gli altri come fissi, con i coefficienti binomiali e/o multinomiali come fattori, avrei dovuto trovare i vari termini da sottrarre a 7!, ma decisamente i numeri avrebbero dovuto essere molto più piccoli di quelli trovati direttamente, e credo che non sia possibile.
se sono riuscita a farmi capire, che cosa ne pensi? hai qualche idea al riguardo?
"adaBTTLS":
se sono riuscita a farmi capire, che cosa ne pensi? hai qualche idea al riguardo?
per ora nessuna idea...
Spero ci si renda conto che, essendo così intrecciato già solo per 7 chiavi, figuriamoci se possiamo usare lo schema à la Ada per, che dire, 77 chiavi! C'è da rimanere annichiliti.
Molto più umana e praticabile sembra la relazione di ricorrenza trovata da Umby che riduce tutto a un puro calcolo, benchè ricorsivo.
Rimane poi la mia formula chiusa (in forma di sommatoria) che taglia la testa al toro. Tra l'altro da questa si vede che per N>6 circa è inutile affannarsi, perchè c'è un'ottima approsimazione e cioè le permutazioni che non lasciano nessun oggetto al suo posto sono una frazione pari a 1/e del totale, cioè n!/e. Più limpido di così!
Allora mi chiedo se c'é anche qualche altra formule chiusa alternastiva.
Me lo chiedo perchè Umby aveva lasciato quasi intendere di sì.
Se é così, spero che prima o poi esca fuori ...
Molto più umana e praticabile sembra la relazione di ricorrenza trovata da Umby che riduce tutto a un puro calcolo, benchè ricorsivo.
Rimane poi la mia formula chiusa (in forma di sommatoria) che taglia la testa al toro. Tra l'altro da questa si vede che per N>6 circa è inutile affannarsi, perchè c'è un'ottima approsimazione e cioè le permutazioni che non lasciano nessun oggetto al suo posto sono una frazione pari a 1/e del totale, cioè n!/e. Più limpido di così!
Allora mi chiedo se c'é anche qualche altra formule chiusa alternastiva.
Me lo chiedo perchè Umby aveva lasciato quasi intendere di sì.
Se é così, spero che prima o poi esca fuori ...
tengo a precisare che lo schema non dà nulla di nuovo rispetto alla formula di Umby, ma risponde al quesito di topi e "dimostra" la formula ricorsiva.
f(k)=(k-1)[f(k-2)+f(k-1)]=(k-1)f(k-2)+(k-1)(k-2)[f(k-3)+f(k-2)]=...
le risposte che aspetto possono venire dagli algebristi. forse posterò in Università, se riuscirò a formulare decentemente la domanda.
ciao.
f(k)=(k-1)[f(k-2)+f(k-1)]=(k-1)f(k-2)+(k-1)(k-2)[f(k-3)+f(k-2)]=...
le risposte che aspetto possono venire dagli algebristi. forse posterò in Università, se riuscirò a formulare decentemente la domanda.
ciao.
"adaBTTLS":
se sono riuscita a farmi capire, che cosa ne pensi? hai qualche idea al riguardo?
Qualcosina ho trovato. Non so, se nella direzione che cercavi te.
Diciamo che sono partito dal fatto che la precedente formula necessitava dei due valori precedenti, e pertanto, per renderla funzionante era necessario calcolare manualmente almeno il valore di D1 e D2.
Questa seconda formula, è molto più snella e più facile da rappresentare.
Ne possiamo farne 2:
- Tutti i valori squadrati
- Almeno uno a posti
La base di partenza è lo 0 (zero) per la prima, ed 1 per la seconda. (D1)
Tutti i valori squadrati:
$D_n = n * D_(n-1) + (-1)^n$
quindi:
$D_2 = 2 * 0 + 1 = 1$
$D_3 = 3 * 1 - 1 = 2$
.....
Pertanto:
$D_7 = 7*(6*(5*(4*(3*(2*0+1)-1)+1)-1)+1)-1 = 1854$
$D_n = n * D_(n-1) + (-1)^n$
quindi:
$D_2 = 2 * 0 + 1 = 1$
$D_3 = 3 * 1 - 1 = 2$
.....
Pertanto:
$D_7 = 7*(6*(5*(4*(3*(2*0+1)-1)+1)-1)+1)-1 = 1854$
Almeno uno a posto:
$P_n = n * P_(n-1) - (-1)^n$
quindi:
$P_7 = 7*(6*(5*(4*(3*(2*1-1)+1)-1)+1)-1)+1 = 3186$
Ora si potrebbe dimostrare anche che:
$D_n + P_n = n!$
$P_n = n * P_(n-1) - (-1)^n$
quindi:
$P_7 = 7*(6*(5*(4*(3*(2*1-1)+1)-1)+1)-1)+1 = 3186$
Ora si potrebbe dimostrare anche che:
$D_n + P_n = n!$
carine!
ora non ho proprio tempo, ma ci tornerò su.
se vuoi avere un'idea di quello che intendevo puoi cercare a Università, dove ho aperto un topic al riguardo (permutazioni cicliche di lunghezza fissata, o qualcosa del genere), anche se non so se si capisca molto, e finora non ha risposto nessuno.
ciao e grazie.
ora non ho proprio tempo, ma ci tornerò su.
se vuoi avere un'idea di quello che intendevo puoi cercare a Università, dove ho aperto un topic al riguardo (permutazioni cicliche di lunghezza fissata, o qualcosa del genere), anche se non so se si capisca molto, e finora non ha risposto nessuno.
ciao e grazie.
Entrambe le formule date da Umby sono una conseguenza immediata del fatto (da me da tempo segnalato) che
$\P_n=n!(1 - 1/(1!) + 1/(2!) - 1/(3!) + ... + \pm 1/(n!))$
e inoltre della definizione stessa:
$D_n = n! - P_n$
$\P_n=n!(1 - 1/(1!) + 1/(2!) - 1/(3!) + ... + \pm 1/(n!))$
e inoltre della definizione stessa:
$D_n = n! - P_n$
allora, riprendo la discussione su questo topic perché, nonostante non abbia ricevuto risposta alla domanda che ho postato nella sezione Università, ho trovato comunque quello che cercavo nell'altro forum di Scienze Matematiche (nella risposta di fields ad un altro quesito). lascio il link:
http://www.scienzematematiche.it/forum/ ... hp?f=8&t=8
evidenzio la parte interessata e la riporto qui:
è proprio quello che io cercavo per ricondurci a contare i cicli di lunghezza fissa e considerare le "decomposizioni" del numero 7 in addendi positivi.
scrivo 7 come somma di addendi positivi in tutti i modi possibili:
7=7
7=6+1, 7=5+2, 7=4+3
7=5+1+1, 7=4+2+1, 7=3+3+1, 7=3+2+2
7=4+1+1+1, 7=3+2+1+1, 7=2+2+2+1
7=3+1+1+1+1, 7=2+2+1+1+1
7=2+1+1+1+1+1
7=1+1+1+1+1+1+1
associo ad ogni addendo un ciclo di lunghezza pari all'addendo stesso.
dunque le decomposizioni che non contengono 1 come addendo sono associate alle permutazioni che non lasciano elementi fissi:
7, 5+2, 4+3, 3+2+2,
mentre tutte le altre sono associate alle permutazioni che presentano almeno un elemento fisso.
applicando la formula $(n!)/(n_0!*...*n_k!*(b_0)^(n_0)*...*(b_k)^(n_k))$ alle 4 decomposizioni che non contengono 1 e sommando i risultati si ottiene il numero di permutazioni distinte dell'insieme {1,2,3,4,5,6,7} che non lasciano alcun elemento fisso, cioè la risposta al problema delle chiavi e delle cameriere:
$(7!)/7+(7!)/(5*2)+(7!)/(4*3)+(7!)/(3*2^2*2!)=1854$
se si vuole fare a riprova lo stesso calcolo sulle restanti decomposizioni si vedrà che il numero di permutazioni di {1,2,3,4,5,6,7} che lasciano almeno un elemento fisso è 3186, per cui in totale vengono $5040=7!$ permutazioni.
la probabilità richiesta (non me la ricordo più, ma penso che sia che nessuna cameriera abbia la chiave giusta) è dunque, come già verificato in altri modi, $P=1854/5040="circa" 36.7%$.
ci tengo a precisare che non si tratta di vedere quale formula sia la migliore, ma, avendo io "lavorato" anni fa ad un problema sui sottogruppi ciclici dei gruppi di permutazioni, l'idea dell'utilità della decomposizione del numero 7 in addendi mi "martellava" continuamente il cervello, ed in questo modo ho potuto verificarla (nel senso che tale idea ha portato ad una soluzione alternativa) nonostante mi era parso di capire che per altri l'argomento era fuori tema.
ciao a tutti e grazie per l'attenzione.
http://www.scienzematematiche.it/forum/ ... hp?f=8&t=8
evidenzio la parte interessata e la riporto qui:
una permutazione di n oggetti viene completamente descritta in questo modo. Decomponiamo la permutazione in cicli disgiunti. Otteniamo allora una partizione di n come somma di interi positivi, quando ci concentriamo sulle cardinalita' dei cicli, e possiamo vedere ogni intero della partizione come un "bidone" che contiene gli elementi del ciclo.
Supponiamo allora $n=b_0n_0+ ... +b_kn_k$ sia una partizione di n in interi positivi distinti $b_0,...,b_k$. Vogliamo in qualche modo rappresentare tutte le permutazioni che partizionano n in tal modo, quando decomposte in cicli disgiunti. Una stringa contenente tutti gli n oggetti fa al caso nostro. I primi $b_0$ elementi rappresentano il primo ciclo della permutazione, i secondi $b_1$ elementi rappresentano il secondo ciclo della permutazione....., gli ultimi $b_k$ elementi rappresentano l'ultimo ciclo della permutazione.
Il problema e' che piu' stringhe possono rappresentare la stessa permutazione, determinando una classe di equivalenza di una certa cardinalita'. Infatti ad esempio la sequenza $c_1c_2c_3$ rappresenta lo stesso ciclo di $c_3c_1c_2$. Un po' di riflessione mostra che ci sono esattamente
$n_0!*...*n_k!*(b_0)^(n_0)*...*(b_k)^(n_k)$ stringhe che rappresentano la stessa permutazione e quindi
$(n!)/(n_0!*...*n_k!*(b_0)^(n_0)*...*(b_k)^(n_k))$ classi di equivalenza.
è proprio quello che io cercavo per ricondurci a contare i cicli di lunghezza fissa e considerare le "decomposizioni" del numero 7 in addendi positivi.
scrivo 7 come somma di addendi positivi in tutti i modi possibili:
7=7
7=6+1, 7=5+2, 7=4+3
7=5+1+1, 7=4+2+1, 7=3+3+1, 7=3+2+2
7=4+1+1+1, 7=3+2+1+1, 7=2+2+2+1
7=3+1+1+1+1, 7=2+2+1+1+1
7=2+1+1+1+1+1
7=1+1+1+1+1+1+1
associo ad ogni addendo un ciclo di lunghezza pari all'addendo stesso.
dunque le decomposizioni che non contengono 1 come addendo sono associate alle permutazioni che non lasciano elementi fissi:
7, 5+2, 4+3, 3+2+2,
mentre tutte le altre sono associate alle permutazioni che presentano almeno un elemento fisso.
applicando la formula $(n!)/(n_0!*...*n_k!*(b_0)^(n_0)*...*(b_k)^(n_k))$ alle 4 decomposizioni che non contengono 1 e sommando i risultati si ottiene il numero di permutazioni distinte dell'insieme {1,2,3,4,5,6,7} che non lasciano alcun elemento fisso, cioè la risposta al problema delle chiavi e delle cameriere:
$(7!)/7+(7!)/(5*2)+(7!)/(4*3)+(7!)/(3*2^2*2!)=1854$
se si vuole fare a riprova lo stesso calcolo sulle restanti decomposizioni si vedrà che il numero di permutazioni di {1,2,3,4,5,6,7} che lasciano almeno un elemento fisso è 3186, per cui in totale vengono $5040=7!$ permutazioni.
la probabilità richiesta (non me la ricordo più, ma penso che sia che nessuna cameriera abbia la chiave giusta) è dunque, come già verificato in altri modi, $P=1854/5040="circa" 36.7%$.
ci tengo a precisare che non si tratta di vedere quale formula sia la migliore, ma, avendo io "lavorato" anni fa ad un problema sui sottogruppi ciclici dei gruppi di permutazioni, l'idea dell'utilità della decomposizione del numero 7 in addendi mi "martellava" continuamente il cervello, ed in questo modo ho potuto verificarla (nel senso che tale idea ha portato ad una soluzione alternativa) nonostante mi era parso di capire che per altri l'argomento era fuori tema.
ciao a tutti e grazie per l'attenzione.
"adaBTTLS":
ciao a tutti e grazie per l'attenzione.
Questa soluzione, intuitivamente è un po piu' complessa (mi riferisco a capirla, da un punto di vista logico), ma è molto interessante.
Se ho ben capito, questa strada potrebbe anche essere utile alla soluzione di quesiti del tipo:
"Calcolare la probabilità che almeno 2 Cameriere abbiano la chiave giusta" (dove il 2, potrebbe essere genericamente n)
sì, i numeri sono stati calcolat indipendentemente l'uno dall'altro. quindi per le permutazioni che lasciano esattamente un elemento fisso basta sommare i numeri relativi alle quattro somme con un solo 1: 6+1, 4+2+1, 3+3+1, 2+2+2+1, che sono rispettivamente 840, 630, 280, 105 (somma 1855), ad esmpio, per cui la probabilità che almeno 2 cameriere abbiano la chiave giusta è (5040-1854-1855)/5040=1331/5040
0 cameriere: (720+420+504+210)/5040=1854/5040
esattamente 1: (840+630+280+105)/5040=1855/5040
esattamente 2: (504+420)/5040=924/5040
esattamente 3: (210+105)/5040=315/5040
esattamente 4: 70/5040
esattamente 5: 21/5040
esattamente 6: 0
esattamente 7: 1/5040
0 cameriere: (720+420+504+210)/5040=1854/5040
esattamente 1: (840+630+280+105)/5040=1855/5040
esattamente 2: (504+420)/5040=924/5040
esattamente 3: (210+105)/5040=315/5040
esattamente 4: 70/5040
esattamente 5: 21/5040
esattamente 6: 0
esattamente 7: 1/5040
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo