P IRATI E MONETE D ’ ORO
B ONUS : OCCHI AZZURRI
Andrea Caranti
Dipartimento di Matematica
Università degli Studi di Trento
science.unitn.it/∼caranti
Rosmini, Rovereto, 15 maggio 2012
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
1 / 42
S OMMARIO
1
I L PROBLEMA
Pirati e monete
2
R AGIONARE DA PIRATI
Come ragionano i pirati
E quando i pirati sono tanti?
3
B IBLIOGRAFIA
4
O CCHI AZZURRI
Occhi azzurri
Soluzione?
Common Knowledge
Mario Draghi
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
2 / 42
I L PROBLEMA
P IRATI E MONETE
C INQUE PIRATI E CENTO MONETE
Cinque pirati devono dividere cento monete d’oro.
Per farlo, seguono regole molto precise.
I pirati sono in grado di fare qualsiasi ragionamento logico.
Inoltre sono razionali.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
4 / 42
I L PROBLEMA
P IRATI E MONETE
P IRATI RAZIONALI
Questo vuol dire che i pirati sono mossi, rigorosamente nell’ordine in
cui sono enunciati, da questi desideri.
1
Ogni pirata vuole sopravvivere.
2
Ogni pirata vuole avere più oro possibile.
3
Ogni pirata vuole far fuori altri pirati.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
5 / 42
I L PROBLEMA
P IRATI E MONETE
P OI NATURALMENTE AI PIRATI PIACE FARE
BALDORIA . . . !
Fonte: http://en.wikipedia.org/wiki/File:BartRobCrew.jpg
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
6 / 42
I L PROBLEMA
P IRATI E MONETE
C ATTIVERIA
Come avete capito, i pirati sono tutti cattivissimi, ma non tutti allo
stesso modo.
Fra i pirati esiste un preciso ordine di cattiveria, noto a tutti i pirati.
Il pirata più cattivo lo chiamiamo P5, quello un po’ meno cattivo,
ma sempre più cattivo di tutti i rimanenti, lo chiamiamo P4, e cosí
via fino al meno cattivo (si fa per dire), che chiamiamo P1.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
7 / 42
I L PROBLEMA
P IRATI E MONETE
L E REGOLE
Il pirata più cattivo dei cinque, dunque P5, propone agli altri un
modo di dividere le 100 monete.
Si vota. (Vota anche il proponente.)
Se almeno la metà dei pirati è d’accordo, le monete vengono
divise secondo la proposta. (Basta esattamente la metà dei voti.)
Altrimenti il proponente viene buttato a mare, e i rimanenti
ripetono la procedura.
Dunque P4 fa una proposta, su cui si vota, ecc.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
8 / 42
I L PROBLEMA
P IRATI E MONETE
C OME DIVIDERE LE MONETE ?
Quale proposta di divisione delle 100 monete deve fare P5?
Avendo in mente che
1
2
3
ogni pirata (lui in particolare) vuole sopravvivere;
ogni pirata (lui in particolare) vuole avere più oro possibile;
ogni pirata vuole far fuori altri pirati.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
9 / 42
I L PROBLEMA
P IRATI E MONETE
M ONETE D ’ ORO !
Fonte: http://en.wikipedia.org/wiki/File:Pyle_pirates_burying2.jpg
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
10 / 42
R AGIONARE DA PIRATI
C OME RAGIONANO I PIRATI
DA CHE PARTE COMINCIAMO ?
Nello scegliere il proprio comportamento, ogni pirata valuterà le
conseguenze del suo voto, in particolare cosa succede se vota
contro, e come conseguenza P5 muore.
In tal caso rimangono quattro pirati. Dunque anche se il problema
è per cinque pirati, occorre chiedersi cosa succede con quattro, e
per la stessa ragione con tre, due, uno. . .
Questo è un classico approccio a questo genere di problemi.
Dobbiamo dapprima chiederci cosa succede con un numero più
piccolo di pirati.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
12 / 42
R AGIONARE DA PIRATI
C OME RAGIONANO I PIRATI
U N PIRATA , DUE PIRATI . . .
Se c’è solo un pirata P1, questo si tiene tutti i soldi, chiaro.
Se ci sono due pirati, P2 e P1, è a P2 che spetta fare una
proposta.
D’altra parte a P2 quanti voti bastano per vincere? La metà di due,
dunque a P2 basta un voto, e questo è il suo. Infatti P2 voterà per
sé. . . perché? Perché ogni pirata vuole innanzitutto sopravvivere.
Dunque P2 si prende tutto.
P2
100
C ARANTI (T RENTO )
P1
0
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
13 / 42
R AGIONARE DA PIRATI
C OME RAGIONANO I PIRATI
T RE PIRATI
Vediamo il caso di tre pirati, P3, P2 e P1. E’ P3 che deve fare una
proposta. Di quanti voti ha bisogno in tutto? Di almeno la metà di
tre, dunque di almeno un voto e mezzo, cioè glie ne bastano due
in tutto.
Dunque P3 ha bisogno di un solo altro voto di appoggio.
P1 e P2 sanno che se P3 muore, P2 si prenderà tutto:
P2 P1
100 0
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
14 / 42
R AGIONARE DA PIRATI
C OME RAGIONANO I PIRATI
T RE PIRATI
Dunque P1 e P2 non hanno problemi di sopravvivenza, ma solo di
quante monete prendere.
P3 può ottenere il voto favorevole di P2? No! P2 voterà comunque
contro P3, perché se P3 muore, P2 si prende tutto al giro
seguente.
P3 P2 P1
X 100 0
(E se P3 gli offre tutto?)
Dunque P3 deve convincere P1 a votare per lui. Basta dargli una
moneta! Infatti se P3 muore, P1 non prenderà niente.
P3 P2 P1
99 0
1
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
15 / 42
R AGIONARE DA PIRATI
C OME RAGIONANO I PIRATI
Q UATTRO PIRATI
Vediamo il caso di quattro pirati, P4, P3, P2 e P1. E’ P4 che deve
fare una proposta. E ha bisogno di un solo voto di appoggio.
Tutti quanti sanno che se P4 muore, gli altri sono salvi, e la
divisione sarà
P3 P2 P1
99 0
1
Dunque a P4 basta offrire una moneta a P2! Infatti se P4 muore,
P2 non prenderà niente. In questo caso vince dunque la divisione
P4
99
C ARANTI (T RENTO )
P3
0
P2
1
P1
0
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
16 / 42
R AGIONARE DA PIRATI
C OME RAGIONANO I PIRATI
E INFINE , CINQUE PIRATI
Vediamo infine il caso iniziale di cinque pirati, P5, P4, P3, P2 e
P1. E’ P5 che deve fare una proposta. E ha bisogno di due voti di
appoggio.
Tutti quanti sanno che se P5 muore, la divisione darà
P4 P3 P2 P1
99 0
1
0
Quali due pirati deve corrompere P5? Quelli che, se P5 muore,
non prenderanno niente! Cioè P3 e P1.
P5 P4 P3 P2 P1
98 0
1
0
1
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
17 / 42
R AGIONARE DA PIRATI
E QUANDO I PIRATI SONO TANTI ?
TANTI PIRATI
Fonte: http://en.wikipedia.org/wiki/Pirates
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
19 / 42
R AGIONARE DA PIRATI
E QUANDO I PIRATI SONO TANTI ?
I L CASO “ GENERALE ”
Se i pirati sono in numero 2n pari, P{2n} dà una moneta a tutti i
pirati pari prima di lui, e si tiene quello che rimane.
P6 P5 P4 P3 P2 P1
98 0
1
0
1
0
Se i pirati sono in numero 2n + 1 dispari, P{2n+1} dà una moneta
a tutti i pirati dispari prima di lui, e si tiene quello che rimane.
P7 P6 P5 P4 P3 P2 P1
97 0
1
0
1
0
1
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
20 / 42
R AGIONARE DA PIRATI
E QUANDO I PIRATI SONO TANTI ?
D UECENTO PIRATI
Fermo restando che le monete sono 100, vediamo cosa succede
quando arriviamo a 200 pirati.
P200
1
P199
0
P198
1
...
...
P3
0
P2
1
P1
0
A P200 rimane una sola moneta, ma meglio di niente.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
21 / 42
R AGIONARE DA PIRATI
E QUANDO I PIRATI SONO TANTI ?
D UECENTOUNO PIRATI
Vediamo cosa succede quando arriviamo a 201 pirati.
P201
0
P200
0
P199
1
P198
0
...
...
P3
1
P2
0
P1
1
P201 dà una moneta a tutti i pirati dispari prima di lui.
Questi sono P1, P3, . . . , P199, e sono 100.
Dunque a lui non rimane neanche una moneta.
Ma almeno sopravvive.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
22 / 42
R AGIONARE DA PIRATI
E QUANDO I PIRATI SONO TANTI ?
D UECENTODUE PIRATI
Vediamo cosa succede quando arriviamo a 202 pirati.
P202
0
P201
0
P200
1
P199
0
P198
1
...
...
P3
0
P2
1
P1
0
P202 ha comunque il suo voto, più quello dei cento pirati a cui ha dato
una moneta.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
23 / 42
R AGIONARE DA PIRATI
E QUANDO I PIRATI SONO TANTI ?
P ROBLEMINO
Vediamo cosa succede quando arriviamo a 203 pirati.
P203 ha bisogno di 102 voti a favore.
Uno è il suo, dunque glie ne restano da trovare 101.
Ma lui ha solo 100 monete da distribuire.
Gli altri pirati non rischiano comunque la vita anche se gli votano
contro perché con 202 pirati non muore nessuno.
Dunque P203 muore comunque.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
24 / 42
R AGIONARE DA PIRATI
E QUANDO I PIRATI SONO TANTI ?
U N MIRACOLO INASPETTATO
Vediamo cosa succede quando arriviamo a 204 pirati.
P204 ha bisogno di 102 voti a favore. Uno è il suo, dunque glie ne
restano da trovare 101. Lui ha solo 100 monete da distribuire.
Dunque muore?
Ma se P204 muore, che succede? Sappiamo che al giro
successivo anche P203 morirà.
Dunque P203 voterà comunque a favore di P204, perché vuole
sopravvivere! Non c’è bisogno che P204 dia alcuna moneta a
P203!
Gli altri 100 voti P204 li ottiene comprando il supporto degli altri
pirati con le 100 monete.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
25 / 42
R AGIONARE DA PIRATI
E QUANDO I PIRATI SONO TANTI ?
U NA STRAGE
P205 non è così fortunato, perché ha bisogno di 103 voti, ma
nessun altro pirata rischia la vita se gli vota contro, perché con
204 pirati non muore nessuno. Dunque ha solo
1 + 100 = 101 < 103 voti. Il povero P205 muore.
Lo stesso capita a P206.
Infatti P206 ha bisogno di 103 voti:
uno è il suo;
100 se li compra con le monete;
uno è quello di P205, perché se muore P206, poi muore anche
P205;
ma con questo si arriva solo a 1 + 100 + 1 = 102 voti, glie ne
manca sempre uno.
Muore anche P207, che ha bisogno di 104 voti, ma ne ha solo
103:
il suo;
100 comprati;
quelli di P206 e P205, che altrimenti muoiono anche loro.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
26 / 42
R AGIONARE DA PIRATI
E QUANDO I PIRATI SONO TANTI ?
S ALVEZZA !
Ma guardiamo P208. Ha bisogno di 104 voti. Uno è il suo. 100 se
li compra con le monete. Gli mancano dunque 3 voti.
Ma se lui muore, allora muoiono anche P205, P206, P207. Questi
sono dunque 3 voti comunque a suo favore, esattamente quelli
che gli mancano!
Qual è la regola generale?
Non è difficile vedere che sopravvivono i pirati che hanno un
numero della forma 200 + 2n , cioè
201 = 200 + 20 ,
202 = 200 + 21 ,
204 = 200 + 22 ,
208 = 200 + 23 ,
216 = 200 + 24 ,
...
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
27 / 42
B IBLIOGRAFIA
B IBLIOGRAFIA
Wikipedia
http://en.wikipedia.org/wiki/Pirate_game
Ian Stewart,
A Puzzle for Pirates
Scientific American, May 1999, p. 98–99.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
28 / 42
O CCHI AZZURRI
O CCHI AZZURRI
B LUE E YES : T HE H ARDEST L OGIC P UZZLE IN THE
W ORLD
http://xkcd.com/blue_eyes.html
http://xkcd.com/solution.html
Puzzle text/solution copyright Randall Munroe, 2005—2006
Su un’isola vive un gruppo di persone con occhi di vari colori.
Sono tutti capaci di qualsiasi ragionamento logico.
Nessuno conosce il colore dei propri occhi, ma ognuno conosce
tutte le altre persone che ci sono sull’isola, e conosce il colore dei
loro occhi.
Ogni mattina all’alba un traghetto si ferma sull’isola. Può (e
vuole/deve) lasciare l’isola ogni abitante che conosca con
certezza il colore dei propri occhi.
Non è ammessa alcuna comunicazione.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
30 / 42
O CCHI AZZURRI
O CCHI AZZURRI
B LUE E YES
Sull’isola ci sono cento persone con gli occhi azzurri, cento con gli
occhi verdi, e il Capo (detto anche outsider), che non conta (e
comunque li ha grigi).
Un giorno (il giorno zero) a mezzogiorno il Capo parla per la prima
e unica volta, e dice a tutti:
“Almeno uno di voi ha gli occhi azzurri.”
Chi lascia l’isola, e quando?
E’ solo una questione di logica, non di giochi di parole, o di
trucchetti tipo specchi o chissà cosa.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
31 / 42
O CCHI AZZURRI
S OLUZIONE ?
C HI LASCIA L’ ISOLA , E QUANDO ?
Pensate al consiglio che vi ho dato prima, a proposito del
problema dei pirati.
Conviene pensare dapprima ai casi più piccoli.
Che succede se c’è una sola persona con gli occhi azzurri
sull’isola?
Dopo che il Capo ha parlato, non vede nessuno con gli occhi
azzurri, ma sa che ce ne sono.
Dunque ha capito di essere l’unico con gli occhi azzurri, e se ne
parte all’alba del primo giorno.
E se ce ne sono due di persone con gli occhi azzurri?
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
33 / 42
O CCHI AZZURRI
S OLUZIONE ?
D UE PERSONE CON GLI OCCHI AZZURRI
Se ci sono due persone con gli occhi azzurri, ognuno dei due sa
che l’altro ha gli occhi azzurri, ma non sa niente dei propri,
dunque non va via il giorno dopo.
Ma a questo punto ognuno dei due si chiede: “Come mai l’altro
non è andato via?”
Se era l’unico, abbiamo già visto che sarebbe andato via dopo un
giorno.
L’unica possibile spiegazione è che l’altro non sia l’unico.
A questo punto entrambi hanno capito di avere gli occhi azzurri e
se ne vanno entrambi dopo due giorni.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
34 / 42
O CCHI AZZURRI
S OLUZIONE ?
C HE INFORMAZIONE HA DATO IL CAPO ?
Ci potremmo chiedere che informazione nuova ha fornito il Capo
in questo caso con la sua dichiarazione?
In fondo in questo caso tutti sapevano già che c’erano persone
con gli occhi azzurri.
Vero, ma prima che parlasse il Capo le due persone con gli occhi
azzurri non sapevano se l’altro lo sapeva!
In effetti se l’altro fosse stato l’unico con gli occhi azzurri, prima
che il Capo parlasse non lo sapeva.
Ma dopo che il Capo ha parlato, tutti sanno che tutti sanno che ci
sono persone con gli occhi azzurri.
Il Capo ha apportato una conoscenza condivisa (common
knowledge).
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
35 / 42
O CCHI AZZURRI
C OMMON K NOWLEDGE
C OMMON K NOWLEDGE
Wikipedia
http://en.wikipedia.org/wiki/Common_knowledge_(logic)
The concept was first introduced in the philosophical literature by
David Kellogg Lewis in his study Convention (1969). [. . . ] It was
first given a mathematical formulation in a set-theoretical
framework by Robert Aumann (1976).
Computer scientists grew an interest in the subject of epistemic
logic in general — and of common knowledge in particular —
starting in the 1980s.
There are numerous puzzles based upon the concept which have
been extensively investigated by mathematicians such as John
Conway.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
37 / 42
O CCHI AZZURRI
C OMMON K NOWLEDGE
E IN GENERALE . . .
Se le persone con gli occhi azzurri sono tre, ciascuna di esse
aspetterà il secondo giorno, per vedere se gli altri due se ne
vanno via.
Visto che al secondo giorno non succede niente, ognuno di loro
capisce che c’è una terza persona con gli occhi azzurri, cioè sé
stesso, e tutti e tre se ne vanno all’alba del terzo giorno.
Dunque nel caso di cento persone con gli occhi azzurri, se ne
vanno tutti all’alba del centesimo giorno.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
38 / 42
O CCHI AZZURRI
NF K
M ARIO D RAGHI
1
noiseFromAmeriKa: Ma perché Draghi deve dire il falso?
http://goo.gl/MZujL 24 luglio 2011 — Andrea Moro
Pensiamo alla seguente situazione.
Se la situazione finanziaria peggiora (per esempio se viene
approvata una manovra che fa schifo), a tutti conviene mettere in
atto comportamenti (per esempio, la svendita di BOT e BTP) che
provocano la catastrofe economica planetaria, o perlomeno
europea, o italiana. Insomma, qualcosa di brutto e indesiderabile.
[. . . ]
È un problema di coordinamento: quando la manovra fa schifo, se
tutti svendono, conviene svendere anche a me, ma se nessuno
svende, meglio tenersi i BOT. Se la manovra fosse buona, allora
non converrebbe mai svendere.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
40 / 42
O CCHI AZZURRI
NF K
M ARIO D RAGHI
2
Tutti sanno che la manovra fa schifo, ma non sanno che gli altri lo
sanno. Se gli altri non lo sanno, non svendono i BOT. Dunque
neanche a me conviene svendere.
Io non so che gli altri lo sanno, né loro sanno che io lo so, quindi
anche loro si comporteranno allo stesso modo.
Ma se Draghi annuncia la manovra fa schifo, cambia tutto. Ora so
che gli altri lo sanno, e loro sanno che io lo so, e so che sanno che
io lo so. . . e cosí via all’infinito.
Si crea quello che in gergo definiamo common knowledge. La
conseguenza è che tutti svendiamo e il mondo crolla.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
41 / 42
O CCHI AZZURRI
NF K
M ARIO D RAGHI
3
Al contrario, quando Draghi dice che la manovra è un importante
passo avanti, questo non ha alcuna conseguenza indesiderata
anche se sappiamo che Draghi è un bravo economista e sta
mentendo.
Nemmeno se lo sanno tutti, che Draghi sta mentendo.
Perché non so che gli altri sanno che sta mentendo.
Questa asimmetria deriva dall’asimmetria iniziale sulle
conoscenze: tutti sanno che la manovra fa schifo. Una frase di
Draghi che va nello stesso senso crea common knowledge. Una
frase in senso contrario, invece, aumenta l’incertezza e consolida
la decisione iniziale di attendere avvenimenti chiarificatori.
C ARANTI (T RENTO )
P IRATI , M ONETE , O CCHI A ZZURRI . . .
ROVERETO , 15 MAGGIO 2012
42 / 42