COMBINATORIA E PROBABILITA` - liceo scientifico gaetano salvemini

Liceo Scientifico “G. Salvemini”
Corso di preparazione per la gara provinciale delle
OLIMPIADI DELLA MATEMATICA
INTRO
COMBINATORIA E PROBABILITA’
CALCOLO COMBINATORIO
Il Calcolo Combinatorio
è lo studio dei diversi modi di ordinare o estrarre oggetti.
Esempi di problemi risolvibili con il CALCOLO COMBINATORIO
QUANTI SONO I TERNI AL LOTTO ?
IN QUANTI MODI DIVERSI SI POSSONO SEDERE GLI INVITATI AD UNA CENA?
QUANTE PAROLE SI POSSONO FORMARE CON LE LETTERE DI “ROMA” ?
QUANTE DELEGAZIONI DI 4 ALUNNI SI POSSONO FORMARE IN UNA CLASSE DI 20
ALUNNI ?
ECC..
QUESITO
SUGGERIMENTO
L’ultima cifra è sicuramente pari.
Distinguiamo a seconda se questa sia quella doppia o no.
Contiamo, nei due casi, quante sono le possibili posizioni
delle due cifre pari uguali e quella della cifra dispari.
Otteniamo i casi possibili che vanno moltiplicati per le
possibili combinazioni al variare delle cifre..
SOLUZIONE
L’ultima cifra è sicuramente pari. Distinguiamo a seconda se questa sia quella doppia o no.
Nel primo caso l’altra cifra doppia può occupare 3 diverse posizioni (non la 4) e per ciascuna
di queste la cifra dispari può occupare una qualunque delle 3 posizioni rimanenti.
Nel secondo caso le due cifre uguali possono disporsi in 3 modi diversi (1 e 3, 1 e 4, 2 e 4) e
per ciascuno di questi la cifra dispari può occupare 2 posizioni tra le 3 libere (non la 5).
In tutto si hanno 33 + 32 = 15 modi di fissare le posizioni delle due cifre uguali e della cifra
dispari.
Per ciascuno di questi modi si possono scegliere liberamente la cifra dispari (5 casi), la cifra
pari doppia (5 casi), la prima e la seconda delle cifre pari singole (4 e 3 casi rispettivamente),
per un totale di 155543 = 4500 combinazioni differenti che rispettano le richieste.
DISPOSIZIONI SEMPLICI
Dati n oggetti distinti, si dicono disposizioni semplici
di classe k ( n), tutte le possibili file che si possono
formare con k degli n oggetti, considerando distinte
due file che differiscono per l’ordine o per qualche
elemento (gli oggetti non si possono ripetere)
disposizioni di n oggetti a k a k
Dn,k = n·(n-1)·…·(n-k+1)
Esempio
In una gara con 8 atleti quanti sono i
possibili ordini di arrivo ?
Dn,k = n·(n-1)·…·(n-k+1)
D8,3 = 8·7·6 = 336
Esempi
Quanti numeri di 2 cifre si possono
scrivere con 4 cifre (senza ripeterle) ?
D4,2 = 4·3 = 12
Quante squadre può formare un
allenatore che ha a disposizione una
rosa di 18 giocatori ?
(nell’ipotesi che ogni giocatore possa
occupare un ruolo qualsiasi)
D18,11 = 18·17·16·15.. ·9·8 = 1.270.312.243.200
Il mestiere di allenatore non sembra agevole!
PERMUTAZIONI SEMPLICI
Le permutazioni sono le disposizioni di n oggetti a n a n
Pn = Dn,n = n·(n-1)·…·2·1
Il prodotto dei numeri da 1 ad n si chiama
n fattoriale e si indica con n!
Pn = n!
0! = 1
Esempi
Quanti sono gli anagrammi della parola
AMORE ?
P5 = 5! = 5·4·3·2·1 = 120
Quanti numeri di 4 cifre si possono
scrivere con 4 cifre (senza ripeterle) ?
P4 = 4! = 4·3·2·1 = 24
Quante sono le possibili configurazioni nelle
assegnazioni dei posti di una classe di 15 alunni ?
P15 = 15! = 1.307.674.368.000
PERMUTAZIONI CON RIPETIZIONE DI OGGETTI
Dati n oggetti in cui k di essi (k<n)
si ripetono r1,r2, .. rk volte,
calcoliamo con la seguente formula il numero della
permutazioni
tenendo conto che lo scambio di posizione tra oggetti
uguale rende equivalente la permutazione:
Prn=
n!
r1! r2 !..rk !
Esempi
Quanti sono gli anagrammi della parola MATTATOIO ?
(anche di senso non compiuto)
Pr9 =
9!
3!4  5  6  7  8  9

 5  6  7  8  9  15.120
3!2!2!
3!4
Quanti numeri si possono formare con le cifre 1223334444 ?
Pr10 =
10!
4!5  6  7  8  9 10

 5  7  4  9 10  12.600
2!3!4!
2!3!4!
COMBINAZIONI SEMPLICI
Dati n oggetti distinti, si dicono combinazioni semplici
di classe k ( n), tutte i possibili gruppi che si possono formare con
k degli n oggetti, considerando distinti due gruppi se differiscono
per almeno un elemento.
(non è importante l’ordine e gli oggetti non si possono ripetere)
combinazioni di n oggetti a k a k
Cn,k=
=
Coefficiente binomiale
Esempio
Quanti sono i possibili terni
all’estrazione del lotto?
C90,3=
=
15
=
= 117.480
Esempio
Quante sono le possibili coppie di
rappresentanti di una classe di 20
alunni?
C20,2=
=
10
=
= 190
File e gruppi con ripetizione
Se nella formazione di file e gruppi è possibile
ripetere gli oggetti si usano le seguenti formule:
Drn,k =
Crn,k=
k
n
Esempio
Quanti numeri di 3 cifre si possono formare con 4
cifre eventualmente ripetendo una cifra ?
Dr4,3 =
Dr4,7 =
7
4
3
4
= 64
NB – La formula
Drn,k si può utilizzare
anche quando k > n !
Esempio
Mescolando 4 vernici tra di loro, in
quantita’ uguali, eventualmente anche
ripetendo uno o più colori, quante
gradazioni si possono ottenere ?
Cr4,4=
=
= 35
EVENTI ALEATORI
Un EVENTO ALEATORIO
è un evento, legato ad un determinato fenomeno,
il cui verificarsi può avere più di un caso
Esempi di eventi aleatori: il lancio di un dado,
l’estrazione di un carta da un mazzo,
l’estrazione di numeri al lotto, ecc.
ALEATORIO è il risultato del dado lanciato, la
carta estratta, il numero estratto.
CALCOLO DELLE PROBABILITA’
Il Calcolo delle probabilità
è lo studio degli eventi
aleatori e della previsione
del loro verificarsi.
CALCOLO DELLE PROBABILITA’
Si definisce lo SPAZIO DEGLI EVENTI
l’insieme di tutti gli eventi aleatori possibili
di un determinato fenomeno.
Uno SPAZIO DEGLI EVENTI
può avere anche una dimensione infinita.
Consideriamo soprattutto spazi degli eventi finiti i
cui possibili risultati siano determinabili a priori
DEFINIZIONE DI PROBABILITA’
Sia E un evento aleatorio appartenente ad
uno SPAZIO DEGLI EVENTI finito.
Si definisce PROBABILITA’ di E il RAPPORTO tra i
casi favorevoli all’evento e il numero di tutti i
casi possibili dello SPAZIO DEGLI EVENTI.
Esempio
Qual’e la probabilità che esca 5
al lancio di un dado ?
P(E1) = 1/6
Qual’e la probabilità che non escano
3 o 5 al lancio di un dado ?
P(E2) = 4/6 = 2/3
Esempio
Qual è la probabilità che esca 7
nel lancio di due dadi ?
1
2
3
4
5
1
7
2
P(E) = 6/36 = 1/6
7
3
7
4
7
5
6
6
7
7
QUESITO
SUGGERIMENTO
La lancetta delle ore è orizzontale se l’orologio
segna le 3 o le 9. Per qualsiasi posizione
raggiunta prima dell’ultimo lancio abbiamo ..
SOLUZIONE
La lancetta delle ore è orizzontale se l’orologio segna le 3 o
le 9. Per qualsiasi posizione raggiunta prima dell’ultimo
lancio abbiamo 1 risultato utile su 6 per raggiungere o il 9
(fig 1) o il 3 (fig 2). Quindi la probabilità è 1/6 .
Fig. 1
Fig. 2
QUESITO
SUGGERIMENTO
Si consideri la scacchiera colorata
come in figura; un passo della
pedina può solo condurla da una
casella bianca a una casella grigia, e
viceversa: ne consegue che, dopo
un numero dispari di passi, ..
SOLUZIONE
Si consideri la scacchiera colorata come in figura;
un passo della pedina può solo condurla da una
casella bianca a una casella grigia, e viceversa: ne
consegue che, dopo un numero dispari di passi, la
pedina non può che trovarsi in una delle quattro
caselle bianche.
Qualunque sia la casella bianca in cui la pedina si
trova dopo 11 passi, vi sono 4 caselle che essa può
raggiungere con il dodicesimo passo, una sola
delle quali è un casella d'angolo. La probabilità
che la pedina si trovi in un angolo dopo 12 passi
(cos come dopo un qualunque numero positivo
pari di passi) e quindi 1/4.
PROBABILITA’ ED INSIEMISTICA
Consideriamo un evento E di
uno spazio degli eventi S ed
il suo complementare E.
S
p(S) = 1
EVENTO CERTO
p() = 0
EVENTO IMPOSSIBILE
p(E) + p(E) = 1
p(E) = 1 – p(E)
E
E
Esempio
Qual è la probabilità che non
escano monete uguali nel
lancio di tre monete ?
P(E) = 1 – P(E) = 1 - 2/8 = 3/4
M1
M2
M3
T
T
T
C
C
C
C
C
T
T
C
T
C
T
T
C
T
C
T
T
T
C
T
C
UNIONE ED INTERSEZIONE DI EVENTI
E1
E2
S
p(E1  E2) = p(E1) + p(E2) – p(E1  E2)
Due eventi sono incompatibili se
E1  E2 = 
p(E1  E2) = p(E1) + p(E1)
E1
S
E2
Esempio
Qual è la probabilità che estraendo una carta da un mazzo di
52 carte sia una figura o una carta di cuore ?
E1 = “Si estrae una figura”
(12 possibilità)
E2 = “Si estrae una carta di cuori”
(13 possibilità)
E1  E2 = “Figure di cuori”
(3 possibilità)
P(E1  E2) = P(E1 ) + P(E2) – P(E1  E2) =
12/52 + 13/52 – 3/52 = 22/52 = 11/26
PROBABILITA’ COMPOSTA – EVENTI INDIPENDENTI
Due eventi si dicono indipendenti se il verificarsi
dell’uno non condiziona il verificarsi dell’altro
Ad esempio l’estrazione di squadre
per un sorteggio di coppa.
Ad esempio l’estrazione successiva di
carte da un mazzo con reinserimento.
PROBABILITA’ COMPOSTA – EVENTI INDIPENDENTI
Si può facilmente dimostrare che se
due eventi sono indipendenti vale:
P(E1  E2) = P(E1 ) · P(E2)
PROBABILITA’ COMPOSTA – EVENTI INDIPENDENTI
Qual è la probabilità che due squadre
inserite in due urne distinte di 4
squadre siano estratte insieme ?
P(E1  E2) = P(E1 ) · P(E2) = 1/4 ·1/4 = 1/16
Qual è la probabilità che in tre
estrazioni successive con
reinserimento siano estratti 3 assi ?
P(E1  E2  E3) = P(E1 ) · P(E2) · P(E3) =
1/13 ·1/13 ·1/13 = 1/2197
QUESITO
Matteo deve fare un test a crocette con
11 domande. Ciascuna domanda ha una
sola risposta giusta. La prima domanda ha
2 possibili risposte (A e B), la seconda
domanda ha 3 possibili risposte (A, B, C),
e così via, fino all'undicesima domanda
che ha 12 possibili risposte. Qual è la
probabilità che facendo a caso il test
Matteo dia almeno una risposta giusta ?
SUGGERIMENTO
Matteo deve fare un test a crocette con 11 domande. Ciascuna domanda ha
una sola risposta giusta. La prima domanda ha 2 possibili risposte (A e B), la
seconda domanda ha 3 possibili risposte (A, B, C), e così via, fino all'undicesima
domanda che ha 12 possibili risposte. Qual è la probabilità che facendo a caso il
test Matteo dia almeno una risposta giusta ?
SOLUZIONE
Matteo deve fare un test a crocette con 11 domande. Ciascuna domanda ha
una sola risposta giusta. La prima domanda ha 2 possibili risposte (A e B), la
seconda domanda ha 3 possibili risposte (A, B, C), e così via, fino all'undicesima
domanda che ha 12 possibili risposte. Qual è la probabilità che facendo a caso il
test Matteo dia almeno una risposta giusta ?
PROBABILITA’ CONDIZIONALE
In altri casi il verificarsi di un evento dipende dal
verificarsi di un altro.
Ad esempio qual è la probabilità che
estratto un asso da un mazzo se ne
estragga un altro ?
F = Si estrae il primo asso dal mazzo
E = Si estrae il secondo asso dal mazzo senza reinserire il primo
PROBABILITA’
DI E DATO F
P(E/F) = 3/51
PROBABILITA’ CONDIZIONALE
Vale:
Esempio: Si deve sorteggiare un alunno con un profitto
almeno discreto di una classe di 25 alunni. La classe è
composta da 10 ragazze tra le quali 6 alunne su un totale
di 13 alunni con profitto almeno discreto.
Qual è la probabilità di scegliere una ragazza ?
P(Estrarre una ragazza / Scelto un alunno con profitto almeno discreto) =
INTERSEZIONE DI EVENTI DIPENDENTI
Dalla formula della probabilità condizionale si può ricavare:
P(E  F) = P(F) · P(E / F)
Esempio: Qual è la probabilità che da un
mazzo di carte siano estratte due figure
(senza reinserire la prima carta) ?
F = Si estrae la prima figura dal mazzo
E = Si estrae la seconda figura dal mazzo senza reinserire la prima
P(E/F) = 11 / 51
P(E  F) = P(F) · P(E / F) =
3/13 · 11/51 = 11/221
PROVE RIPETUTE
Consideriamo una evento aleatorio che si ripete n volte.
Sia p la probabilità che l’evento abbia risultato E
La probabilità che E si verifichi k volte su n è:
QUESITO
SUGGERIMENTO
Considera separatamente i casi in cui Nicola abbia
rispettivamente perso e vinto l’ultima partita.
Nel primo caso (che avviene con probabilità 1/3) Nicola deve aver
vinto le prime quattro partite ..
Nel secondo caso (che avviene con probabilità 2/3), Nicola deve
non aver perso più di due partite tra le prime quattro:
quest’ultimo evento ha probabilità complementare rispetto a
quella di perdere tutte le prime quattro partite, o di vincerne
esattamente una su quattro ..
SOLUZIONE
QUESITO A RISPOSTA NUMERICA
Un cavallo è posto in una casella
d'angolo di una scacchiera 3 x 3. Una
mossa consiste nello spostare il cavallo
in una casella raggiungibile mediante
due passi in orizzontale seguiti da un
passo in verticale, o due passi in
verticale seguiti da un passo in
orizzontale. In quanti modi è possibile
spostarlo nella casella d'angolo
opposta, con esattamente 12 mosse?
SUGGERIMENTO
Osserviamo che il cavallo si muoverà sempre su caselle adiacenti al
perimetro della scacchiera (tutte tranne quella centrale) e che da ogni
casella sono possibili due mosse: una che porta il cavallo avanti di 3
caselle sul perimetro in senso orario, e una che lo sposta di 3 caselle in
senso antiorario.
Se si numerano le caselle del perimetro della scacchiera da 1 a 8 in
senso orario, dove la casella 1 è quella di partenza, le mosse del cavallo
possono essere rappresentate come nella figura che segue: ciascuna
mossa porta il cavallo dal vertice dell'ottagono corrispondente alla
casella in cui si trova a uno dei due adiacenti, a seconda che sia in senso
orario o antiorario.
Per arrivare all'angolo opposto, il cavallo deve spostarsi in totale di 4 posizioni
sull'ottagono, più eventualmente di un numero intero di giri dell'ottagono (8
mosse in senso orario o antiorario riportano il cavallo sulla casella di partenza).
Sia x il numero di mosse effettuate in senso orario, y il numero di mosse
effettuate in senso antiorario; dobbiamo contare il numero di percorsi possibili
in cui x + y = 12 (si compiono 12 mosse in totale) e x - y è un numero della
forma 8k+4 (con k intero) ..
SOLUZIONE
Per arrivare all'angolo opposto, il cavallo deve spostarsi in totale di 4
posizioni sull'ottagono, più eventualmente di un numero intero di giri
dell'ottagono (8 mosse in senso orario o antiorario riportano il cavallo
sulla casella di partenza).
Per arrivare all'angolo opposto, il cavallo deve spostarsi in totale di 4 posizioni sull'ottagono,
più eventualmente di un numero intero di giri dell'ottagono (8 mosse in senso orario o
antiorario riportano il cavallo sulla casella di partenza).
Sia x il numero di mosse effettuate in senso orario, y il numero di mosse effettuate in senso
antiorario; dobbiamo contare il numero di percorsi possibili in cui x + y = 12 (si compiono 12
mosse in totale) e x - y è un numero della forma 8k+4 (con k intero). Le coppie ordinate di
soluzioni possibili (con x e y non negativi) sono le seguenti: x = 12, y = 0; x = 0, y = 12; x = 8,
y = 4; x = 4, y = 8. Le prime due coppie rappresentano i due percorsi in cui il cavallo fa tutte
le mosse in senso orario o antiorario.
Le altre due coppie rappresentano percorsi in cui vengono fatte 8 mosse in senso orario e 4
in senso antiorario, o viceversa; il numero di tali percorsi è dato dal numero di modi in cui è
possibile scegliere l'ordine delle mosse: in particolare, si tratta di
in entrambi i casi (fra
le 12 mosse da effettuarsi, dalla prima alla dodicesima, vanno scelte le 4 che saranno svolte
in senso antiorario nel primo caso, orario nel secondo).