• Non ci sono risultati.

Possiamo numerare la lettere e le buste da 1 ad n (lettera e busta corrispondente con lo stesso numero) e rappresentare ogni imbustamento come una funzione biunivoca

N/A
N/A
Protected

Academic year: 2021

Condividi "Possiamo numerare la lettere e le buste da 1 ad n (lettera e busta corrispondente con lo stesso numero) e rappresentare ogni imbustamento come una funzione biunivoca"

Copied!
1
0
0

Testo completo

(1)

Matematica Discreta

Lezione del giorno 15 novembre 2011 Il problema della “segretaria distratta”.

Supponiamo di avere n lettere (per n destinatari diversi) e le n buste corrispondenti (con il nome del destinatario già stampato), e di effettuare un “imbustamento” mettendo ogni lettera in una busta (lettere diverse in buste diverse).

Quesito: in quanti modi diversi si può effettuare un imbustamento totalmente errato, cioè in cui nessuna lettera vada nella busta corrispondente ?

Possiamo numerare la lettere e le buste da 1 ad n (lettera e busta corrispondente con lo stesso numero) e rappresentare ogni imbustamento come una funzione biunivoca

f : {1,2,…,n} → {1,2,…,n}

L’insieme A di tutti gli imbustamenti coincide con l’insieme di tutte le suddette funzioni biunivoche, di cardinalità n!.

Ogni imbustamento totalmente errato è una funzione fA che non soddisfa nessuna delle seguenti n proprietà:

f(1)=1; f(2)=2; … … ; f(n)=n

Possiamo allora usare la forma negativa del principio di inclusione-esclusione. Costruiamo quindi gli n insiemi:

A

1

= { fA / f(1)=1 }; A

2

= { fA / f(2)=2 }; etc …. ….; A

n

= { fA / f(n)=n } La risposta al quesito sarà: A-A

1

A

2

…A

n

.

Per il principio di inclusione-esclusione si ha:

A

1

A

2

…A

n

=α

1

2

3

4

+…….±α

n

dove α

1

è la somma delle cardinalità dei singoli insiemi; α

2

è la somma delle cardinalità di tutte le possibili intersezioni a 2 a 2 degli insiemi; α

3

è la somma delle cardinalità di tutte le possibili intersezioni a 3 a 3 degli insiemi; …….. …….; α

n

è la cardinalità dell’intersezione di tutti gli insiemi, preceduta da un segno + se n è dispari, da un segno – se n è pari.

Calcoliamo la cardinalità di A

1

: esso contiene le funzioni biunivoche f : {1,2,…,n} → {1,2,…,n}

tali che f(1)=1. Con il principio delle scelte multiple si ottiene cheA

1

=(n-1)!.

Con ragionamenti analoghi si ottiene:

A

2

=A

3

=……=A

n

=(n-1)!

dunque α

1

è la somma di n addendi tutti uguali ad (n-1)!, ossia α

1

= (n-1)!n = n!.

Ragionando in modo simile si ottiene che A

1

∩A

2

=(n-2)!, e ciò vale per la cardinalità dell’intersezione di 2 qualunque degli insiemi. Le possibili intersezioni a 2 a 2 corrispondono alle combinazioni semplici di n insiemi presi a 2 a 2, quindi sono in numero di



 

 2

n

. Dunque α

2

è la

somma di



 

 2

n

addendi tutti uguali ad (n-2)! .

Si ha allora: α

2

=(n-2)!



 

 2

n

= (n-2)!

2!(nn!2)!

=

2!

n!

. Con ragionamenti analoghi si ha: α

3

=

3!

n!

, α

4

=

4!

n!

, ... , α

n

=

n!

n!

=1 . Dunque il numero di imbustamenti totalmente errati é:

A-X

1

X

2

…X

n

=n!-(n!-

2!

n!

+

3!

n!

-

4!

n!

+....±

n!

n!

) =

2!

n!

-

3!

n!

+

4!

n!

+....±1 (dove l’ultimo

addendo 1 ha il segno + se n é pari, il segno – se n è dispari).

(2)

Esempio: se il numero delle lettere (e delle buste) è n=5, il numero di imbustamenti totalmente errati è: 5!/2!-5!/3!+5!/4!-5!/5! = 60-20+5-1=44

(su un totale di 5! = 120 imbustamenti in totale).

Principio del contare per righe e per colonne.

E’ un principio molto semplice, ma che spesso ha applicazioni interessanti.

Consideriamo una matrice nxm (n righe, m colonne) nelle cui caselle vi sono valori numerici.

Siano:

r

1

la somma dei valori che si trovano nella prima riga;

r

2

la somma dei valori che si trovano nella seconda riga;

etc….

r

n

la somma dei valori che si trovano nella riga numero n (l’ultima riga).

Analogamente siano:

c

1

la somma dei valori che si trovano nella prima colonna;

c

2

la somma dei valori che si trovano nella seconda colonna;

etc….

c

m

la somma dei valori che si trovano nella colonna numero m (l’ultima colonna).

Il principio del contare per righe e per colonne afferma semplicemente che:

r

1

+r

2

+……+r

n

= c

1

+c

2

+….+c

m

La dimostrazione di tale eguaglianza è ovvia: le 2 somme sono uguali perché coincidono entrambe con la somma di tutti gli elementi della matrice.

Esempio:

Siano dati 12 studenti (indicati con numeri interi da 1 a 12), che devono scegliere ognuno 4 corsi da seguire, fra 6 corsi a disposizione (indicati con le lettere A,B,C,D,E.F).

