Le Pierangiolate n.2 Dipartimento di Ingegneria della Informazione e Scienze Matematiche Luca...

Le Pierangiolate n.2

Dipartimento di Ingegneria della Informazione e Scienze Matematiche

Luca Chiantini presenta

Se gratti S I E N AChe 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,


ES AI N

S N AI E

S N AIE

ok

no

cosa scommettere?



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 brutaES AI N

S ha 5 possibilitàI ha 4 possibilitàE ha 3 possibilitàN ha 2 possibilitàA ha 1 possibilità

5 4 3 2 1

5 ! = = 120fattoriale

SIE N A

S nella prima casella

Per avere due consonanti vicine

N nella seconda casellaPossibilità 1 ∙ 3 ∙ 2 ∙ 1 = 6

S nella terza casellaPossibilità 2 ∙ 3 ∙ 2 ∙ 1 = 12

N nella seconda o quarta casella

S nella seconda casella N nella prima o terza casellaPossibilità 2 ∙ 3 ∙ 2 ∙ 1 = 12

S nella quarta casella N nella terza o prima casellaPossibilità 2 ∙ 3 ∙ 2 ∙ 1 = 12

S nella quinta casella N nella quarta casellaPossibilità 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



Probabilità di successo = 72 / 120 = 3 / 5 = 60%

Ragionamento per analogia

Avessi la parola L I C E O?

Se invece di S I E N A

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 P A L I O

si pongono numerosissimi problemi combinatorici simili

ESEMPIO: se in un Palio corrono solo due contrade nemiche, quale è la probabilità che finiscano accanto al canape?

ESEMPIO: quante sono le possibilità di allineamento alla mossa?

20%

17! / 7! = 17 ∙ 16 ∙ … ∙ 8 = 70.572.902.400

Avessi la parola P A L C O? sono 12 (10%)



Probabilità di successo = 72 / 120 = 3 / 5 = 60%

Ragionamento per analogia

Avessi la parola L I C E O?

Se invece di S I E N A

72

Avessi la parola P A L I O? 72

Qualunque parola di 5 lettere con 2 consonanti e 3 vocali DISTINTEdà la stessa soluzione

Avessi la parola L I C E I ?

Se invece di L I C E O

In quanti modi diversi si possono ordinare le lettere della parola LICEI?

L I C E O L I C E I

L O C E I L I C E I 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?

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

120 / 2 = 60 possibilità

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?= 36

I numeri cambiano,ma la percentuale no! 36 / 60 = 3 / 5 = 60%

120 / 4 = 30 possibilità totali

72 / 4 = 18 possibilità senza consonanti contigue

In quanti modi diversi si possono ordinare le lettere della parola ARARE, in modo che non vi siano due consonanti consecutive?

I numeri cambiano, ma la percentuale no! 18 / 30 = 3 / 5 = 60%

Stavolta, oltre a poter scambiare le due A, possiamo anche scambiare le due R senza cambiare la parola

Stavolta, oltre a poter scambiare le due N, possiamo anche permutare le tre A

senza cambiare la parola

120 / (2 ∙ 6) = 10 possibilità totali

72 / (2 ∙ 6) = 6 possibilità senza consonanti contigue

In quanti modi diversi si possono ordinare le lettere della parola ANANA, in modo che non vi siano due consonanti consecutive?

I numeri cambiano, ma la percentuale no! 6 / 10 = 3 / 5 = 60%

ci sono 6 permutazioni sulle A

AAANN ANNAAAANAN NAAANAANNA NAANAANAAN NANAAANANA NNAAA

ci sono 2 permutazioni sulle N

AAANN ANNAAAANAN NAAANAANNA NAANAANAAN NANAAANANA NNAAA

Le precedenti parole possono essere considerate SCHEMI di situazioni, in cui A = vocale N = consonante

ORDINAMENTO LESSICOGRAFICO

Ogni parola di cinque lettere con due consonanti può essere ridotta a uno degli schemi precedenti

L I C E O

S I E N A

A R A R E

N A N A A

N A A N A

A N A N A

Problemi combinatorici di questo tipo si studiano partendo dalla comprensione di ciò che avviene sugli schemi.


20%

E' sufficiente lavorare sugli schemi di parole con 10 letteredel tipo AANANAAAAA, doveN = contrada con nemicaA = contrada senza nemica

Il numero totale di tali schemi è:

10! / (2! ∙ 8!)

permutazioni delle N permutazioni delle A

= (10 ∙ 9) / 2 = 45


Affichè le due nemiche si trovino accanto:

Il numero totale di tali schemi è 45

9 / 45 = 20%

se la prima N è al primo posto la seconda N deve essere al posto 2

se la prima N è 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 ledue nemiche sono affiancate

ANNAAAAAAAAAA

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 è

ci sono n-1 schemi in cui le due N sono affiancate

