515 ⎟⎟⎠⎞⎜⎜⎝⎛ 515 ⎟⎟⎠⎞⎜⎜⎝⎛ 37 ⎟⎟⎠⎞⎜⎜⎝⎛

Compito di Matematica Discreta I (3 settembre 2007)

Soluzioni

Esercizio 1. Tutti i vertici con 3 colonne sono adiacenti a tutti i vertici con 5 colonne, mentre i vertici con 4 colonne sono tutti adiacenti fra loro: vi sono quindi 2 componenti connesse, la prima contenente i vertici con 3 o 5 colonne (in numero di 2

+2

), la seconda quelli con 4 colonne (in numero di 2

). Per colorare i vertici della prima componente bastano 2 colori, per colorare i vertici della seconda occorrono necessariamente almeno 2

colori (uno per ogni vertice): il numero cromatico del grafo è dunque 2

. Nella prima componente ogni vertice ha grado pari (2

oppure 2

) quindi in essa esiste un cammino ciclico Euleriano, mentre nella seconda ogni vertice ha grado dispari 2

-1, quindi in essa non esiste un cammino Euleriano.

Esercizio 2. Si può usare il principio di induzione applicato al predicato P(n)=”il numero totale di parole sull’alfabeto {a,b} di lunghezza compresa fra 3 e 3+n (inclusi) è 2

-8”. Per n=1 il predicato è vero: il numero totale di parole di lunghezza compresa fra 3 e 4 (inclusi) è 2

+2

=24=2

-8. Supponendo vero P(k), dimostriamo vero P(k+1): il numero totale di parole sull’alfabeto {a,b} di lunghezza compresa fra 3 e 3+(k+1) (inclusi) è uguale alla somma del numero totale di parole sull’alfabeto {a,b} di lunghezza compresa fra 3 e 3+k (che per ipotesi è 2

-8) più il numero di parole di lunghezza k+4 (che è 2

) ottenendo in tutto (2

-8)+ 2

=2

-8, dunque P(k+1) è vero.

Esercizio 3. Si può usare il principio di inclusione-esclusione, costruendo 3 insiemi A,B,C contenenti rispettivamente le funzioni f tali che f(a),f(e) sono <6, f(a),f(o) sono

<6, f(e),f(o) sono <6 e calcolando la cardinalità: |A∪B∪C|=|A|+|B|+|C|- {|A∩B|+|A∩C|+|B∩C|}+|A∩B∩C|==5

8

+5

8

+5

8

-{5

8

+5

8

+5

8

+)+5

8

.

Esercizio 4. La scelta delle 3 posizioni fra le prime 7 in cui inserire cifre pari si può

effettuare in modi; la scelta della cifra (pari) in queste 3 posizioni si può effettuare in 4

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ 3 7

3

modi; la scelta della cifra (dispari) nelle restanti 4 posizioni (fra le prime 7) si può effettuare in 5

modi; la scelta della cifra nelle ultime 5 posizioni si può effettuare in 9

modi. Per il principio delle scelte multiple, la risposta è data dal prodotto di questi 4 numeri.

Esercizio 5. Ogni miscela è una combinazione con ripetizione di 6 elementi presi a

10 a 10, quindi il numero di possibili miscele è . Nel secondo caso, non sono più ottenibili solo le 6 miscele in cui si usa per 10 volte la stessa sostanza, quindi in questo caso il numero di possibili miscele è -6

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ 5 15

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ 5 15