Se per i primi 5 corsi A,B,C,D,E il numero di studenti che frequentano è:

A: 9 studenti B: 8 studenti C: 3 studenti D: 7 studenti E: 10 studenti

quanti studenti frequentano il corso F ?

Per risolvere il problema possiamo costruire una matrice con 6 righe (ogni riga associata ad uno dei 6 corsi) e con 12 colonne (ogni colonna associata ad uno degli studenti):

1 2 3 4 5 6 7 8 9 10 11 12 A

B

(3)

C D E F

e inserire in ogni casella della matrice il valore 1 se lo studente corrispondente alla colonna della casella frequenta il corso corrispondente alla riga della casella, oppure il valore 0 in caso contrario.

Se calcoliamo c

1

(la somma dei valori nella prima colonna), si ha c

1

=4 (perché lo studente 1 frequenta 4 corsi su 6 dunque vi sono 4 valori =1 e 2 valori =0 nella prima colonna). Analogo ragionamento vale per le altre colonne: in ogni colonna la somma dei valori è sempre =4.

Se calcoliamo r

1

(la somma dei valori della prima riga), si ha r

1

=9 (perché il corso A è frequentato da 9 studenti, dunque vi sono 9 valori =1 e 3 valori =0 nella prima riga). Per le altre righe si ottengono r

2

=8, r

3

=3, r

4

=7, r

5

=10. Il numero r

6

(la somma dei valori della sesta riga) rappresenta il numero di studenti che frequentano il corso F.

Per il principio del contare per righe e per colonne si ha:

c

1+

c

2

+…..+c

12

= r

1

+r

2

+r

3

+r

4

+r

5

+r

6

ossia:

48 = 9+8+3+7+10+r

6

Si ottiene la risposta al quesito: r

6

=17.

Teoria dei grafi

L’origine storica della teoria dei grafi si fa risalire al problema dei 7 ponti di Könisberg (Eulero, 1736). La città di Könisberg (a quel tempo in Prussia, oggi in Russia e rinominata Kaliningrad) era attraversata dal fiume Pregel, nel quale vi erano 2 piccole isole; le 4 zone di terraferma (le 2 sponde del fiume e le 2 isole nel fiume) erano collegate da 7 ponti.

Ecco una mappa dell’epoca (dove in verde sono indicati i 7 ponti):

La situazione geografica si può schematizzare come segue:

Sponda a

(4)

Fiume Isola 5 Pregel

3 4 7

Sponda c

dove i ponti sono indicati con 1,2,3,4,5,6,7 e le zone di terra (2 isole + 2 sponde) sono indicate con a,b,c,d.

Gli abitanti della città di Könisberg si chiedevano:

Problema: è possibile partire da una delle 4 zone di terra, percorrere tutti i 7 ponti ognuno una ed una sola volta e tornare al punto di partenza ?

Nel piano si può disegnare una rappresentazione geometrica della situazione geografica, rappresentando le zone di terra a,b,c,d come punti ed i ponti come archi di curva, ognuno dei quali unisce 2 di tali punti:

a 6 1 2

b

5 d

3 4

c 7

Questo è già un esempio di rappresentazione piana di quello che chiameremo grafo: tale rappresentazione è costituita da punti del piano (detti vertici o nodi) e da archi di curva (detti archi o lati) ognuno dei quali unisce 2 vertici.

Però tale rappresentazione piana non può essere scelta come definizione del concetto di grafo, perché essa non è univoca, in quanto dipende dalla scelta delle posizioni dei vertici nel piano e dal modo di tracciare gli archi che li uniscono.

Per esempio potremmo ottenere un’altra rappresentazione piana dello stesso grafo dei ponti di Konisberg in questo altro modo:

1

Isola b

Isola d

(5)

a 6 d 5 b

7 3

4 c

Una definizione più astratta di grafo, ma più precisa ed univoca, è la seguente:

un grafo è una struttura costituita da 2 insiemi A, V (l’insieme A è detto insieme degli archi o lati del grafo, l’insieme V è detto insieme dei vertici o nodi del grafo), e da una funzione f: A → V

2

(dove V

2

indica l’insieme di tutti i sottoinsiemi di V che hanno cardinalità 2).

Una rappresentazione piana di un grafo si ottiene appunto rappresentando ogni vertice con un punto del piano e per ogni arco xA tale che f(x)={y,z} disegnando un arco di curva che unisce i due vertici y,z (questa rappresentazione, come già notato, può essere fatta in diversi modi).

Esempio: Nel grafo dei ponti di Konisberg, l’insieme dei vertici è V={a,b,c,d}, l’insieme degli archi è A={1,2,3,4,5,6,7}, e la funzione di adiacenza f: A  V

2

è definita ponendo:

f(1)={a,b}, f(2)={a,b}, f(3)={b,c}, f(4)={b,c}, f(5)={b,d}, f(6)={a,d}, f(7)={c,d}.

Riferimenti

Documenti correlati

[r]

[r]

[r]

Tale punto si connette a (0, −1) con un arco nel

Le funzioni e x , sin x, cos x, sinh x e cosh x verificano le ipotesi del precedente teorema, risultano quindi sviluppabili in serie di Taylor nel

Si terr` a conto non solo della correttezza dei risultati, ma anche della completezza e chiarezza delle spiegazioni..

Si terr` a conto non solo della correttezza dei risultati, ma anche della completezza e chiarezza delle spiegazioni..

Si terr` a conto non solo della correttezza dei risultati, ma anche della completezza e chiarezza delle spiegazioni..