Matematica Discreta (II modulo)

Secondo appello, a.a. 2000/2001

2 luglio 2001

Esercizio 1   Dire se il sistema di congruenze

$$\left\{ \begin{array}{ll} x \cong 37 &\quad{\rm mod} 280 \\ x \cong 47 &\quad{\rm mod} 165 \end{array} \right.$$

ammette soluzioni ed in tal caso determinarle.
Soluzione

Esercizio 2   Sia $x_n$ la successione definita ricorsivamente da

$$\left\{ \begin{array}{l} x_{n+2} = 2 x_{n+1} + x_n \\ x_1 = 44 \\ x_0 = 43 \end{array} \right.$$

1. Si provi che $x_n$ è dispari se $n$ è pari ed è pari se $n$ è dispari;
2. Si provi che $[x_{n+1},x_n]=x_{n+1}x_n$ per ogni $n\in\mathbb{N}$.

Soluzione

Esercizio 3   Si determini il numero di anagrammi della parola

PRECIPITEVOLISSIMEVOLMENTE.

Si determini inoltre il numero di tali anagrammi che scambiano le P con le O.
Soluzione

Esercizio 4   Dire, motivando la risposta, quale dei vettori

$$\begin{eqnarray*} d_1 & = & (0,1,2,3,3,3,5,8,8,9)\\ d_2 & = & (1,3,3,3,4,4,4,5,5) \end{eqnarray*}$$

è 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 anche connesso

Soluzione

Esercizio 5   Sia $G=(V,E)$ un grafo e sia $n=\left\vert V\right\vert\ge3$. Si provi che in $G$ non possono esistere contemporaneamente due vertici di grado $n-1$ e un vertice di grado $1$.
Soluzione

Esercizio 6   Dire quali tra i seguenti grafi sono tra loro isomorfi e quali no:

1. $G_1=(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}16\mathbb{Z}}} {{}_{\!... ...!\scriptstyle {}16\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}16\mathbb{Z}}},E_1)$, essendo $E_1=\big\{\{n,m\}\bigm\vert n=m+2 \hbox{\rm { in }} \mathbb{Z}\big/\mathchoice... ...\scriptstyle {}16\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}16\mathbb{Z}}}\big\}$
2. $G_2=(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}16\mathbb{Z}}} {{}_{\!... ...!\scriptstyle {}16\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}16\mathbb{Z}}},E_2)$, essendo $E_2=\big\{\{n,m\}\bigm\vert n=m+3 \hbox{\rm { in }} \mathbb{Z}\big/\mathchoice... ...\scriptstyle {}16\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}16\mathbb{Z}}}\big\}$
3. $G_3=((\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}17\mathbb{Z}}} {{}_{\... ...criptstyle {}17\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}17\mathbb{Z}}})^*,E_3)$, essendo $E_3=\big\{\{n,m\}\bigm\vert n=3m \hbox{\rm { in }} \mathbb{Z}\big/\mathchoice ... ...\scriptstyle {}17\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}17\mathbb{Z}}}\big\}$

Soluzione