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{array}{\vert c\vert c\vert c\vert c\vert c\vert} \hl... ... & 11 & 14 \\ \hline 3 & 6 & 9 & 12 & 15 \\ \hline \end{array}$$

raccogliendo quindi per righe le carte si ottiene la permutazione

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

la cui decomposizione in cicli disgiunti è:

$$\sigma = (1)(2~6~12~14~10~4)(3~11~9~13~5~7)(8)(15)$$

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$.     

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

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

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

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

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{array}{rclcrcl} 7 & = & 119 + 28 \cdot(- 4) & \\ ... ...85\cdot(-4) \\ &&&&&=& 504\cdot(13)+385\cdot(-17) \end{array}$$

Quindi,

$$32-11 = 3\cdot 7 = 3(504\cdot(13)+385\cdot(-17))=504\cdot 39 + 385 \cdot (-51)$$

e per tanto

$$-19624 = 32 - 504\cdot 39 = 11 + 385 \cdot (-51)$$

è 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 è:

$$\{-19624 + k 27720\mid k\in \mathbb{Z}\}= \{8096 + k 27720\mid k\in \mathbb{Z}\}.$$

    

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

$$x_{n+1}=3 x_{n} - x_{n-1} \le 3 x_{n} \le 3\cdot 3^n=3^{n+1}.$$

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:

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

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:

$$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}$$

    

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{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}$$

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

Figura: Un grafo che realizza $d_2$ come score (esercizio 4)

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$.     

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

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

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

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.