Matematica Discreta (II modulo)

Terzo appello, a.a. 2001/2002

Date: 19 settembre 2002

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.

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

Esercizio 1   Dire, motivando la risposta, se il sistema di congruenze

$$\begin{cases} x \cong 9 \quad{\rm mod}\ 603 \\ x \cong 27 \quad{\rm mod}\ 144 \end{cases}$$

ammette soluzioni ed in tal caso determinarle tutte. $(603,144)=9\mathrel{\big\vert}18 = 27-9$ quindi il sistema e` risolubile. Inoltre $9 = (-5) \cdot 603 + (21) \cdot 144$ quindi $27-9= 18 = 9 \cdot 2 = 603 \cdot (-10) + 144 \cdot 42$ quindi $x_0=-6021 = 27 -42 \cdot 144 = 9 -10\cdot 603$ è una soluzione del sistema. Tutte le soluzioni sono allora date da $\{ -6021 + k [144,603] \mid k\in\mathbb{Z}\}=\{ -6021 + k 9648 \mid k\in\mathbb{Z}\}=\{ 3627 + k 9648 \mid k\in\mathbb{Z}\} = \left[3627\right]_{9648}$     $\square$

Soluzione

Esercizio 2   Su uno scaffale ci sono $7$ libri, $3$ sono libri di matematica e $4$ sono libri di scienze. In quanti modi si possono disporre i libri sullo scaffale perché tutti i libri di matematica stiano assieme? [Charles M. Schulz]

Sapresti fornire, motivandola, una formula per lo soluzione dello stesso problema nel caso generale di $n$ libri di matematica e $m$ libri di scienze?
Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

$$d_1 = (1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 11, 12)\qquad d_2 = (1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 12, 13)$$

è 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 2-connesso
3. è possibile trovare un tale grafo che sia sconnesso

Soluzione

Esercizio 4   Sia $G$ un grafo aciclico con 10 vertici e $7$ lati. Provare che è possibile aggiungere a $G$ un lato in modo che il grafo rimanga aciclico.

Qual è il massimo numero di lati che si possono aggiungere a $G$ in modo che rimanga aciclico?
Soluzione

Domanda di teoria 1.  Si dia la definizione di rappresentabilità di un numero naturale rispetto ad una base fissata. Quindi si enunci e si provi il teorema di rappresentabilità dei numeri naturali rispetto ad una base fissata.

Domanda di teoria 2.  Scrivere e provare la formula che in un grafo finito lega i gradi dei vertici al numero dei lati. Se ne enunci quindi qualche conseguenza