Il Paradosso dei compleanni
e … la pirateria informatica
Autori:
BARRETTA DOMENICO
CASCARINO ROBERTA
CICCARELLI SARA
DI GIROLAMO VINCENZA
DI MAIOLA ANNA
DI NARDO ILARIA
GALLARELLO SIMONE
GIORDANO VINCENZA
GRANATA FEDERICA
GRANATA GIUSY
Autori:
MAURIELLO TONYA
ORDINE LEOPOLDO
D’ALTERIO CARLO
PUGLIESE FRANCESCO
RUSSO PASQUALE
SOZIO PIERLUIGI
TRINCHILLO MARIA
GIUSEPPINA
Prof.
MALLARDO ANGELA
PIANESE SERAFINA
PARADOSSO:
Dal greco παρά (contro) e δόξα (opinione) ovvero
andare contro l’opinione comune (quella più diffusa)
L’EVENTO ALLA BASE DEL PARADOSSO DEI COMPLEANNI:
«In un insieme G di N persone c’è almeno una coppia
costituita da persone nate
nello stesso giorno e nello stesso mese.»
In tale contesto, non si considera il giorno dell’anno bisestile e si considerano
equiprobabili i 365 giorni dell’anno rispetto alla nascita di una persona. Inoltre d’ora in
poi consideriamo i giorni dell’anno numerati da 1 (1 Gennaio) fino a 365 (31 Dicembre) in
modo da eliminare il riferimento al mese.
Nel paradosso dei compleanni emerge in maniera del tutto
spontanea la questione della determinazione del minimo
intero N per il quale l’evento considerato risulta avere
probabilità
IDEA INTUITIVA:
l’opinione comune suggerisce che il gruppo debba essere
formato da almeno:
183 (>365/2)
persone.
MA è proprio così
?
•
•
•
P Ω =1
P 𝐸 ≥0
se gli eventi 𝐸1 , 𝐸2 , ⋯ , 𝐸𝑛 sono a due a due incompatibili
(𝐸𝑖 ∩ 𝐸𝑗 = ∅ per 𝑖 ≠ 𝑗)
P(𝐸1 ∪ 𝐸2 ∪ ⋯ ∪ 𝐸𝑛 ) = P(𝐸2 ) + P 𝐸2 + ⋯ + P 𝐸𝑛
In particolare
P(𝐸)= 1 – P(𝐸)
•
la legge del prodotto
P(𝐸1 ∩ 𝐸2 ∩ ⋯ ∩ 𝐸𝑛 ) = P(𝐸1 ) ∙ P(𝐸2 |𝐸1 ) ∙ ⋯ ∙ P(𝐸𝑛 |𝐸1 ∩ 𝐸2 ∩ ⋯ ∩ 𝐸𝑛−1 )
Si supponga ora di aver, in qualche modo, ordinato le
persone dell’insieme 𝐺 per cui si può parlare della
prima persona, della seconda persona e così via.
Inoltre, consideriamo i seguenti eventi:
𝑬𝟏 : «la prima persona è nata in un qualsiasi
giorno dell’anno»
e, per 2 ≤ 𝑘 ≤ 𝑁 ,
𝐄𝐤 : «la 𝐤-ima persona è nata in un giorno diverso
dai giorni di nascita delle persone a lei
precedenti».
In una situazione come quella che stiamo
considerando (ricordiamo che abbiamo supposto
«equiprobabili» i 365 giorni dell’anno rispetto alla
nascita di una persona) si può adottare la definizione
classica di probabilità:
per ogni evento 𝐸,
P(𝑬) =
𝒏𝒖𝒎𝒆𝒓𝒐 𝒅𝒊 𝒄𝒂𝒔𝒊 𝒇𝒂𝒗𝒐𝒓𝒆𝒗𝒐𝒍𝒊 𝒂𝒍𝒍′ 𝒆𝒗𝒆𝒏𝒕𝒐 𝑬
𝒏𝒖𝒎𝒆𝒓𝒐 𝒅𝒊 𝒄𝒂𝒔𝒊 𝒑𝒐𝒔𝒔𝒊𝒃𝒊𝒍𝒊
Fornisce immediatamente la probabilità 1 − 𝑝
dell’insieme 𝐺 sono nate tutte in giorni differenti:
che le 𝑁
persone
1 − 𝑝 = P(𝐸1 ∩ 𝐸2 ∩ ⋯ ∩ 𝐸𝑁 )
= P(𝐸1 ) ∙ P(𝐸2 |𝐸1 ) ∙ ⋯ ∙ P(𝐸𝑛 |𝐸1 ∩ 𝐸2 ∩ ⋯ ∩ 𝐸𝑁−1 )
=
365 364
∙
∙
365 365
⋯∙
365− 𝑁−1
365
=
365!
.
365−𝑁 !∙365𝑁
Pertanto, passando all’evento negato, la probabilità 𝑝 che ci sia almeno una
coppia costituita da persone nate nello stesso giorno vale:
𝑝 = 1 − P 𝐸1 ∩ 𝐸2 ∩ ⋯ ∩ 𝐸𝑁
= 1−
365 364
365 − 𝑁 − 1
∙
∙ ⋯∙
=1−
365 365
365
365!
.
𝑁
365 − 𝑁 ! ∙ 365
La tabella seguente riporta i valori di 𝑝 per alcuni valori di 𝑁
2
0,00274
24
0,53834
10
0,11695
30
0,70362
15
0,25290
40
0,89123
19
0,37912
50
0,97037
20
0,41144
60
0,99412
21
0,44369
70
0,99916
22
0,47570
80
0,99991
23
0,50730
90
0,99999
Basta che l’insieme 𝐺 sia formato da soltanto
23 persone, per avere
maggiore di 1/2
la probabilità di trovare almeno una coppia di
persone nate lo stesso giorno.
Da una indagine dell’espresso Web in un articolo del 19
gennaio 2008 esaminando le 43 date di nascita e 39 di
morte di Presidenti americani
Polk e Harding nacquero il:
2 novembre
Carter e Heisenhower nacquero il
14 ottobre;
Truman e Ford morirono il
26 dicembre,
Polk e Buchanan morirono il
15 giugno
tre presidenti, Jefferson, Adams e
Monroe, morirono il
4 luglio.
Crittografare un messaggio significa
«nascondere» l’informazione utilizzando una
«chiave».
Ipotizziamo che:
 un certo messaggio sia codificato con stringhe
