Calcolo combinatorio
Scusate se ultimamente sto chiedendo spesso il vostro aiuto ma purtroppo in questi giorni ho un compito e su alcuni determinati argomenti non so proprio metterci mano perchè non riesco a capirli...il mio problema è il calcolo combinatorio e non capisco la differenza tra permutazioni semplici e con ripetizione, disposizioni semplici e con ripetizione, combinazioni semplici e con ripetizione qualcuno mi potrebbe spiegare la differenza sostanziale? Inoltre posterò degli esercizi che non so fare........
1) In quanti modi uno studente può scegliere 5 materie per il proprio piano di studi, avendo a disposizione 5 materie informatiche e 4 materie matematiche ed essendo vincolato a sceglierne almeno 2 materie per ogni area?
2) Quanti sono glia anagrammi della parola "MATEMATICA" che iniziano per "M" e finoscono per "A"?
3) Quante schedine devo giocare per essere certo di fare sei al superenalotto? e per il 5+1?
4) In Italia le targhe automobilistiche sono composte da 2 lettere seguite da 3 cifre 2 da altre due lettere. Nel paese Ailati le cose vanno alla rovescia e le targhe sono composte da 2 cifre, seguite da 3 lettere ed altre 2 cifre. Supponendo che in entrambi i paesi si usino 10 cifre e 22 lettere (I, O, U, Q, non sono utilittate) determinare la differenza tra il numero di tutte le targhe possibili fra quelle italiane e quelle di Ailati.
5) In uno stabilimento un semilavorato è sottoposto a 5 lavorazioni diverse a,b,c,d,e. Se la lavorazione a deve precedere quella b in quanti modi diversi si possono ordinare le lavorazioni? E se la lavorazione c precede quella d?
Lo so sono molti vi chiedo scusa ma sono in difficoltà.........
1) In quanti modi uno studente può scegliere 5 materie per il proprio piano di studi, avendo a disposizione 5 materie informatiche e 4 materie matematiche ed essendo vincolato a sceglierne almeno 2 materie per ogni area?
2) Quanti sono glia anagrammi della parola "MATEMATICA" che iniziano per "M" e finoscono per "A"?
3) Quante schedine devo giocare per essere certo di fare sei al superenalotto? e per il 5+1?
4) In Italia le targhe automobilistiche sono composte da 2 lettere seguite da 3 cifre 2 da altre due lettere. Nel paese Ailati le cose vanno alla rovescia e le targhe sono composte da 2 cifre, seguite da 3 lettere ed altre 2 cifre. Supponendo che in entrambi i paesi si usino 10 cifre e 22 lettere (I, O, U, Q, non sono utilittate) determinare la differenza tra il numero di tutte le targhe possibili fra quelle italiane e quelle di Ailati.
5) In uno stabilimento un semilavorato è sottoposto a 5 lavorazioni diverse a,b,c,d,e. Se la lavorazione a deve precedere quella b in quanti modi diversi si possono ordinare le lavorazioni? E se la lavorazione c precede quella d?
Lo so sono molti vi chiedo scusa ma sono in difficoltà.........
Risposte
visto che non è opportuno che ti rispondiamo a tutti i quesiti contemporaneamente, ti suggerisco di iniziare adl 2) e dal 4) che mi sembrano i più semplici, e tentare di buttar giù una tua idea. per ora ti do una dritta per il 2): fissate due lettere, rimangono 8 lettere di cui due doppie...
se non provi a ragionarci, è inutile. ciao.
se non provi a ragionarci, è inutile. ciao.
allora per il numero 2) dovrebbe essere in questo modo correggimi se baglio.....
M e A sono fisse e non si contano rimangono quindi ATEMATIC 8 lettere
ma dobbiamo tenere conto che ci sono due A e due T che formano anagrammi simili sia
$M={a_1 , a_2 , a_3 , a_4 , a_5 , a_6 , a_7 , a_8}$ l'insieme di tutte le permutazioni. Le soluzioni di questo insieme è 8!
però permutazioni distinte formano lo stesso anagramma per esempio $a_1 , a_2 , a_3 , a_4 , a_5 , a_6 , a_7 , a_8$ e
$a_5 , a_2 , a_3 , a_4 , a_1 , a_6 , a_7 , a_8$ formano lo stesso anagramma
raggruppiamo le due doppie e si ottiene 2! per le lettere "A" e 2! per le lettere "T"
quindi all'insieme di partenza doppiamo togliere le doppie cioè facendo $(8!)/(2!*2!) =10080$
giusto?
M e A sono fisse e non si contano rimangono quindi ATEMATIC 8 lettere
ma dobbiamo tenere conto che ci sono due A e due T che formano anagrammi simili sia
$M={a_1 , a_2 , a_3 , a_4 , a_5 , a_6 , a_7 , a_8}$ l'insieme di tutte le permutazioni. Le soluzioni di questo insieme è 8!
però permutazioni distinte formano lo stesso anagramma per esempio $a_1 , a_2 , a_3 , a_4 , a_5 , a_6 , a_7 , a_8$ e
$a_5 , a_2 , a_3 , a_4 , a_1 , a_6 , a_7 , a_8$ formano lo stesso anagramma
raggruppiamo le due doppie e si ottiene 2! per le lettere "A" e 2! per le lettere "T"
quindi all'insieme di partenza doppiamo togliere le doppie cioè facendo $(8!)/(2!*2!) =10080$
giusto?
sì. bravo. ora prova il 4).
ok ora ci provo.... quella che ho applicato è una permutazione con ripetizione........mi dici quando la devo applicare perchè mi confondo............
rispondere in maniera generale è un po' difficile. comunque se hai come qui un certo numero fisso di "cose" da collocare in un altrettanto numero di "posti", hai da fare delle permutazioni (gli anagrammi sono tipici esempi, e, appunto, se ci sono delle lettere che si ripetono, bisogna tenerne conto)...
quando invece devi formare una parola avendo a disposizione tutte le lettere che ti pare, allora la cosa è diversa (come mi pare sia richiesto nell'esercizio 4)).
quando invece devi formare una parola avendo a disposizione tutte le lettere che ti pare, allora la cosa è diversa (come mi pare sia richiesto nell'esercizio 4)).
per quanto riguarda il numero 4) non sono molto sicuro.......comunque...
in Italia avendo a disposizione 10 cifre e 22 lettere e sapendo che la targa è composta da LLCCCLL dove L=lettera e C=cifra
si hanno le seguenti disposizioni $D^r(L) = 22^2 , D^r(C)=10^3 , D^r(L) = 22^2$ (disposizioni con ripetizioni ma si applicano solo in questo caso? non capisco)
e si ha $R=D^r(L)*D^r(C)*D^r(L)= 22^2*10^3*22^2= 234256000
in Ailati avendo a disposizione sempre 10 cifre e 22 lettere e sapendo che la targa è composta da CCLLLCC dove L=lettera e C=cifra
si hanno le seguenti disposizioni $D^r(C) = 10^2 , D^r(L)=22^3 , D^r(C) = 10^2$
e si ha $R_1=D^r(C)*D^r(L)*D^r(C)= 10^2*22^3*10^2= 106480000
La Differenza $D=R-R_1=234256000-106480000=127776000
in Italia avendo a disposizione 10 cifre e 22 lettere e sapendo che la targa è composta da LLCCCLL dove L=lettera e C=cifra
si hanno le seguenti disposizioni $D^r(L) = 22^2 , D^r(C)=10^3 , D^r(L) = 22^2$ (disposizioni con ripetizioni ma si applicano solo in questo caso? non capisco)
e si ha $R=D^r(L)*D^r(C)*D^r(L)= 22^2*10^3*22^2= 234256000
in Ailati avendo a disposizione sempre 10 cifre e 22 lettere e sapendo che la targa è composta da CCLLLCC dove L=lettera e C=cifra
si hanno le seguenti disposizioni $D^r(C) = 10^2 , D^r(L)=22^3 , D^r(C) = 10^2$
e si ha $R_1=D^r(C)*D^r(L)*D^r(C)= 10^2*22^3*10^2= 106480000
La Differenza $D=R-R_1=234256000-106480000=127776000
il calcolo non è giusto, ma il ragionamento sì.
se ti dice che che in Ailati non vengono utilizzate 4 lettere, vuol dire che in Italia ne devi considerare 26.
mantenendo le tue denominazioni, $R=26^4*10^3," "R_1=22^3*10^4$.
spero sia chiaro. ciao.
se ti dice che che in Ailati non vengono utilizzate 4 lettere, vuol dire che in Italia ne devi considerare 26.
mantenendo le tue denominazioni, $R=26^4*10^3," "R_1=22^3*10^4$.
spero sia chiaro. ciao.
sia in italia che in ailati non vengono usate ( I, o u, q)..........
ah, OK. avevo letto distrattamente. allora è più semplice fare il conto, perché puoi mettere in evidenza $22^3*10^3$, nella sottrazione: non credo infatti che ti sia richiesto il numero in unità.
EDIT: se vuoi controllare il risultato tuo con il mio, correggo un errore di digitazione e scrivo la formula finale:
$R-R_1=22^4*10^3-22^3*10^4=22^3*10^3*(22-10)=12*22^3*10^3=127776000$
EDIT: se vuoi controllare il risultato tuo con il mio, correggo un errore di digitazione e scrivo la formula finale:
$R-R_1=22^4*10^3-22^3*10^4=22^3*10^3*(22-10)=12*22^3*10^3=127776000$
comunque ho fatto tutto giusto?......
mentre per gli altri non ci so mettere mano comletamente
mentre per gli altri non ci so mettere mano comletamente
il 4) è OK. ho completato nell'altro post.
il primo: quali possono essere le scelte in termini di numero di esami per ciascun'area? in quanti modi si possono scegliere?
il primo: quali possono essere le scelte in termini di numero di esami per ciascun'area? in quanti modi si possono scegliere?
allora penso che se sono obbligato a sceglierne almeno due per ogni area e avendone 5 a disposizione
penso
2 materie info e 3 matematica e
3 materie info e 2 matematica
penso sia cosi
penso
2 materie info e 3 matematica e
3 materie info e 2 matematica
penso sia cosi
e dunque? in quanti modi puoi scegliere 2 (o 3) elementi da un insieme di 5 (o 4) elementi?
per quanto riguarda le materie info ne devo scegliere 2 nel primo caso si ha $(5!)/(2!*3!)
mentre matematica devo sceglierne 3 quindi $(4!)/(3!*1!)
poi nel secondo caso le materie info ne devo scegliere 3 nel primo caso si ha $(5!)/(3!*2!)
mentre matematica devo sceglierne 2 quindi $(4!)/(2!*2!)
giusto?
mentre matematica devo sceglierne 3 quindi $(4!)/(3!*1!)
poi nel secondo caso le materie info ne devo scegliere 3 nel primo caso si ha $(5!)/(3!*2!)
mentre matematica devo sceglierne 2 quindi $(4!)/(2!*2!)
giusto?
Problema N.3 posto da Corel
La risposta al primo quesito è ovvia: tante sestine quante ce ne sono possibili, cioè $((90),(6))$.
La risposta al secondo quesito non è per niente ovvia.
Anche se si evita la complicazione del 5+1, e si chiede soltanto:
"Quante sestine devo giocare per esser certo di fare 5", la risposta non è per niente banale.
Entriamo così, quasi senza accorgercene, nel terreno dei cosiddetti "sistemi a riduzione" a proposito dei quali, quando ne si trova lo sviluppo (ad esempio per il Totocalcio in appositi manualetti), non ho mai capito se la risposta viene trovata sviluppando un algoritmo di "searching" o se è possibile trovarne in anticipo almeno il numero.
Il problema dato sopra credo che vada affrontato dopo aver risolto un altro problema più semplice, ma non del tutto banale, cioè:
Data una certa combinazione semplice di N segni a k a k, quante sono le combinazioni di N segni a k a k che differiscono da quella data in esattamente un segno?
Mi pare che la risposta sia: $N+1-2k+u_k-u_1$, dove la combinazione previamente assegnata si suppone scritta come
$(u_1, u_2, ...., u_k)$ con $0
14567 - 24567 - 34568 - 34569 (non ne vedo altre)
Invece,se la combinazione assegnata è 1xyz9 con x, y, z numeri qualsiasi compresi fra 2 e 8, allora il numero di combinazioni che differiscono da quella data (qualunque essa sia) sono 9+1-2(5)+(9-1)=8. Per esempio, se abbiamo come combinazione di riferimento 13579, le combinazioni che differiscono da questa esattamente in un posto (diciamo, le "monovarianti") sono
23579 - 12579 - 14579 - 13479 - 13679 - 13589 - 13569 - 13578 (non mi sembra ce ne siano altre)
Se prendiamo 12789, le monovarianti sono sempre 8: 13789, 14789, 15789, 16789, 12389, 12489, 12589, 12689, fine.
Questo credo dia un'idea della difficoltà di rispondere alla domanda posta da Corel (se sto prendendo un abbaglio, smentitemi!)
Infatti la mia formuletta non risponde alla domanda posta da Corel, bensì a una molto più semplice:
"Se conosciamo la sestina vincente del SuperEnaLotto, quante sono le sestine fra loro diverse che fanno 5 punti?"
E se chiediamo quante di queste sestine azzeccano anche un altro numero, v, il "jolly, scelto a caso fra 1 e N (ma diverso da ciascuno dei 6 numeri già usciti), la risposta è: o 1 o 2.
E' 1 se v è inferiore a tutti i numeri della sestina vincente, oppure se, viceversa, li supera tutti.
E' 2 se si trova "in mezzo", ed allora può sostituirsi sia al numero che immediatamente lo precede, sia a quello che immediatamente lo segue.
Per esempio se la sestina vincente è : 4-25-43-70-77-81 e il jolly è 34, allora il numero delle sestine distinte che fanno 5 punti è
90+1-2(6)+(81-4) = 79+77 = 156
ma, dato che il 34 si colloca fra 25 e 43, ci sono solo due sestine che fanno 5+1:
4-34-43-70-77-81 e 4-25-34-70-77-81.
Scusate se mi sono dilungato, ma l'argomento lo merita. Anzi, penso che potrebbe riempire un topic a parte.
La risposta al primo quesito è ovvia: tante sestine quante ce ne sono possibili, cioè $((90),(6))$.
La risposta al secondo quesito non è per niente ovvia.
Anche se si evita la complicazione del 5+1, e si chiede soltanto:
"Quante sestine devo giocare per esser certo di fare 5", la risposta non è per niente banale.
Entriamo così, quasi senza accorgercene, nel terreno dei cosiddetti "sistemi a riduzione" a proposito dei quali, quando ne si trova lo sviluppo (ad esempio per il Totocalcio in appositi manualetti), non ho mai capito se la risposta viene trovata sviluppando un algoritmo di "searching" o se è possibile trovarne in anticipo almeno il numero.
Il problema dato sopra credo che vada affrontato dopo aver risolto un altro problema più semplice, ma non del tutto banale, cioè:
Data una certa combinazione semplice di N segni a k a k, quante sono le combinazioni di N segni a k a k che differiscono da quella data in esattamente un segno?
Mi pare che la risposta sia: $N+1-2k+u_k-u_1$, dove la combinazione previamente assegnata si suppone scritta come
$(u_1, u_2, ...., u_k)$ con $0
14567 - 24567 - 34568 - 34569 (non ne vedo altre)
Invece,se la combinazione assegnata è 1xyz9 con x, y, z numeri qualsiasi compresi fra 2 e 8, allora il numero di combinazioni che differiscono da quella data (qualunque essa sia) sono 9+1-2(5)+(9-1)=8. Per esempio, se abbiamo come combinazione di riferimento 13579, le combinazioni che differiscono da questa esattamente in un posto (diciamo, le "monovarianti") sono
23579 - 12579 - 14579 - 13479 - 13679 - 13589 - 13569 - 13578 (non mi sembra ce ne siano altre)
Se prendiamo 12789, le monovarianti sono sempre 8: 13789, 14789, 15789, 16789, 12389, 12489, 12589, 12689, fine.
Questo credo dia un'idea della difficoltà di rispondere alla domanda posta da Corel (se sto prendendo un abbaglio, smentitemi!)
Infatti la mia formuletta non risponde alla domanda posta da Corel, bensì a una molto più semplice:
"Se conosciamo la sestina vincente del SuperEnaLotto, quante sono le sestine fra loro diverse che fanno 5 punti?"
E se chiediamo quante di queste sestine azzeccano anche un altro numero, v, il "jolly, scelto a caso fra 1 e N (ma diverso da ciascuno dei 6 numeri già usciti), la risposta è: o 1 o 2.
E' 1 se v è inferiore a tutti i numeri della sestina vincente, oppure se, viceversa, li supera tutti.
E' 2 se si trova "in mezzo", ed allora può sostituirsi sia al numero che immediatamente lo precede, sia a quello che immediatamente lo segue.
Per esempio se la sestina vincente è : 4-25-43-70-77-81 e il jolly è 34, allora il numero delle sestine distinte che fanno 5 punti è
90+1-2(6)+(81-4) = 79+77 = 156
ma, dato che il 34 si colloca fra 25 e 43, ci sono solo due sestine che fanno 5+1:
4-34-43-70-77-81 e 4-25-34-70-77-81.
Scusate se mi sono dilungato, ma l'argomento lo merita. Anzi, penso che potrebbe riempire un topic a parte.
per il primo, OK: fai il conto che dovrebbe venire 100.
per il quinto ci sono due richieste: forse non mi è chiaro il testo, ma mi pare che siano equivalenti. forse la seconda richiesta va intesa con entrambe le limitazioni?
in ogni caso puoi pensare alla prima, e per il discorso fatto prima dovresti pensare ad un ordinamento di "lettere" fisse...
ciao.
per il quinto ci sono due richieste: forse non mi è chiaro il testo, ma mi pare che siano equivalenti. forse la seconda richiesta va intesa con entrambe le limitazioni?
in ogni caso puoi pensare alla prima, e per il discorso fatto prima dovresti pensare ad un ordinamento di "lettere" fisse...
ciao.
"seascoli":
Se la mia formula è giusta, essa mostra come il numero delle combinazioni che differiscono da una data dipende da come è fatta la combinazione data. Per esempio, se ho 9 segni presi a 5 a 5, sono solo 4 le combinazioni che differiscono esattamente in un segno da 34567 (infatti si ha: 9+1-2(5)+(7-3)=4 ) e per la precisione sono:
14567 - 24567 - 34568 - 34569 (non ne vedo altre)
... non conosco bene il gioco del superenalotto, mi sembra che devi indovinare i numeri indipendentemente dalla loro posizione
se è cosi, la combinazione 34567 puo avere anche altre soluzioni che differiscono in un segno:
oltre alle 4 da te citate, puoi avere
13456 13457 13467 .... ne sono 20.
se non è cosi', mi scusate, ma non ho MAI giocato a questo gioco.
ragazzi il numero 1 che ho sviluppato sopra cioè
per quanto riguarda le materie info ne devo scegliere 2 nel primo caso si ha 5!2!⋅3!
mentre matematica devo sceglierne 3 quindi $(4!)/(3!*1!)
poi nel secondo caso le materie info ne devo scegliere 3 nel primo caso si ha 5!3!⋅2!
mentre matematica devo sceglierne 2 quindi $(4!)/(2!*2!)
giusto?
non mi avete detto se è giusto per quanto riguarda il procedimento posto da seascoli è alquanto complicato io ho già difficoltà a capire la differenza tra disposizioni e permutazioni........io ringrazio seascoli per la brillante spiegazione e per l'aiuto che mi sta dando.....comunque io penso che l'esercizio richiede di fare 5+1 come se dovessi fare 6 enunciato da ada.........
per quanto riguarda le materie info ne devo scegliere 2 nel primo caso si ha 5!2!⋅3!
mentre matematica devo sceglierne 3 quindi $(4!)/(3!*1!)
poi nel secondo caso le materie info ne devo scegliere 3 nel primo caso si ha 5!3!⋅2!
mentre matematica devo sceglierne 2 quindi $(4!)/(2!*2!)
giusto?
non mi avete detto se è giusto per quanto riguarda il procedimento posto da seascoli è alquanto complicato io ho già difficoltà a capire la differenza tra disposizioni e permutazioni........io ringrazio seascoli per la brillante spiegazione e per l'aiuto che mi sta dando.....comunque io penso che l'esercizio richiede di fare 5+1 come se dovessi fare 6 enunciato da ada.........
"adaBTTLS":
per il primo, OK: fai il conto che dovrebbe venire 100.
per il quinto ci sono due richieste: forse non mi è chiaro il testo, ma mi pare che siano equivalenti. forse la seconda richiesta va intesa con entrambe le limitazioni?
in ogni caso puoi pensare alla prima, e per il discorso fatto prima dovresti pensare ad un ordinamento di "lettere" fisse...
ciao.
come vedi, sul primo ti ho risposto, ma il calcolo non va "spezzettato": hai verificato il risultato finale?
poi io sul n. 3 non mi sono pronunciata per niente, perché ti sto suggerendo uno alla volta e ti ho suggerito di passare al n. 5.
non ho letto nemmeno le ossservazioni di seascoli e Umby. non mi intendo di superenalotto. penso che per il sei si riferisca a sei numeri a caso, ma non saprei come interpretare il 5+1.
ciao.
Umby scripsit:
E' vero! Adottando a regole simili a quelle dell'Enalotto (me le sono andate a leggere con attenzione), il numero delle combinazioni monovarianti rispetto a una data (ogni combinazione si forma prendendo N segni a k a k) è:
Numero monovarianti = $k(N-k)$, indipendentemente da com'è fatta la specifica combinazione di raffronto!
Quindi nell'esempio da me fatto (9 segni presi a 5 a 5) qualsiasi combinazione ha k(N-k)=5(9-5) = 20 monovarianti (e nel SuperEnalotto qualsiasi sestina vincente ha 504 monovarianti).
Perciò è esatta la risposta data da Umby per la combinazione 34567.
Ma la stessa risposta sarebbe valida per qualsiasi altra combinazione.
Per esempio le 20 monovarianti di 13679 sono:
23679, 34679, 35679, 36789, (3679 coincidono)
12679, 14679, 15679, 16789, (1679 coincidono)
12379, 13479, 13579, 13789, (1379 coincidono)
12369, 13469, 13569, 13689, (1369 coincidono)
12367, 13467, 13567, 13678, (1367 coincidono)
Bene, questo risultato più semplice può aiutarci ora a rispondere al quesito originario di Corel?
Prendiamo il caso, forse più semplice, in cui si chiede: Quante ne devo giocare (di sestine) per essere sicuro di fare 5?
Più in generale: se la combinazione di N oggetti a k a k non è assegnata in anticipo, volendo la garanzia di fare k-1 punti, quante combinazioni devo giocare?
Sappiamo che ogni combinazione ha k(N-k) monovarianti. Ragionamo un po' a chili, come farebbe in prima approssimazione un fisico. La cosa "migliore" che potrebbe capitare (ma non capita!) è che tutte le combinazioni si possano suddividere in classi di equivalenza distinte ognuna contenente una combinazione e le sue "sorelle". Se le cose andassero così allora ci sarebbero
$\frac{((N),(k))} {1+k(N-k)} ~= (\frac{N}{k(N-k)})^2((N-2),(k-1))$
classi distinte. Basterebbe allora giocare una sola combinazione per ogni classe per essere sicuri che "qualunque sia la combinazione che verrà estratta, si facciano almeno k-1 punti (e una volta sola)". Giusto?
Così abbiamo determinato, non la risposta giusta, ma un lower bound del numero cercato.
Per esempio per l'Enalotto si ha N=90, k=6 e il lower bound in questione è : circa 1.233.000 sestine, mentre il numero totale di sestine possibili è 622.614.630, con un fattore di riduzione pari a 1+k(N-k) = 505. E a che serve il lower bound? Beh, se proprio non riesco a trovare una formula esatta chiusa, allora posso ricorrere a un qualche algoritmo di "searching" al computer in grado di prelevare le combinazioni giuste una dopo l'altra. Allora il lower bound mi dice quando fermarmi. Se cioè ne ho trovate già tante, allora è inutile cercare ancora, perchè proprio non possono essercene altre. Chiaro?
se è cosi, la combinazione 34567 puo avere anche altre soluzioni che differiscono in un segno:
oltre alle 4 da te citate, puoi avere
13456 13457 13467 .... ne sono 20.
E' vero! Adottando a regole simili a quelle dell'Enalotto (me le sono andate a leggere con attenzione), il numero delle combinazioni monovarianti rispetto a una data (ogni combinazione si forma prendendo N segni a k a k) è:
Numero monovarianti = $k(N-k)$, indipendentemente da com'è fatta la specifica combinazione di raffronto!
Quindi nell'esempio da me fatto (9 segni presi a 5 a 5) qualsiasi combinazione ha k(N-k)=5(9-5) = 20 monovarianti (e nel SuperEnalotto qualsiasi sestina vincente ha 504 monovarianti).
Perciò è esatta la risposta data da Umby per la combinazione 34567.
Ma la stessa risposta sarebbe valida per qualsiasi altra combinazione.
Per esempio le 20 monovarianti di 13679 sono:
23679, 34679, 35679, 36789, (3679 coincidono)
12679, 14679, 15679, 16789, (1679 coincidono)
12379, 13479, 13579, 13789, (1379 coincidono)
12369, 13469, 13569, 13689, (1369 coincidono)
12367, 13467, 13567, 13678, (1367 coincidono)
Bene, questo risultato più semplice può aiutarci ora a rispondere al quesito originario di Corel?
Prendiamo il caso, forse più semplice, in cui si chiede: Quante ne devo giocare (di sestine) per essere sicuro di fare 5?
Più in generale: se la combinazione di N oggetti a k a k non è assegnata in anticipo, volendo la garanzia di fare k-1 punti, quante combinazioni devo giocare?
Sappiamo che ogni combinazione ha k(N-k) monovarianti. Ragionamo un po' a chili, come farebbe in prima approssimazione un fisico. La cosa "migliore" che potrebbe capitare (ma non capita!) è che tutte le combinazioni si possano suddividere in classi di equivalenza distinte ognuna contenente una combinazione e le sue "sorelle". Se le cose andassero così allora ci sarebbero
$\frac{((N),(k))} {1+k(N-k)} ~= (\frac{N}{k(N-k)})^2((N-2),(k-1))$
classi distinte. Basterebbe allora giocare una sola combinazione per ogni classe per essere sicuri che "qualunque sia la combinazione che verrà estratta, si facciano almeno k-1 punti (e una volta sola)". Giusto?
Così abbiamo determinato, non la risposta giusta, ma un lower bound del numero cercato.
Per esempio per l'Enalotto si ha N=90, k=6 e il lower bound in questione è : circa 1.233.000 sestine, mentre il numero totale di sestine possibili è 622.614.630, con un fattore di riduzione pari a 1+k(N-k) = 505. E a che serve il lower bound? Beh, se proprio non riesco a trovare una formula esatta chiusa, allora posso ricorrere a un qualche algoritmo di "searching" al computer in grado di prelevare le combinazioni giuste una dopo l'altra. Allora il lower bound mi dice quando fermarmi. Se cioè ne ho trovate già tante, allora è inutile cercare ancora, perchè proprio non possono essercene altre. Chiaro?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo