Combinatoria2011 - fabiobonoli .it

Il calcolo
combinatorio
Quanti sono?
prof. Fabio Bonoli
www.fabiobonoli.it
16 dicembre 2011
Liceo scientifico “A. Righi - Cesena
Sommario
1 - INTRODUZIONE
 Esempi e regole generali
2 – COMBINATORIA IN FORMULE
 Le disposizioni
 Le combinazioni
 Disposizioni con ripetizione
 Permutazioni e permutazioni cicliche
 Il coefficiente binomiale
 Il binomio di Newton
3– PROBLEMI VARI DI COMBINATORIA
In quanti modi può accadere un evento?
Quanti …
Il calcolo combinatorio si occupa di
determinare (contare) quanti sono i
raggruppamenti che si possono fare con n
oggetti di un insieme finito, secondo
determinate regole.
Introduzione
Il calcolo combinatorio - Quanti sono?
Problema:
In quanti modi una associazione composta da 9 membri
può nominare un presidente, un vice e un segretario
cassiere?
Schematizzando:
Quante sono le possibili configurazioni (terne) ordinate e
senza ripetizioni?
Soluzione:
9 scelte possibili per il presidente, a questo punto restano
8 scelte possibili per il vice presidente e infine 7 scelte
per il segretario. 9  8  7  504 modi
Introduzione
Il calcolo combinatorio - Quanti sono?
PRIMA REGOLA
Se una scelta può essere fatta in r modi diversi,
per ciascuno dei quali una seconda scelta può essere
effettuata in s modi diversi,
e, per ciascuno dei modi in cui si sono compiute le
prime due scelte, una terza scelta può essere
effettuata in t modi diversi ecc.,
allora la successione di tutte le scelte può essere
compiuta in
r·s·t ... modi diversi
Introduzione
Il calcolo combinatorio - Quanti sono?
Problema:
Quattro squadre partecipano ad un torneo, quante sono le possibili
classifiche finali?
Schematizzando: Quante sono le possibili configurazioni (quaterne)
ordinate e senza ripetizioni? (Tutti gli elementi vengono considerati)
Soluzione:
4 scelte possibili per il vincitore, a questo punto restano 3 scelte
possibili per il secondo, 2 scelte possibili per il terzo e infine 1
scelta obbligata per l’ultimo classificato.
4  3 2 1  24 classifich e
Introduzione
Il calcolo combinatorio - Quanti sono?
SECONDA REGOLA (conseguenza della prima)
Dati n oggetti, essi si possono "mettere in fila" (o
“mettere in colonna”) in n! modi diversi,
dove il simbolo n! = n·(n-1)·(n-2)· … ·3·2·1.
Infatti, per la scelta del primo oggetto della fila abbiamo n
possibilità;
a ciascuna di queste n possibilità sono abbinate (n-1)
possibilità di scelta per il secondo oggetto della fila;
ad ognuna delle n·(n-1) possibilità per i primi due oggetti
corrispondono (n- 2) possibilità di scelta per il terzo
oggetto della fila; ... ;
in totale, quindi, n oggetti possono essere ordinati in
n·(n-1)·(n-2)· … ·3·2·1 = n! modi diversi.
Introduzione
Il calcolo combinatorio - Quanti sono?
Problema:
In quanti modi un insegnante può scegliere 4 studenti in una classe di
25 alunni per un’ora di interrogazioni?
Testo equivalente:
Quante sono le possibili quaterne di alunni interrogati?
Schematizzando:
Quante sono le possibili configurazioni (quaterne) NON ordinate e
senza ripetizioni?
Soluzione:
Ragionando come prima, calcoliamo le quaterne ordinate:
25 scelte possibili per il primo, a questo punto restano 24 scelte
possibili per il secondo, ora 23 scelte possibili per il terzo e infine
22 scelte per l’ultimo.
25  24  23 22  303600
Introduzione
Il calcolo combinatorio - Quanti sono?
Noi però vogliamo "raggruppare" tutte le quaterne "equivalenti" (cioè,
contenenti gli stessi ragazzi, sia pure in ordine diverso) per "farne
una sola",
MA DATA UNA QUATERNA ORDINATA, QUANTE SONO LE
QUATERNE ORDINATE AD ESSA EQUIVALENTI (COMPRESA
QUELLA DI PARTENZA)?
SONO TANTE QUANTI I MODI CON CUI, DATI 4 OGGETTI, ESSI
POSSONO ESSERE ORDINATI (= MESSI IN FILA)
Pertanto, fissata una quaterna ordinata, essa fa parte di un gruppo
di 4! quaterne equivalenti.
Il numero delle quaterne non ordinate di ragazzi interrogati sarà
(25·24·23·22)/ 4!= 12650
Introduzione
Il calcolo combinatorio - Quanti sono?
TERZA REGOLA (conseguenza delle precedenti)
Se in un dato problema ci interessano le n-uple NON
ordinate, dobbiamo pensare il nostro elenco di n-uple
ordinate ripartito in tanti gruppi, in ciascuno dei quali vi
sono le n-ple che contengono gli stessi elementi, anche
se in ordine diverso.
Abbiamo così tanti gruppi, ciascuno formato da n! n-uple, e
ciascun gruppo va contato "come se si trattasse di una
sola n-upla".
Allora
numero n - ple ordinate
numero n - ple non ordinate 
n!
Introduzione
Il calcolo combinatorio - Quanti sono?
Le disposizioni
Supponiamo di avere n oggetti distinti (ad es: n palline numerate
progressivamente da 1 a n, oppure n lettere dell'alfabeto, ... ).
Sia ora k un intero, k ≤ n.
Le k-uple (configurazioni con k elementi) ORDINATE che si possono
costruire utilizzando (senza ripetizione) k fra gli n oggetti dati sono
anche dette "le DISPOSIZIONI degli n elementi di classe k”.
Dn ,k  n  n  1    (n  k  1) 
Dn ,k 
n  n  1    (n  k  1)  (n  k )!
(n  k )!
n!
(n  k )!
Esempio: Ci sono 10 ragazzi, in quanti modi posso scegliere: un
portiere, un arbitro e un raccattapalle? 10!
10! 10  9  8  7!
D10,3 


 720
(10  3)! 7!
7!
Combinatoria in formule
Il calcolo combinatorio - Quanti sono?
Le combinazioni
Le k-uple NON ORDINATE che si possono costruire utilizzando (senza
ripetizione) k fra n gli oggetti dati sono anche dette
"le COMBINAZIONI degli n oggetti dati di classe k".
Cn , k 
Dn ,k
k!

n!
k!(n  k )!
tale passaggio è possibile anche per k = n ricordando che 0! =1
DA RICORDARE
 Disposizioni: configurazioni ordinate
 Combinazioni: configurazioni non ordinate
Esempio: Giocando a briscola, quante sono le possibili “mani” all’inizio
40! 40  39  38  37!
del gioco per un giocatore?
C 

 9880
40 , 3
Combinatoria in formule
Il calcolo combinatorio - Quanti sono?
37!3!
37!6
Le disposizioni con ripetizione
Si parla di "DISPOSIZIONI CON RIPETIZIONE" quando uno stesso
oggetto, nella k-upla ordinata, può essere ripetuto più di una volta.
In questo caso, non deve essere necessariamente k ≤ n.
Il numero delle disposizioni con ripetizione di n oggetti, presi a k a k, si
indica col simbolo
Dn ,k  n k
Esempio: Se si lanciano 10 monete (o anche: se si lancia una moneta
10 volte) quanti sono gli esiti possibili?
D2 ,10  210  1024
Combinatoria in formule
Il calcolo combinatorio - Quanti sono?
Le permutazioni
Le "PERMUTAZIONI DI n OGGETTI" sono tutte le n-uple ordinate
costruibili utilizzando, senza ripetizione, quegli oggetti;
Pn  n!
Esempio: Quanti sono gli anagrammi della parola PARCO
P5  5! 120
La funzione fattoriale può anche essere definita in modo ricorsivo:
se n  0
1
n! 
n  (n  1)! se n  0
Combinatoria in formule
Il calcolo combinatorio - Quanti sono?
Le permutazioni
Permutazioni di n oggetti non tutti diversi
Possiamo pensare alle "PERMUTAZIONI DI n OGGETTI NON TUTTI
DIVERSI“.
Presi n oggetti, dei quali m<n uguali fra loro, e gli altri tutti diversi l’uno
dall’altro e dai precedenti, quante n-uple ordinate distinguibili
potremo costruire utilizzando quegli n oggetti?
n!
Pn 
Esempio:
m!
Abbiamo 3 palline bianche identiche fra loro, 6 palline rosse identiche
fra loro e 5 palline verdi tutte identiche fra loro, quante sequenze
distinguibili potremo costruire con questi 3+6+5=14 oggetti?
n!
14!
Pn 

m1!m2 !m3! 3!6!5!
Combinatoria in formule
Il calcolo combinatorio - Quanti sono?
Le permutazioni
Esistono anche le "PERMUTAZIONI CICLICHE DI n OGGETTI".
Una "permutazione ciclica di n oggetti"è "uno dei modi in cui tali oggetti
possono essere disposti intorno ad un tavolo circolare, come se
fossero giocatori di carte".
E' evidente che la situazione
a
d
b
c
n!
coincide, in questo contesto, con ciascuna delle seguenti: Pn   ( n  1)!
n
d
a
c
b
c
d
b
a
b
c
a
d
Esempio: In quanti modi si possono disporre 5 giocatori di carte intorno
a un tavolo?
4! = 24
Combinatoria in formule
Il calcolo combinatorio - Quanti sono?
Il coefficiente binomiale
I numeri
Cn , k
n
n!

  
k!(n  k )!  k 
vengono anche detti “coefficienti binomiali”
Il coefficiente binomiale risponde alla domanda:
"dati n oggetti, in quanti modi ne posso scegliere k?"
Proprietà  n 
n
 n 
n
n  n 
   1 ;    n ; 
  n ;    1 ;    
 ;
0
1
 n  1
n
k  n  k 
 n   n  1  n  1
   
  

 k   k   k  1
Combinatoria in formule
Il calcolo combinatorio - Quanti sono?
Il binomio di Newton
Si chiama "binomio di Newton" la formula per lo sviluppo dell'n-esima
potenza di un binomio.
La formula è:
n
a  b n   a n 
0
Combinatoria in formule
 n  n 1
n
 a b    a n  2b 2   
1
 2
 n 
n

a b n 1   b n
 n  1
n
Il calcolo combinatorio - Quanti sono?
Problemi vari di combinatoria
Giochi di Archimede [22 novembre 2011]
Quanti sono i numeri palindromi di 5 cifre tali che la somma delle cifre
sia pari?
Il numero deve essere del tipo "abcba": 9 scelte per a x 10 scelte per b
x 5 scelte per c = 450 .
La prima cifra non può essere 0, altrimenti il numero sarebbe di 4 cifre,
nessuna limitazione per b. La somma delle cifre, esclusa la centrale
è pari, qualunque sia la parità delle prime due; infatti è pari sia la
somma di due pari, sia la somma di due dispari.
Dunque è la cifra c che assegna la parità al numero e quindi si hanno
solo 5 scelte.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Problemi vari di combinatoria
Giochi di Archimede - biennio [18 novembre 2009]
Carla sì è dimenticata la password di accensione del suo nuovissimo
computer. Si ricorda però che è una sequenza di 4 vocali, non
necessariamente distinte, di cui due sono maiuscole e due sono
minuscole. Quante password diverse deve provare Carla, al
massimo, per accendere il computer?
(A) 3 • 54 (B) 55 (C) 6 • 54 (D) 56 (E) 3 • 56.
Supponiamo che la pwd sia MMmm.
5 scelte per ciascuno vocale, quindi 54 ; oppure le disposizioni con
ripetizione nk .
Ora si deve anagrammare la parola MMmm, perché maiuscole e
minuscole possono essere in qualsiasi posizione e quindi, per la
formula delle permutazioni con ripetizione si ha 4!
4
6
6

5
2!2!
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Problemi vari di combinatoria
Giochi di Archimede [22 novembre 2011]
Alla Grande Cena … l’anno scorso c’erano 60 modi di
scegliere un pasto (primo + secondo). Quest’anno
verranno aggiunti dei primi e ci saranno 68 modi di
scegliere un pasto. Quanti primi c’erano, come minimo lo
scorso anno?
anno scorso: p scelte per il primo x s scelte per il
secondo p x s=60 quest’anno: (p+p’) x s = 68
Quindi (p+p’)/ p = 17/15 e quindi p’/p = 2/15.
Ovvero p = (15p’)/2
Il primo intero si ha per p’=2 ed è p=15.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Problemi vari di combinatoria
Gara di febbraio 2009
Nell'ultimo Capodanno, andavano molto di moda degli occhiali con la
forma del numero "2009" e le lenti al posto dei due zeri. Per
fabbricare occhiali simili, è necessario che nel numero che
rappresenta l'anno vi siano due o più zeri consecutivi (per esempio
3500 va bene, 2010 no). Quanti anni compresi tra l'anno 999 e
l'anno 9999 contengono due o più zeri consecutivi nella loro
scrittura? (A) 171 (B) 180 (C) 190 (D) 191 (E) 200.
Contiamo quanti sono gli anni che contengono due o più cifre zero
consecutive; per fare questo, consideriamo inizialmente in quali
posizioni possono essere le cifre zero e non-zero. Le possibilità
sono 3: XOOO, XXOO, XOOX (dove O rappresenta una cifra zero e
X rappresenta un non-zero)..
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Problemi vari di combinatoria
Gara di febbraio 2009
XOOO, XXOO, XOOX (dove O rappresenta una cifra zero e X
rappresenta un non-zero).
Infatti in prima posizione non ci può essere uno zero a causa
dell'intervallo di anni scelto. Ora, al posto di ogni X possiamo
sostituire una cifra tra 1 e 9, e ogni possibile, scelta "genera" un
anno valido. Quindi per la prima possibilità abbiamo 9 scelte, invece
per il secondo e per il terzo 9 • 9 = 81. In totale allora abbiamo 9 +
81 +81=171 ( anni validi).
Si noti che se invece avessimo contato il numero di modi in cui si può
sostituire una i cifra da 1 a 9 a X e una cifra da O a 9 a Y nei due
pattern XOOY e XYOO, avremmo ottenuto un risultato errato perché
avremmo contato due volte gli anni della forma XOOO.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Problemi vari di combinatoria
Gara di febbraio 2010
Antonio, Beppe, Carlo e Duccio si distribuiscono
casualmente le 40 carte di un mazzo, 10 a testa, Antonio
ha l'asso, il due e il tre di denari. Beppe ha l'asso di
spade e l'asso di bastoni. Carlo ha l'asso di coppe. Chi è
più probabile che abbia il 7 di denari?
(A) Antonio (B) Beppe (C) Carlo (D) Duccio (E) due o
più giocatori hanno la stessa probabilità di averlo.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Problemi vari di combinatoria
Gara di febbraio 2010
Intuitivamente, le posizioni delle carte rimanenti sono
equiprobabili, quindi è più probabile che il 7 di denari finisca a
Duccio "perché ha più spazio libero".
Più formalmente: contiamo i modi di distribuire 34 carte tra 4
persone, in modo che uno ne riceva 10, uno 9, uno 8 e uno 7;
possiamo distribuire ordinatamente 34 carte in 34! modi
diversi, ma questo viene diviso per 10!9!8!7! (la formula è la
stessa degli anagrammi con ripetizione). Quindi abbiamo P =
34! /(10!9!8!7!) casi possibili. Quante sono le configurazioni in
cui Antonio ha il 7 di denari?
Per un conto analogo sono PA = 33! /(10!9!8!6!)
PA/P = 7/34 ; PB/P = 8/34; PC/P = 9/34 ; PD/P = 10/34
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Problemi vari di combinatoria
Gara di febbraio 2011
Quanti sono i numeri interi positivi di 10 cifre abcdefghij, con tutte le
cifre diverse e che verificano le condizioni a+j=b+i=c+h=d+g=e+f=9
Nota: un numero non può iniziare con 0.
(A) 3456 (B) 3528 (C) 3645 (D) 3840 (E) 5040.
Chiamiamo, come nel testo, abcdefghij le 10 cifre del numero.
Per i numeri della forma richiesta, fissare le prime 5 cifre a, b, c, d, e
determina univocamente tutto il numero per la condizione imposta
(dato che possiamo ricavare f=9-e, a=9-d,...).
Dimenticandoci per ora del fatto che un numero non deve iniziare per
0, vediamo che a può essere scelta in 10 modi, b in 8 modi (tutte le
cifre, tranne a, già usata, e 9-a), c in 6, d in 4 ed e in 2 modi possibili
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Problemi vari di combinatoria
Da questi dobbiamo però togliere i numeri che iniziano con
la cifra zero. Essi sono 8 • 6 • 4 • 2 per lo stesso
ragionamento di prima (8 scelte per la cifra b, 6 per e, 4
per d e 2 per e).
La risposta al problema è quindi
10 • 8 • 6 • 4 • 2 - 8 • 6 • 4 • 2 = (10-1)* 8 • 6 • 4 • 2 = 3456.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
“Principio della cassettiera o della piccionaia”
Il principio della piccionaia
Il principio della piccionaia afferma che se p piccioni devono trovare
posto in c caselle e ci sono più piccioni che caselle (p>c) allora in
qualche casella entreranno almeno due piccioni.
Tale principio può essere descritto anche nel modo seguente.
Il principio della cassettiera
Se n oggetti sono collocati in k cassetti, e se n>k, allora almeno un
cassetto deve contenere almeno due oggetti.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
“Principio della cassettiera o della piccionaia”
Esempio.
Se ci sono 8 piccioni in 7 caselle, allora, poiché 8 > 7, almeno una
casella contiene almeno 2 piccioni.
Questo è un principio semplice ma di grande utilità.
Estensione del principio della piccionaia
Se p (piccioni) > n*c (caselle) per qualche intero n, allora almeno
una casella contiene n + 1 piccioni.
Esempio.
Se ci sono 27 piccioni in 8 caselle, allora, poiché 27 > 3*8, almeno
una casella contiene 3 + 1 = 4 piccioni.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
La peggiore delle ipotesi (worst case)
Calzini in una stanza buia
In un cassetto ci sono 10 paia di calzini marroni e 10 paia blu. Quanti calzini
devi prendere per essere sicuro di avere un paio di calzini dello stesso
colore?
E’ sufficiente pescare 3 calzini
Palline nere, rosse e bianche
In un cassetto ci sono 12 palline nere, 8 rosse e 6 bianche.
Pescando a caso, quante se ne devono prendere per essere sicuri di
averne 3 dello stesso colore?
Nella peggiore delle ipotesi, 6 palline non sono sufficienti. Infatti
potrebbero essere B-B-N-N-R-R. Supponiamo di essere arrivati a 6
palline senza averne 3 dello stesso colore. Visto che i colori sono 3,
alla settima estrazione si avranno almeno 3 dello stesso colore. In
conclusione bisogna pescarne almeno 7.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Partizioni di un intero e colorazioni
Problema:
In quanti modi si possono scegliere tre numeri a, b, c (non negativi) tali
che a+b+c=14 (da notare che 5+2+7 è diverso da 2+5+7)
Soluzione:
L’idea è che ad ogni modo di colorare 2 caselle su 16 corrisponde
univocamente un modo di scegliere 3 numeri che sommati formano
14.
16  16 15
  
 120
2
2
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Partizioni di un intero e colorazioni
In generale:
 n  k  1

  combinazio ni con ripetizion i di n  1 elementi
 k 1 
 n  k  1

in classe k - 1
Cn ,k  
 k 
E se fra gli addendi non ci può essere lo zero?
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Partizioni di un intero e colorazioni
Problema:
Dato un intero positivo, in quanti modi può essere espresso come
somma di k interi maggiori o uguali di 1? (L’ordine conta!)
Ad esempio: In quanti modi 8 è somma di quattro addendi?
Diventa: in quanti modi disporre 3 segmenti colorati su 7?
Risposta:  7 
 3
In generale
Problemi vari di combinatoria
 n  1

  combinazio ni di n - 1 segmentini interni
 k  1
in classe k - 1
Il calcolo combinatorio - Quanti sono?
Principio di inclusione - esclusione
Problema:
In una classe con 30 studenti. Tutti suonano almeno uno strumento. 20
alunni suonano il piano e 16 la chitarra. Quanti entrambi?
Soluzione:
30 = 20 + 16 – x
x=6
A B  A  B  A B
Ritroviamo
Problema Olimpiadi 1998 (biennio):
In una classe di 20 persone, 15 giocano a calcio, 14 a basket e 13 a
pallavolo. Quanti sono, al minimo, che praticano tutti e 3 gli sport?
Soluzione:
5 persone non giocano a calcio, 6 non giocano a basket, 7 non giocano
a pallavolo. Al massimo sono 5 + 6 + 7 =18. Quindi almeno 2
ragazzi devono praticare tutti e tre gli sport.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Divisori di un intero positivo
Problema:
Quanti sono i divisori di 2012?
Soluzione:
Fattorizzo 22 x 503
Come è un divisore di 2012? 2a x 503b
Con a = 0, 1, 2 b= 0, 1
Pertanto si avranno 3 scelte per a e 2 scelte per b.
In totale
3 2  6