numeriche di 4 elementi.
 Per nasconderle si provveda a moltiplicare tutti
i numeri della stringa per un intero lungo un
byte (8 bit)
Se la stringa è 4 7 5 6, che nel sistema binario si
esprime come:
0
0
0
0
0
1
0
0
4
0
0
0
0
0
1
1
1
7
0
0
0
0
0
1
0
1
5
0
0
0
0
0
1
1
0
6
Essa attraverso un intero K detto chiave viene trasformata
in una nuova stringa detta crittogramma.
Per esempio quella che si ottiene
moltiplicando tutti i numeri per 8 sarà
0
0
0
0
0
1
0
0
4
0
0
0
0
0
1
1
1
7
0
0
0
0
0
1
0
1
5
0
0
0
0
0
1
1
0
6
x8
(Chiave)
0
0
1
0
0
0
0
0
32
0
0
1
1
1
0
0
0
56
0
0
1
0
1
0
0
0
40
0
0
1
1
0
0
0
0
48
Crittogramma
Ipotesi:
Se un messaggio contiene due
crittogrammi codificati con la stessa
chiave esso è decifrabile.
Un hacker (pirata informatico) vuole:
assegnato un blocco di crittogrammi
trovare due stringhe codificate con la
stessa chiave.
Sapendo che le possibili chiavi che si ottengono con 1
byte sono:
28 =256
abbiamo calcolato la probabilità che,
Presi n crittogrammi, tra questi n ce ne siano almeno
due generati dalla stessa chiave k.
La probabilità è data dalla formula:
P(n)=𝟏 −
𝟐𝟓𝟔!
𝟐𝟓𝟔−𝒏 !(𝟐𝟓𝟔)𝒏
Utilizziamo un foglio di calcolo per determinare la
funzione che caratterizza questa probabilità
probabilità Attacco
1.2
1
0.8
0.6
0.4
0.2
0
0
20
40
60
80
100
Con soltanto 20 Crittogrammi ha una probabilità
maggiore del 50% di trovare stringhe codificate con
la stessa chiave e dunque vista l’ipotesi fatta
decifrare la chiave di accesso.
Con 40 Crittogrammi tale probabilità sarebbe
addirittura maggiore del 90%.
Ringraziamo i professori Aniello Buonocore e Luigia
Caputo per aver con estrema professionalità suscitato il
nostro interesse riguardo al calcolo delle probabilità,
argomento a noi non noto, nonché per la collaborazione e
la disponibilità mostrata durante la stesura della
presentazione.