Matematica Discreta (II modulo)

Primo appello, a.a. 2003/2004 -- compito 2

Date: 19 aprile 2004

Da svolgersi in tre ore. Al candidato si richiede di svolgere almeno un esercizio di ciascuno dei due gruppi e di rispondere ad almeno una delle domande teoriche. Tutte le risposte devono essere motivate.

Non è ammessa la consultazione di libri e/o appunti.

Esercizio 1   Dire se il seguente sistema di congruenze ammette soluzioni ed in tal caso determinarle tutte:

$$\begin{cases} x\equiv -3 \quad{\rm mod} 35 \\ x\equiv 22 \quad{\rm mod} 25 \\ \end{cases}$$

    $\square$
Soluzione

Esercizio 2   Un musicista jazz vuole formare una band composta da 5 sassofonisti, 3 trombettisti, 2 percussionisti, 2 chitarristi.
Alle selezioni si presentano 8 sassofonisti, 7 trombettisti, 5 percussionisti e 3 chitarristi.

1. Quante sono le possibili band che può formare?
2. Il musicista decide di selezionare anche una cantante da scegliere fra 4 candidate, come cambia il numero determinato al punto precedente?
3. Supponendo che il musicista abbia scelto la band, in quanti modi può selezionare da questa un trio di solisti composto da 1 sax, 1 chitarra, 1 percussione?

Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

$$d_1 = (1, 1, 2, 2, 2, 2, 7, 7)\qquad d_2 = (1, 1, 2, 3, 3, 3, 3, 4, 6, 7, 9)$$

è lo score di un grafo e quando ciò è possibile costruire un tale grafo. Si dica inoltre se

1. è possibile trovare un tale grafo che sia anche un albero
2. è possibile trovare un tale grafo che sia connesso
3. è possibile trovare un tale grafo che sia 2-connesso

Soluzione

Esercizio 4   Dire, motivando la risposta, quali tra i grafi rappresentati in figura sono tra loro isomorfi e quali no.

Soluzione

Domanda di teoria 1. Si dia la definizione di elemento invertibile in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\textst... ...} {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$, quindi si enunci e si provi il piccolo teorema di Fermat.

Domanda di teoria 2. Si dia la definizione di albero, quindi si enunci e si provi il teorema di caratterizzazione degli alberi finiti (formula di Eulero).