Le Pierangiolate
n.2
Dipartimento di Ingegneria della
Informazione e Scienze Matematiche
Luca Chiantini presenta
Se gratti S I E N A
Che cosa salta fuori?
Se gratti S I E N A
Che cosa salta fuori?
Giochi di Archimede ---- 22 novembre 2006
PROBLEMA : In quanti modi diversi si possono ordinare le
lettere della parola SIENA,
In modo che non vi siano due consonanti consecutive?
In quanti modi diversi si possono ordinare le
lettere della parola SIENA,
In modo che non vi siano due consonanti consecutive?
SI ENA
S I NE A
ok
EI SNA
no
cosa scommettere?
In quanti modi diversi si possono ordinare le
lettere della parola SIENA,
In modo che non vi siano due consonanti consecutive?
Tirare a indovinare
Forza bruta
Metodo matematico
MENONE:
Differenza fra retta opinione
e Scienza
Platone
In quanti modi diversi si possono ordinare le
lettere della parola SIENA?
Forza bruta
E
S
I
E
N
A
S I ENA
I
N
S
A
ha 5 possibilità
ha 4 possibilità
ha 3 possibilità
ha 2 possibilità
ha 1 possibilità
fattoriale
5!=
54321
= 120
Per avere due consonanti vicine
S nella prima casella
S
S
S
S
N nella seconda casella
Possibilità 1 ∙ 3 ∙ 2 ∙ 1 = 6
nella seconda casella N nella prima o terza casella
Possibilità 2 ∙ 3 ∙ 2 ∙ 1 = 12
nella terza casella
N nella seconda o quarta casella
Possibilità 2 ∙ 3 ∙ 2 ∙ 1 = 12
nella quarta casella
N nella terza o prima casella
Possibilità 2 ∙ 3 ∙ 2 ∙ 1 = 12
nella quinta casella
N nella quarta casella
Possibilità 1 ∙ 3 ∙ 2 ∙ 1 = 6
48
In quanti modi diversi si possono ordinare le lettere
della parola SIENA, In modo che non vi siano due
consonanti consecutive?
= 120 – 48 = 72
In quanti modi diversi si possono ordinare le lettere
della parola SIENA, In modo che non vi siano due
consonanti consecutive?
Probabilità di successo
= 120 – 48 = 72
= 72 / 120 = 3 / 5 = 60%
Ragionamento per analogia
Se invece di
SIENA
Avessi la parola
L I C E O?
72
Avessi la parola
P A L I O?
72
Avessi la parola
C I E L O?
72
Qualunque parola di 5 lettere con 2 consonanti e 3 vocali
dà la stessa soluzione
nel
PALIO
si pongono numerosissimi
problemi combinatorici simili
ESEMPIO: se in un Palio corrono solo due contrade nemiche,
quale è la probabilità che finiscano accanto al canape?
20%
ESEMPIO: quante sono le possibilità di allineamento alla mossa?
17! / 7! = 17 ∙ 16 ∙ … ∙ 8 = 70.572.902.400
In quanti modi diversi si possono ordinare le lettere
della parola SIENA, In modo che non vi siano due
consonanti consecutive?
Probabilità di successo
= 120 – 48 = 72
= 72 / 120 = 3 / 5 = 60%
Ragionamento per analogia
Se invece di
SIENA
Avessi la parola
L I C E O?
72
Avessi la parola
P A L I O?
72
Avessi la parola
P A L C O?
sono 12 (10%)
Qualunque parola di 5 lettere con 2 consonanti e 3 vocali DISTINTE
dà la stessa soluzione
Se invece di
LICEO
Avessi la parola
LICE I?
In quanti modi diversi si possono ordinare le
lettere della parola LICEI?
LICEO
LICEI
LOCEI
LICEI
idem come sopra
Quindi le possibilità si dimezzano,
in quanto uno scambio delle due I non modifica la parola
120 / 2 = 60 possibilità
In quanti modi diversi si possono ordinare le
lettere della parola LICEI?
120 / 2 = 60 possibilità
Stesso discorso vale per le disposizioni
in cui le due consonanti non sono contigue:
poiché scambiando le I la parola non cambia
il loro numero si dimezza
72 / 2 = 36 possibilità senza consonanti contigue
In quanti modi diversi si possono ordinare le lettere
della parola LICEI, in modo che non vi siano due
consonanti contigue?
I numeri cambiano,
ma la percentuale no!
= 36
36 / 60 = 3 / 5 = 60%
In quanti modi diversi si possono ordinare le lettere della parola ARARE, in
modo che non vi siano due consonanti consecutive?
Stavolta, oltre a poter scambiare le due A,
possiamo anche scambiare le due R senza cambiare la parola
120 / 4 = 30 possibilità totali
72 / 4 = 18 possibilità senza consonanti contigue
I numeri cambiano, ma la percentuale no!
18 / 30 = 3 / 5 = 60%
In quanti modi diversi si possono ordinare le lettere della parola ANANA, in
modo che non vi siano due consonanti consecutive?
Stavolta, oltre a poter scambiare le due N,
possiamo anche permutare le tre A
senza cambiare la parola
ci sono 2 permutazioni sulle N
ci sono 6 permutazioni sulle A
120 / (2 ∙ 6) = 10 possibilità totali
72 / (2 ∙ 6) = 6 possibilità senza consonanti contigue
I numeri cambiano, ma la percentuale no!
AAANN
AANAN
AANNA
ANAAN
ANANA
6 / 10 = 3 / 5 = 60%
ANNAA
NAAAN
NAANA
NANAA
NNAAA
AAANN
AANAN
AANNA
ANAAN
ANANA
ANNAA
NAAAN
NAANA
NANAA
NNAAA
ORDINAMENTO
LESSICOGRAFICO
Le precedenti parole possono essere
considerate SCHEMI di situazioni, in cui
A = vocale
N = consonante
Ogni parola di cinque lettere con due consonanti
può essere ridotta a uno degli schemi precedenti
LICEO
SIENA
ARARE
NANAA
NAANA
ANANA
Problemi combinatorici di questo tipo si studiano
partendo dalla comprensione di ciò che avviene sugli schemi.
ESEMPIO: se in un Palio
corrono solo due contrade
nemiche, quale è la
probabilità che finiscano
accanto al canape?
20%
E' sufficiente lavorare sugli schemi di parole con 10 lettere
del tipo AANANAAAAA, dove
N = contrada con nemica
A = contrada senza nemica
Il numero totale di tali schemi è:
10! / (2! ∙ 8!) = (10 ∙ 9) / 2 = 45
permutazioni delle N
permutazioni delle A
ESEMPIO: se in un Palio
corrono solo due contrade
nemiche, quale è la
probabilità che finiscano
accanto al canape?
ANNAAAAAAAAAA
Il numero totale di tali schemi è 45
Affichè le due nemiche
si trovino accanto:
se la prima N è al primo posto
se la prima N è al posto 2
...........
la seconda N deve essere al posto 2
la seconda N deve essere al posto 3
ci sono 9 posti dove si può trovare la prima N
quindi ci sono 9 schemi in cui le
due nemiche sono affiancate
9 / 45 = 20%
GENERALIZZANDO:
Disponendo n oggetti, di cui due di tipo N e i rimanenti di tipo A,
quale è la probabilità che i due oggetti di tipo N finiscano accanto?
Il numero totale degli schemi è
n! / (2! ∙ (n-2)!) = n ∙ (n-1) / 2
ci sono n-1 schemi in cui le due N sono affiancate
PROBABILITA' =
(n-1) ∙ 2 / n ∙ (n-1) = 2 / n
PROBLEMA
SCHEMATIZZAZIONE
analogia
GENERALIZZAZIONE
APPLICAZIONI
"poesia della Matematica"
ITALO CALVINO
nato a Cuba
1923
morto a Siena
1985
Le città invisibili (1972)
MARCO Di una città non godi le sette, o le
settantasette meraviglie, ma la risposta che dà ad una
tua domanda
KAN O le domande che ti pone, costringendoti a
rispondere. Come Tebe, per bocca della Sfinge.
Prendendo a caso una QUALUNQUE parola di 5 lettere, quale
è la probabilità di trovare due consonanti consecutive?
Di cui "buoni"
Gli SCHEMI di parole con 5 vocali sono
1
0
Gli SCHEMI di parole con 4 vocali sono
5
0
Gli SCHEMI di parole con 3 vocali sono
10
4
Gli SCHEMI di parole con 2 vocali sono
10
9
Gli SCHEMI di parole con 1 vocale sono
5
5
Gli SCHEMI di parole con 0 vocali sono
1
1
32 = 25
19
SIMMETRIA
1
1
1
1
1
1
2
3
4
5
1
1
3
6
10
probabilità
1
4
10
19 / 32 = 59% circa
1
5
1
Triangolo di Tartaglia
(A + N)^5 = (A + N) (A + N) (A + N) (A + N) (A + N) (A + N) = ……
Prendendo a caso una QUALUNQUE parola di n lettere, quale
è la probabilità di trovare due consonanti consecutive?
Di cui buoni
Gli SCHEMI di parole con n vocali sono
1
Gli SCHEMI di parole con n-1 vocali sono
n
……………….
?
Gli SCHEMI di parole con 0 vocali sono
1
2n
Triangolo di Tartaglia
buon divertimento ...
ESEMPIO: e se ci sono DUE
coppie di contrade nemiche,
quale è la probabilità che
ALMENO una coppia finisca
accanto?
una coppia accanto
un’altra coppia accanto
20% +
20%
conteremmo 2 volte una
disposizione in cui entrambe le
coppie di nemiche sono accanto
40%
PERCENTUALE
GIUSTA
=
% due nemiche
accanto
+
% due nemiche
accanto
(FORMULA di GRASSMANN)
-
% entrambe le
coppie di nemiche
sono accanto
PERCENTUALE
GIUSTA
=
% due
nemiche
accanto
+
% due
nemiche
accanto
-
% entrambe
le coppie di
nemiche
sono accanto
quante sono le disposizioni in cui entrambe
le coppie di nemiche sono accanto?
se le prime due
nemiche finiscono in
queste posizioni
(2 ∙ 8! possibilità )
(1 + 2 + 1) ∙ 6!
possibilità
(1 + 2 + 2 + 2 + 1) ∙ 6!
possibilità
allora le altre due
nemiche devono stare:
accanto nelle prime
tre posizioni
accanto nelle ultime
cinque posizioni
è il ragionamento di
prima, adattato al
caso di tre o cinque
posizioni al canape
PERCENTUALE
GIUSTA
=
% due
nemiche
accanto
+
% due
nemiche
accanto
-
% entrambe
le coppie di
nemiche
sono accanto
il ragionamento va ripetuto per tutte le possibili
disposizioni delle prime due nemiche
.......
cioè per tutte le PARTIZIONI binarie di 8 (= 10 – 2):
8 = 0 + 8 = 1 + 7 = 2 + 6 = ....
RISULTATO FINALE
% entrambe
le coppie di
nemiche
sono accanto
=
2 / 45
quindi
Se ci sono DUE coppie di contrade
nemiche, quale è la probabilità che
ALMENO una coppia finisca accanto?
35,55...%
ESEMPIO: e se ci sono TRE
coppie di contrade nemiche,
quale è la probabilità che
ALMENO una coppia finisca
accanto?
stavolta arriveremo a dover considerare le partizioni
TERNARIE di 6
ad esempio 6 = 2 + 1 + 3 ....
YOUNG TABLEAUX
IN GENERALE è difficile trovare una funzione F(n)
che in base a quante coppie n di nemiche ci sono
mi dà la probabilità che almeno due nemiche siano
accanto al canape.
eccetera ...
funzione
generatrice
buon divertimento!
P R O B A B I L I T A’
Casi favorevoli
Casi possibili
?
Esce 1
Esce 2
Esce 3
Truccato?
Esce 3
Esce 4
La probabilità
non è più di 1/6
Esce 5
Non esce 3
Esce 6
Prendendo a caso una QUALUNQUE parola di 5 lettere DEL
VOCABOLARIO, la probabilità di trovare due consonanti
consecutive NON è certo il 59%!
Pensate che stiamo scherzando?
Le password dei programmi non vanno mai, preferibilmente,
cercate fra le parole di senso compiuto
Usando le distorsioni causate da
elementi linguistici, si possono
“krakkare” i codici segreti
Alan Turing
Presso alcuni popoli e alcune culture, il
rimescolamento combinatorico degli
elementi è la via fondamentale per il
raggiungimento della conoscenza mistica
Presso tali popoli, lo studio della
combinatorica fa parte del
DNA ?culturale
DNA
La catena del DNA rappresenta una sequenza di proteine di 4 tipi:
ACGT
Il codice del DNA è compreso solo parzialmente
buona parte dell’analisi del DNA è di tipo combinatorico
…ACATCGGACCTGACACGTAGTCAGTATCAGACTCCGAACT…
Studiando le occorrenze non casuali, si possono ottenere informazioni su come
sono codificate le informazioni per la costruzione degli esseri viventi
MASTER in BIOINFORMATICA
A. del Lungo
SPONSORS
Fondazione Monte dei Paschi di Siena
Wind
Novartis Italia
Siena Biotech
SienaBioGrafix
ProteoGenBio
Centro Sviluppo
Diesse Diagnostica Senese S.p.A.
CORSO di LAUREA MAGISTRALE
in BIOINFORMATICA
congiunto
Università di SIENA
Università di LEIDA (NL)
Le città invisibili (1972)
... Il Kan cercava di immedesimarsi nel gioco, ma ora era il perchè del gioco a
sfuggirgli. Quale era la posta? Allo scacco matto, sotto il piede del re sbalzato
dal vincitore, non rimaneva che una casella vuota, un tassello di legno
piallato: il nulla ...
Allora Marco parlò – La tua scacchiera, Sire, è intarsio di due legni: ebano e
acero. Il tassello sul quale si fissa il tuo sguardo illuminato fu tagliato su uno
strato del tronco che crebbe in un anno di siccità: vedi infatti come sono strette
le fibre? Ecco un poro più grosso, indice di una malattia della pianta, che forse
portò al suo abbattimento ... – e continuava.
Il Kan era stupito. La quantità di cose che si potevano leggere su un pezzetto di
legno piallato lo sommergeva. E già Marco era venuto a parlare dei boschi di
ebano, di zattere sui fiumi, e di approdi, e di donne alle finestre ...
In quanti modi diversi si possono ordinare le
lettere della parola SIENA,
In modo che non vi siano due consonanti consecutive?
SI ENA
In quanti modi diversi si possono ordinare le
lettere della parola SIENA,
In modo che non vi siano due consonanti consecutive?
Le possibili disposizioni sono ancora 120
Per avere due consonanti accanto:
Ho 5 possibilità per la S.
Ovunque metta la S, ho poi 2
possibilità per la N.
Poi ho 3 · 2 · 1 possibilità per
le vocali
60 possibilità su 120: il 50%!
SI ENA
Naturalmente il pentagono non è l’unica altra disposizione
eccetera
GRAFO =
Insieme di vertici collegati da alcuni spigoli
spigoli
vertici
Quanti sono i possibili grafi con n vertici?
Ogni vertice può essere collegato con altri n-1 vertici
Ogni spigolo collega due vertici
I possibili spigoli sono n (n-1) / 2
I possibili grafi sono
2
n (n-1) / 2
Quando n = 5, ci sono al più 10 spigoli, e i grafi sono 210 = 1024
Grafo completo
Presi un grafo e una disposizione delle lettere della parola SIENA,
quante probabilità ci sono che si abbiano due consonanti “vicine”?
SIMMETRIA
Dato un grafo G, è possibile formare il suo “antigrafo” G’ prendendo
per G’ esattamente gli spigoli mancanti in G.
antigrafo
antigrafo
Presi un grafo e una disposizione delle lettere della parola SIENA,
quante probabilità ci sono che si abbiano due consonanti “vicine”?
SIMMETRIA
Dato un grafo G, è possibile formare il suo “antigrafo” G’ prendendo
per G’ esattamente gli spigoli mancanti in G.
Fissata la disposizione delle lettere
Le consonanti sono vicine in G
Le consonanti NON sono vicine
nell’antigrafo G’
Quindi la probabilità è esattamente il 50%
La Matematica
NON
serve a
NON
fare i conti
GRAFI PLANARI
Grafo non planare
GRAFI PLANARI
E’ possibile, per ogni piantina geografica con 5 regioni,
disporre le lettere della parola SIENA
in modo che le consonanti non vadano su regioni confinanti?
I
S
E
A
N
Colorazione
delle piante
geografiche
TEOREMA dei QUATTRO COLORI
Ogni piantina geografica del piano può essere colorata con 4
colori, evitando che due regioni confinanti abbiano lo stesso colore
E’ possibile, per ogni piantina geografica con 5 regioni,
disporre le lettere della parola SIENA
in modo che le consonanti non vadano su regioni confinanti
Siccome ci sono 5 regioni, due devono avere per forza lo stesso colore:
basta mettere in queste due regioni la S e la N
I
S
Il Teorema dei 4 colori non
vale sul
A
Pianeta Ciambella
E
N
buon divertimento ...
“
Se gratti “S I E N A
Che cosa salta fuori?
Grazie per l’attenzione