Matematica Discreta (II modulo)

Terzo appello, a.a. 2004/2005 -- compito 1

Date: 7 settembre 2005

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   Determinare tutte le soluzioni della congruenza $x^7 \cong 4 \quad{\rm mod} 25$ e dire se il sistema di congruenze

$$\begin{cases} x^7 \cong 4 & \quad{\rm mod} 25 \\ x \cong 16 & \quad{\rm mod} 45 \end{cases}$$

ammette soluzioni oppure no.
Soluzione

Esercizio 2   Siano $A = \mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}14\mathbb{Z}}} {{}_{\!\t... ...{{}_{\!\scriptstyle {}14\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}14\mathbb{Z}}}$ e $B = (\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}14\mathbb{Z}}} {{}_{\!\... ..._{\!\scriptstyle {}14\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}14\mathbb{Z}}})^*$. Si calcolino le cardinalità dei seguenti insiemi:

1. $\mathcal{X}_1 = \{ C \in 2^A \mid \left\vert C \cap B\right\vert = 4\}$;
2. $\mathcal{X}_2 = \{ f \in A^A \mid f(B)=B\}$;
3. $\mathcal{X}_3 = \{ f \in A^A \mid f(B)=B$    e $f$    è iniettiva$\}$.

Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

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

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

1. un albero;
2. connesso;
3. sconnesso.

Soluzione

Esercizio 4   Si provi che in ogni albero con 10 vertici dei quali 7 siano di grado 1 esiste almeno un vertice di grado maggiore o uguale a 4.
Soluzione

Domanda di teoria 1.  Dare la definizione di numero primo e provare che $p$ è primo se e solo se

$$\forall \; a,b\in\mathbb{Z}\quad p\mathrel{\big\vert}ab \Rightarrow p\mathrel{\big\vert}a$$    o $$p \mathrel{\big\vert}b.$$

Domanda di teoria 2. Si diano le definizioni di passeggiata, cammino e di grafo connesso. Si provi che in un grafo due vertici sono congiungibili con una passeggiata se e solo se sono congiungibili con un cammino.