next up previous
Next: About this document ... Up: Testo degli esercizi Previous: Testo degli esercizi

Soluzioni proposte

Soluzione dell'esercizio 1 Eseguire le due operazioni produce una permutazione del mazzo di carte e iterare le due permutazioni corrisponde ad iterare la stessa permutazione. Dato che ogni permutazione di un insieme finito ha ordine finito (i.e. se $\sigma\in S_n$ esiste $k$ tale che $\sigma^k= 1$) allora dopo un numero finito di volte il mazzo tornerà nella disposizione di partenza.

Per determinare il minimo tale numero scriviamo esplicitamente la permutazione. La prima operazione sistema le carte nel modo seguente:

\begin{displaymath}
\begin{array}{\vert c\vert c\vert c\vert c\vert c\vert}
\hl...
... & 11 & 14 \\ \hline
3 & 6 & 9 & 12 & 15 \\ \hline
\end{array}\end{displaymath}

raccogliendo quindi per righe le carte si ottiene la permutazione

\begin{displaymath}
\sigma = \left(
\begin{array}{ccccccccccccccc}
1 & 2 & 3 ...
...2 & 3 & 8 & 13 & 4 & 9 & 14 & 5 & 10 & 15
\end{array} \right)
\end{displaymath}

la cui decomposizione in cicli disgiunti è:

\begin{displaymath}
\sigma = (1)(2~6~12~14~10~4)(3~11~9~13~5~7)(8)(15)
\end{displaymath}

L'ordine di $\sigma$, ossia il minimo intero positivo per cui $\sigma^k= 1$ è dato dal minimo comune multiplo delle lunghezze dei cicli, ossia $6$.     back.gif


Soluzione dell'esercizio 2 Dato che $396 \cong 11 \quad{\rm mod}\ 385$ il sistema è equivalente a:

