ESERCITAZIONE DI MATEMATICA DISCRETA (23 novembre 2011) Esercizio 1

(1)

ESERCITAZIONE DI MATEMATICA DISCRETA (23 novembre 2011)

Esercizio 1 E’ possibile tracciare il disegno illustrato senza sollevare la penna dal foglio e senza ripassare più volte per lo stesso tratto, partendo dal punto A ? e partendo dal punto B ?

A

BB B

Soluzione: si può interpretare il disegno come un grafo (in cui i vertici sono i 7 punti in cui si incrociano i vari tratti e gli archi sono i tratti che collegano 2 vertici). Il problema richiede in pratica se esiste un cammino Euleriano in tale grafo: poiché si verifica che il grafo è connesso e che vi sono 5 vertici di grado pari (4 vertici di grado 4, ed il vertice A di grado 6) e 2 vertici di grado dispari (entrambi di grado 3, tra i quali B), per i Teoremi di Eulero risulta che esiste un cammino Euleriano non ciclico che collega i 2 vertici di grado dispari.

Quindi è possibile tracciare il disegno partendo da B (e terminando sull’altro vertice di grado dispari), ma non partendo da A.

Esercizio 2 Dimostrare che per ogni numero naturale n è vero il seguente predicato:

P(n)= “il numero n

³

-n+6 è divisibile per 3”.

Soluzione: si può applicare il principio di induzione (I

^a

forma). Il predicato è vero per n=1 perché il numero 1

³

-1+6=6 è divisibile per 3. Supponiamo il predicato vero per un valore n=k (quindi supponiamo che il numero k

³

-k+6 sia divisibile per 3) e dimostriamolo vero per n=k+1: la tesi è che il numero (k+1)

³

-(k+1)+6 è divisibile per 3. Ma sviluppando i calcoli tale numero coincide con:

(k

³

+3k

²

+3k+1)-(k+1)+6=(k

³

-k)+3k

²

+3k

e tale numero è divisibile per 3 (perché somma di numeri divisibili per 3) cioè la tesi.

Esercizio 3 Vengono distribuite caramelle di 6 gusti diversi a 10 bambini, in modo che ogni bambino riceva 5 caramelle. Dimostrare che esiste un gusto (o più di uno) del quale vengono distribuite almeno 9 caramelle.

(Sugg. Costruire una opportuna matrice, ragionare per assurdo e applicare il “contare per righe e colonne”).

Soluzione: si può costruire una matrice 6x10 in cui ad ogni riga corrisponde un gusto e ad ogni colonna un bambino, inserendo in ogni casella il numero di caramelle del gusto corrispondente alla riga che vengono date al bambino corrispondente alla colonna. Contando per colonne i valori nella matrice si ottiene 105=50.

Se per assurdo di ognuno gusto venissero distribuite al massimo 8 caramelle, contando per righe si avrebbe un totale al più di 86=48, contraddizione.

Esercizio 4 Calcolare il numero delle matrici 3x5 ad elementi nell’insieme {1,2,3,4,5,6,7} in cui nella prima colonna vi sono almeno 2 numeri <4.

Soluzione: si può applicare il principio di inclusione-esclusione in forma positiva costruendo gli insiemi A

1

,A

2

,A

3

contenenti rispettivamente le matrici in cui nella prima colonna si ha che la prima e seconda casella (rispettivamente la seconda e la terza, la prima e la terza) contengono numeri <4 e calcolando:

A

1

A

2

A

3

=A

1

+A

2

+A

3

-{A

1

A

2

+A

2

A

3

+A

1

A

3

+}+A

1

A

2

A

3

 Con il principio delle scelte multiple si ha:

A

1

=A

2

=A

3

=3

²

7

¹³

, A

1

A

2

=A

2

A

3

=A

1

A

3

=A

1

A

2

A

3

=3

³

7

¹²

.

Esercizio 5 Si consideri l’insieme di tutti i numeri naturali di 5 cifre, con cifre scelte fra 1,2,3,4,5,6,7

(2)