1
2
n
In generale: Se n  p1  p2    pn
(1  1)  ( 2  1)   ( n  1)
I divisori di n sono
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Invarianti
Per risolvere alcuni problemi di combinatoria può essere
utile ricorrere agli invarianti, cioè una quantità che non
cambia durante un procedimento.
Ad esempio: su una lavagna sono scritti 10 numeri. Ad
ogni turno si aggiunge 1 ad un numero e si toglie 1 da un
altro. Invariante è la somma dei numeri.
Oppure su una lavagna sono scritti 10 numeri. Ad ogni
turno si aggiunge o si toglie 1 da 2 numeri. Invariante è
la parità della somma dei numeri.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
Invarianti
Problema:
Ci sono tre sacchetti: A con 2000 palline, B con 3000
palline e C con 4000 palline. Posso fare 2 mosse:
prendere due palline da un sacchetto e metterle una in
ciascuno dei restanti sacchetti oppure prendere due
palline da due sacchetti distinti e metterle nel terzo.
Si può giungere ad avere 3000 palline in ogni sacchetto?
Considero la differenza fra le palline di due sacchetti.
Essa resta costante o aumenta di 3.
Pertanto partendo da 1000 o 2000 non può arrivare a 0.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
E… il senso comune?
Quesito n.7 (EdS 2010):
Per la ricorrenza della festa della mamma, la sig.ra Luisa
organizza una cena a casa sua, con le sue amiche che hanno
almeno una figlia femmina. La sig.ra Anna è una delle invitate
e perciò ha almeno una figlia femmina. Durante la cena, la
sig.ra Anna dichiara di avere esattamente due figli. Si chiede:
qual è la probabilità che anche l’altro figlio della sig.ra Anna
sia femmina? Si argomenti la risposta.
Anna ha esattamente due figli di cui almeno una femmina.
Le possibili coppie ordinate (per il primo e secondo figlio) sono:
MF -FM -FF
La probabilità che entrambi i figli siano femmine è 1/3.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
E… il senso comune?
Il paradosso di Monty Hall
Il problema di Monty Hall è un famoso problema legato al gioco a premi
americano “Let’s make a deal”. Prende il nome da quello del
conduttore dello show, noto con lo pseudonimo di Monty Hall.
Nel gioco vengono mostrate al concorrente tre porte chiuse; dietro ad
una si trova un’automobile, mentre ciascuna delle altre due
nasconde una capra. Il giocatore può scegliere una delle tre porte
vincendo il premio corrispondente. Dopo che il giocatore ha
selezionato una porta, ma non l’ha ancora aperta, il conduttore dello
show (che sa cosa si trova dietro ogni porta) apre una delle altre
due mostrando una delle due capre, e offre al giocatore la possibilità
di cambiare la scelta iniziale passando all’unica porta chiusa.
Si tratta di capire se al concorrente conviene cambiare la scelta.
Ce lo spiega Kevin Spacey dal film 21 Il Problema di Monty Hall
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?
E… il senso comune?
Il paradosso di Monty Hall
Contiamo le tre situazioni possibili, ciascuna avente
probabilità 1/3:
1. Il giocatore sceglie la capra numero 1. Il conduttore
sceglie l'altra capra. Cambiando, il giocatore vince
l'auto.
2. Il giocatore sceglie la capra numero 2. Il conduttore
sceglie l'altra capra. Cambiando, il giocatore vince
l'auto.
3. Il giocatore sceglie l'auto. Il conduttore sceglie una
capra, non importa quale. Cambiando, il giocatore trova
l'altra capra.
Problemi vari di combinatoria
Il calcolo combinatorio - Quanti sono?