n! / (2! ∙ (n-2)!) = n ∙ (n-1) / 2

PROBABILITA' = (n-1) ∙ 2 / n ∙ (n-1) = 2 / n

PROBLEMA

SCHEMATIZZAZIONE

GENERALIZZAZIONE

APPLICAZIONI

analogia

"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?

Gli SCHEMI di parole con 5 vocali sono




Gli SCHEMI di parole con 1 vocale sono


1

10

5

10

5

1

1

1 1

1 2 1

1 3 31

1 4 6 41

1 5 10 105 1

Triangolo di Tartaglia

(A + N)^5 = (A + N) (A + N) (A + N) (A + N) (A + N) (A + N) = ……

Di cui "buoni"

0

4

0

9

5

1

1932

probabilità

19 / 32 = 59% circa

SIMMETRIA

= 25

Prendendo a caso una QUALUNQUE parola di n lettere, quale è la probabilità di trovare due consonanti consecutive?

Gli SCHEMI di parole con n vocali sono

Gli SCHEMI di parole con n-1 vocali sono


1

n

1

Triangolo di Tartaglia

Di cui buoni

?

2n

……………….

buon divertimento ...

ESEMPIO: e se ci sono DUE coppie di contrade nemiche, quale è la probabilità che ALMENO una coppia finisca accanto?

un’altra coppia accantouna coppia accanto +

20%

20%

40%conteremmo 2 volte una disposizione in cui entrambe le coppie di nemiche sono accanto

PERCENTUALE GIUSTA

% due nemiche accanto

% due nemiche accanto= + - % entrambe le

coppie di nemiche sono accanto

(FORMULA di GRASSMANN)

PERCENTUALE GIUSTA


= + -% 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à ) allora le altre due nemiche devono stare:

accanto nelle prime tre posizioni

accanto nelle ultime cinque posizioni

(1 + 2 + 1) ∙ 6!

possibilità

(1 + 2 + 2 + 2 + 1) ∙ 6!

possibilità

è il ragionamento di prima, adattato al caso di tre o cinque posizioni al canape

PERCENTUALE GIUSTA


= + -% 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

quindi

Se ci sono DUE coppie di contrade nemiche, quale è la probabilità che ALMENO una coppia finisca accanto?

2 / 45

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 ....

buon divertimento!

IN GENERALE è difficile trovare una funzione F(n)che in base a quante coppie n di nemiche ci sonomi dà la probabilità che almeno due nemiche siano accanto al canape.

eccetera ...YOUNG TABLEAUX

funzione generatrice

P R O B A B I L I T A’

Casi favorevoli

Casi possibili ?

Esce 1

Esce 2

Esce 3

Esce 4

Esce 5

Esce 6

Esce 3

Non esce 3

Truccato?

Prendendo a caso una QUALUNQUE parola di 5 lettere DEL VOCABOLARIO, la probabilità di trovare due consonanti

consecutive NON è certo il 59%!

La probabilità non è più di 1/6

Presso tali popoli, lo studio della combinatorica fa parte del

Le password dei programmi non vanno mai, preferibilmente,cercate fra le parole di senso compiuto

Pensate che stiamo scherzando?

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

DNA culturale?

La catena del DNA rappresenta una sequenza di proteine di 4 tipi: A C G T

DNA

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

SPONSORS Fondazione Monte dei Paschi di SienaWindNovartis ItaliaSiena BiotechSienaBioGrafixProteoGenBioCentro SviluppoDiesse Diagnostica Senese S.p.A.

MASTER in BIOINFORMATICAA. del Lungo

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 ...

ES AI N



ES AI N



Le possibili disposizioni sono ancora 120

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

Per avere due consonanti accanto:

60 possibilità su 120: il 50%!

Naturalmente il pentagono non è l’unica altra disposizione

eccetera

GRAFO = Insieme di vertici collegati da alcuni spigoli

vertici

spigoli

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 2n (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 serve a fare i conti

NON NON

GRAFI PLANARI

Grafo non planare

GRAFI PLANARI

SE

I

NA

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?

Colorazione delle piante geografiche

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

Ogni piantina geografica del piano può essere colorata con 4 colori, evitando che due regioni confinanti abbiano lo stesso colore

Siccome ci sono 5 regioni, due devono avere per forza lo stesso colore: basta mettere in queste due regioni la S e la N

Il Teorema dei 4 colori non vale sul

TEOREMA dei QUATTRO COLORI

A

E

N

I

S

Pianeta Ciambellabuon divertimento ...


“

“

Grazie per l’attenzione

Le Pierangiolate n.2 Dipartimento di Ingegneria della Informazione e Scienze Matematiche Luca...

Documents

Transcript of Le Pierangiolate n.2 Dipartimento di Ingegneria della Informazione e Scienze Matematiche Luca...