Dimostrare che , presi a piacere 50 di questi numeri, ne esistono fra essi sempre almeno 2 distinti x,y tali che il numero naturale di 2 cifre ottenuto considerando le ultime 2 cifre di x sia uguale al numero naturale di 2 cifre ottenuto considerando le ultime 2 cifre di y.

ESERCITAZIONE DI MATEMATICA DISCRETA (23 novembre 2011) Esercizio 1

ESERCITAZIONE DI MATEMATICA DISCRETA (23 novembre 2011)

Esercizio 1 E’ possibile tracciare il disegno illustrato senza sollevare la penna dal foglio e senza ripassare più volte per lo stesso tratto, partendo dal punto A ? e partendo dal punto B ?

A

BB B

Quindi è possibile tracciare il disegno partendo da B (e terminando sull’altro vertice di grado dispari), ma non partendo da A.

Esercizio 2 Dimostrare che per ogni numero naturale n è vero il seguente predicato:

P(n)= “il numero n

-n+6 è divisibile per 3”.

Soluzione: si può applicare il principio di induzione (I

forma). Il predicato è vero per n=1 perché il numero 1

-1+6=6 è divisibile per 3. Supponiamo il predicato vero per un valore n=k (quindi supponiamo che il numero k

-k+6 sia divisibile per 3) e dimostriamolo vero per n=k+1: la tesi è che il numero (k+1)

-(k+1)+6 è divisibile per 3. Ma sviluppando i calcoli tale numero coincide con:

(k

+3k

+3k+1)-(k+1)+6=(k

-k)+3k

+3k

e tale numero è divisibile per 3 (perché somma di numeri divisibili per 3) cioè la tesi.

Esercizio 3 Vengono distribuite caramelle di 6 gusti diversi a 10 bambini, in modo che ogni bambino riceva 5 caramelle. Dimostrare che esiste un gusto (o più di uno) del quale vengono distribuite almeno 9 caramelle.

(Sugg. Costruire una opportuna matrice, ragionare per assurdo e applicare il “contare per righe e colonne”).

Se per assurdo di ognuno gusto venissero distribuite al massimo 8 caramelle, contando per righe si avrebbe un totale al più di 86=48, contraddizione.

Esercizio 4 Calcolare il numero delle matrici 3x5 ad elementi nell’insieme {1,2,3,4,5,6,7} in cui nella prima colonna vi sono almeno 2 numeri <4.

Soluzione: si può applicare il principio di inclusione-esclusione in forma positiva costruendo gli insiemi A

,A

,A

contenenti rispettivamente le matrici in cui nella prima colonna si ha che la prima e seconda casella (rispettivamente la seconda e la terza, la prima e la terza) contengono numeri <4 e calcolando:

A

A

A

=A

+A

+A

-{A

A

+A

A

+A

A

+}+A

A

A

 Con il principio delle scelte multiple si ha:

A

=A

=A

=3

7

, A

A

=A

A

=A

A

=A

A

A

=3

7

.

Esercizio 5 Si consideri l’insieme di tutti i numeri naturali di 5 cifre, con cifre scelte fra 1,2,3,4,5,6,7

Dimostrare che , presi a piacere 50 di questi numeri, ne esistono fra essi sempre almeno 2 distinti x,y tali che il numero naturale di 2 cifre ottenuto considerando le ultime 2 cifre di x sia uguale al numero naturale di 2 cifre ottenuto considerando le ultime 2 cifre di y.

(Sugg. Applicare il principio dei cassetti, scegliendo in modo opportuno gli insiemi A,B e la funzione f:AB).

Soluzione: se A è l’insieme dei 50 numeri presi a piacere, e se B è l’insieme di tutti i numeri naturali di 2

cifre, con cifre scelte fra 1,2,3,4,5,6,7, definiamo la funzione f:AB che associa ad ogni xA il numero

formato dalle ultime sue cifre. La cardinalità di A è 50, maggiore della cardinalità di B (che è 77=49), quindi,

per il principio dei cassetti, esistono almeno 2 elementi distinti x,y di A tali che f(x)=f(y), e si ha la tesi.