Matematica Discreta (II modulo)

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

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 -7 \quad{\rm mod}\ 21 \\ x\equiv 41 \quad{\rm mod}\ 81 \\ \end{cases}$$

Soluzione

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

1. Quante sono le possibili band che può formare?
2. Il musicista decide di selezionare anche due cantanti 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 = (2, 2, 2, 3, 3, 3, 3, 4, 8, 8)\qquad d_2 = (1, 1, 1, 1, 2, 2, 6, 6)$$

è 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 sconnesso
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).