\begin{displaymath}
\left\{
\begin{array}{ll}
x \cong 11 &\quad{\rm mod}\ 385 \\
x \cong 32 &\quad{\rm mod}\ 504
\end{array}\right.
\end{displaymath}

Calcoliamo il massimo comun divisore tra $504$ e $385$ usando l'algoritmo di Euclide.

\begin{displaymath}
\begin{array}{rcl}
504 & = & 385 \cdot 1 + 119 \\
385 & = &...
...\\
119 & = & 28 \cdot 4 + 7 \\
28 & = & 7 \cdot 4
\end{array}\end{displaymath}

quindi $(504,385)=7$ e pertanto il sistema di congruenze ha soluzione (dato che $(504,385)=7\mathrel{\big\vert}21=32-11$. Esprimiamo $7$ come combinazione intera di $504$ e $385$.

\begin{displaymath}
\begin{array}{rclcrcl}
7 & = & 119 + 28 \cdot(- 4) & \\
...
...85\cdot(-4) \\
&&&&&=& 504\cdot(13)+385\cdot(-17)
\end{array}\end{displaymath}

Quindi,

\begin{displaymath}
32-11 = 3\cdot 7 = 3(504\cdot(13)+385\cdot(-17))=504\cdot 39 + 385 \cdot (-51)
\end{displaymath}

e per tanto

\begin{displaymath}
-19624 = 32 - 504\cdot 39 = 11 + 385 \cdot (-51)
\end{displaymath}

è una soluzione del sistema. Dato che il minimo comune multiplo tra $504$ e $385$ è dato da $[504,385]=504\cdot 385/(504,385)=504\cdot 385/7=27720$, l'insieme delle soluzioni del sistema è:

\begin{displaymath}
\{-19624 + k 27720\mid k\in \mathbb{Z}\}= \{8096 + k 27720\mid k\in \mathbb{Z}\}.
\end{displaymath}

    back.gif


Soluzione dell'esercizio 3 (1). Procediamo per induzione su $n$. Per $n=1$ si ha che $2\ge 1 =
3^0$. Supponiamo $n\ge 1$, e che la tesi sia vera per $n$, e proviamo che allora è vera per $n+1$. Infatti

\begin{displaymath}
x_{n+1}=3 x_{n} - x_{n-1} \le 3 x_{n} \le 3\cdot 3^n=3^{n+1}.
\end{displaymath}

Dove la seconda disuguaglianza è data dall'ipotesi di induzione, mentre la prima dal fatto che per ogni $n$ si ha che $x_n\ge0$.

Quest'ultimo fatto lo proviamo nuovamente per induzione. Per $n=0,1$ la tesi è banale. Se $n\ge2$ allora $x_n=3x_{n-1}-x_{n-2}\ge 0$ in quanto per ipotesi di induzione $x_{n-1}\ge 0$ e $x_{n-2}\ge 0$.

(2). Proviamo che $(x_{n+1},x_n)=2$ per ogni $n$. Per $n=0$ la tesi è banale. Supponiamo la tesi vera per $n$ e proviamola per $n+1$. Dalla relazione $x_{n+2}=3x_{n+1}-x_n$ e dal lemma per la dimostrazione dell'algoritmo di Euclide, segue che $(x_{n+2},x_{n+1})=(x_{n+1},x_{n})$ e quest'ultimo, per ipotesi di induzione è $3$.

(3). Il polinomio caratteristico dell'equazione è dato da $t^2-3t+1$ le cui radici sono $(3+\sqrt{5})/2$ e $(3-\sqrt{5})/2$. La soluzione generale dell'equazione ricorsiva è allora data da: $A(3+\sqrt{5})^n/2^n + B(3-\sqrt{5})^n/2^n$. Imponendo le due condizioni iniziali si ottiene il sistema:

\begin{displaymath}
\left\{
\begin{array}{l}
A+B=2\\
A \frac{3+\sqrt{5}}{2} + B \frac{3-\sqrt{5}}{2}=2.
\end{array} \right.
\end{displaymath}

le cui soluzioni sono $A=(\sqrt{5}-1)/\sqrt{5}$ e $B=(\sqrt{5}+1)/\sqrt{5}$, quindi la successione definita per ricorrenza è data da:

\begin{displaymath}
x_n=\frac{\sqrt{5}-1}{\sqrt{5}} \frac{(3+\sqrt{5})^n}{2^n}+
\frac{\sqrt{5}+1}{\sqrt{5}} \frac{(3-\sqrt{5})^n}{2^n}
\end{displaymath}

    back.gif


Soluzione dell'esercizio 4 Osserviamo che in $d_1$ compaiono tre numeri dispari, quindi non può essere lo score di un grafo dato che in tal caso il numero di numeri dispari dovrebbe essere pari.

Usiamo il teorema dello score per determinare se $d_2$ è realizzabile oppure no.

\begin{displaymath}
\begin{array}{lcl}
d_2 & = & (1,1,1,1,2,2,3,5)\\
d_2' & ...
... = & (0,0,1,1,1,1,2)\\
d_2'' & = & (0,0,1,1,0,0)
\end{array}\end{displaymath}

Evidentemente $d_2''$ è realizzabile e pertanto $d_2$ lo è (vedi la figura [*]).

Figura: Un grafo che realizza $d_2$ come score (esercizio 4)
\begin{figure}\begin{center}\psfig{file=fig_a2_e4.ps,width=4cm} \end{center}\end{figure}

Osserviamo inoltre che $d_2$ non può essere realizzato da un albero in quanto se $G$ è un grafo che realizza $d_2$ allora

\begin{eqnarray*}
\left\vert V(G)\right\vert & = & 8 \\
\left\vert E(G)\right...
...c {1}{2}\sum_{v\in V(G)}\deg(v) =
\frac{1+1+1+1+2+2+3+5}{2} = 8
\end{eqnarray*}



Un tale grafo non può quindi essere un albero in quanto se lo fosse si avrebbe $\left\vert V(G)\right\vert-1=\left\vert E(G)\right\vert$.     back.gif


Soluzione dell'esercizio 5 Per assurdo sia $v$ una foglia di $G$ e sia $w$ l'unico vertice tale che $\{v,w\}\in E(G)$. Allora in $G-w$ non ci sono lati che partono da $v$, ma ci sono altri vertici diversi da $v$ (essendo $2$-connesso, $G$ ha almeno $3$ vertici), quindi $G-w$è sconnesso. Assurdo.

Il viceversa non è vero, si consideri ad esempio il grafo $G$ rappresentato in figura [*].

Figura: Il contresempio dell'esercizio 5, G è connesso, non ha foglie ma non è 2-connesso
\begin{figure}\begin{center}
\psfig{file=fig_a2_e5.ps,width=8cm} \end{center}\end{figure}

Il grafo $G$ non ha foglie, è connesso ed ha più di 3 vertici ma non è nemmeno $2$-connesso.     back.gif


Soluzione dell'esercizio 6 Scriviamo esplicitamente i lati dei tre grafi:

\begin{eqnarray*}
E_1 & = & \big\{ \{0,1\},\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,...
... & \big\{ \{3,1\},\{6,2\},\{2,3\},\{5,4\},\{1,5\},\{4,6\} \big\}
\end{eqnarray*}



Figura: I gragfi $G_1$ e $G_3$ sono dei cicli, mente il grafo $G_2$ è costituito da due cicli disgiunti, in particolare non è connesso
\begin{figure}\begin{center}
\psfig{file=fig_a2_e6.ps,width=11cm} \end{center}\end{figure}

Osserviamo che $G_1\oldcong G_3\oldcong C_6$, dato che $(0,1,2,3,4,5,0)$ è un ciclo in $G_1$ che contiene tutti i vertici e tutti i lati e anche $(3,1,5,4,6,2,3)$ è un ciclo in $G_3$ che contiene tutti i vertici e tutti i lati. In particolare $G_1$ e $G_3$ sono connessi. Il grafo $G_2$ non è connesso, in quanto è costituito dai due cicli $(0,2,4,0)$ e $(1,3,5,1)$ che non hanno vertici in comune. Quindi $G_2$ non è isomorfo né a $G_1$ né a $G_2$. Si veda la figura[*].     back.gif



next up previous
Next: About this document ... Up: Testo degli esercizi Previous: Testo degli esercizi
Luminati Domenico 2002-05-16