Soluzioni proposte

Soluzione dell'esercizio 1 $(2,55)=1$, quindi $2$ è invertibile in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}55\mathbb{Z}}} {{}_{\!\text... ...{}_{\!\scriptstyle {}55\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}55\mathbb{Z}}}$. $55=5\cdot11$, quindi $\Phi(55)=4\cdot10=40$, quindi $(3,40)=1$, pertanto esiste un unico $(\quad{\rm mod}\ 40)$ $d$ tale che $3d\cong1\quad{\rm mod}\ 40$. Determiniamo tale $d$.

$40=3\cdot 13+1$, quindi $1=40+(-13)3$ e quindi $3\cdot(-13)\cong 1 \quad{\rm mod}\ 40$ ovvero $3\cdot 27\cong1\quad{\rm mod}\ 40$. Ovvero $d\cong 27\quad{\rm mod}\ 40$.

Utilizzando il piccolo teorema di Fermat, si ottiene allora:

$$2^{3d}\cong 2 \quad{\rm mod}\ 55$$

ovvero $x\cong2^d=2^{27}\quad{\rm mod}\ 55$. Ma ora $2^6=64\cong 9\quad{\rm mod}\ 55$, quindi $2^{27}=(2^6)^42^3\cong 9^4 2^3=3^82^3\quad{\rm mod}\ 55$. Ora, $3^32=54\cong-1\quad{\rm mod}\ 55$, quindi $3^82^3=(3^32)^23^22\cong(-1)^218=18\quad{\rm mod}\ 55$. Ovvero $x\cong18\quad{\rm mod}\ 55$.     

Soluzione dell'esercizio 2 Il polinomio caratteristico è dato da $x^2-6x+3$ le cui radici sono $3+\sqrt{6}$ e $3-\sqrt{6}$, quindi una base dello spazio delle soluzioni è data dalle due successioni $a_n=(3+\sqrt{6})^n$ e $b_n=(3-\sqrt{6})^n$, quindi la soluzione generale dell'equazione è data da:

$$x_n=A (3+\sqrt{6})^n+B(3-\sqrt{6})^n\quad A,B\in\mathbb{R}.$$

Imponendo le condizioni iniziali si ottiene il sistema

$$\left\{ \begin{array}{l} -2 = x_0 = A + B \\ 3 = x_1 = A(3+\sqrt{6}) + B(3-\sqrt{6}) \end{array} \right.$$

risolvendo il quale si ottiene $A=(9-2\sqrt{6})/2\sqrt{6}$ e $B=(-9-2\sqrt{6})/2\sqrt{6}$, e quindi la soluzione è:

$$x_n=(9-2\sqrt{6}) (3+\sqrt{6})^n/2\sqrt{6}+(-9-2\sqrt{6})(3-\sqrt{6})^n/2\sqrt{6}.$$

    

Soluzione dell'esercizio 3 (1). $f\in {\cal F}_1$, se e solo se $\setbox\restrictbox=\hbox{$\hbox{$f$}_{A}$}\setbox0\hbox{$f$} {{f}\,\vrule widt... ...depth\dp\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{A}}\in B^A$ e $\setbox\restrictbox=\hbox{$\hbox{$f$}_{X-A}$}\setbox0\hbox{$f$} {{f}\,\vrule wi... ...dp\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{X-A}}\in Y^(X-A)$, possiamo quindi definire l'applicazione $\varphi :{\cal F}_1\to B^A \times Y^{X-A}$ ponendo

$$\varphi (f)=(\setbox\restrictbox=\hbox{$\hbox{$f$}_{A}$}\se... ...rictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{X-A}})$$

$\varphi$ è iniettiva. Infatti $\varphi (f)=\varphi (g)$ se e solo se $\setbox\restrictbox=\hbox{$\hbox{$f$}_{A}$}\setbox0\hbox{$f$} {{f}\,\vrule widt... ...tbox depth\dp\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{A}},$ e $\setbox\restrictbox=\hbox{$\hbox{$f$}_{X-A}$}\setbox0\hbox{$f$} {{f}\,\vrule wi... ...box depth\dp\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{X-A}}$ e quindi $f=g$ (dato che coincidono su titti gli elementi di $X$.

$\varphi$ è suriettiva. Infatti se $h\in B^X$ e $k\in Y^{X-A}$, allora è ben definita la funzione $f:X\to Y$ ponendo

$$f(x)=\Big\langle \begin{array}{lcl} h(x) & &\hbox{\rm {se }} x\in A \\ k(x) & &\hbox{\rm {se }} x\in X-A \end{array}$$

È immediato verificare che $f\in {\cal F}_1$ e che $\varphi (f)=(h,k)$.

Ma allora $\varphi$ è una bigezione, e quindi:

$$\left\vert\cal F\right\vert _1 = \left\vert B^A \times Y^{X... ...Y\right\vert^{\left\vert X\right\vert-\left\vert A\right\vert}$$

(2). Dati due insiemi $U$ e $V$ indichiamo con ${\cal I}(U,U)$ l'insieme delle applicazioni iniettive $U\to V$. Sappiamo che se $U$ e $V$ sono finiti, allora $\left\vert{\cal}(U,V)\right\vert=\left\vert V\right\vert!/(\left\vert V\right\vert-\left\vert U\right\vert)!$.

Osserviamo che se $f\in {\cal F}_2$ se e solo se $\setbox\restrictbox=\hbox{$\hbox{$f$}_{A}$}\setbox0\hbox{$f$} {{f}\,\vrule widt... ...strictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{A}}\in {\cal I}(A,B)$ e $\setbox\restrictbox=\hbox{$\hbox{$f$}_{X-A}$}\setbox0\hbox{$f$} {{f}\,\vrule wi... ...ox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{X-A}}\in{\cal I}(X-A,Y-f(A))$. Quindi è ben definita l'applicazione $\varphi :{\cal F}_2\to {\cal I}(A,B) \times Y^{X-A}$ ponendo

$$\varphi (f)=(\setbox\restrictbox=\hbox{$\hbox{$f$}_{A}$}\se... ...rictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{X-A}})$$

la cui immagine è contenuta nell'insieme

$$\begin{eqnarray*} {\cal B} & = &\big\{(h,k)\in {\cal I}(A,B) \times Y^{X-A} \bi... ... & \bigcup_{h\in {\cal I}(A,B)}\{h\}\times{\cal I}(X-A,Y-h(A)). \end{eqnarray*}$$

Come nella dimostrazione di (1), si dimostra che $\varphi$ è iniettiva e che la sua immagine è proprio $\cal B$. Quindi

$$\begin{eqnarray*} \left\vert{\cal F}_2\right\vert & = & \left\vert{\cal B}\righ... ...ight\vert)!}{(\left\vert Y\right\vert-\left\vert X\right\vert)!} \end{eqnarray*}$$

dove si è usato il fatto che, essendo $h$ iniettiva, $\left\vert h(A)\right\vert=\left\vert A\right\vert$ e che la somma di addendi tutti uguali è uguale al prodotto di uno di essi per il numero degli addendi.     

Soluzione dell'esercizio 4 Usiamo il teorema dello score.

$$\begin{eqnarray*} d & = & (2,2,2,2,,4,4,6,6) \\ d' & = & (2,1,1,1,3,3,5) \\ ... ...,1,2,2) \\ d'' & = & (0,0,1,1,2,2) \\ d''' & = & (0,0,1,0,1) \end{eqnarray*}$$

$d'''$ è realizzabile, quindi anche $d$ lo è. Una realizzazione è data ad esempio dal grafo rappresentato in figura 1, in cui è anche descritto un percorso euleriano del grafo.

Figura 1: Un grafo che realizza lo score dell'esercizio 4 ed un suo percorso euleriano, dato da $(a,b,c,d,e,a,c,h,e,g,f,c,e,f,a)$

Per provare che ogni grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d$ è euleriano, basta provare che ogni tale grafo è connesso. In tal cao infatti, dato che tutti i verici hanno grado pari, il teorema di caratterizzazione dei grafi euleriani garantisce la tesi.

Siano $v_1$ un vertice di grado $6$ e siano $v_2,\dots,v_7$ i vertici a lui adiacenti (i.e. $\{v_1,v_j\}\in E(G)$ per $j=2,\dots,7$). Sia $w$ il vertice rimanente, allora, dato che $\deg w \ge 2$, esiste $i$ tale che $\{w,v_i\}\in E(G)$, pertanto $(w,v_i,v_1)$ è un cammino che collega $w$ a $v_1$. Ogni vertice è quindi collegabile al vertice $v_1$ e pertanto il grafo è connesso.     

Soluzione dell'esercizio 5 Dato che $G$ ha almeno due vertici, $C_w(G)$ ne ha almeno $3$. Osserviamo che $C_w(G)-w = G$ e quindi è connesso. Se invece $v\in V(G)$ allora

$$\begin{eqnarray*} V(C_w(G)-v) & = & V(C_w(G)) -\{w\} =(V-\{v\})\cup\{w\} = V(C_... ...\big\{\{w,u\}\bigm\vert u\in V(G-v)\big\}=\\ & = & E(C_w(G-v)) \end{eqnarray*}$$

ossia $C_w(G)-v=C_w(G-v)$ e questo è connesso in quanto ogni vertice è adiacente a $w$.     

Soluzione dell'esercizio 6 $G_1$ e $G_2$ sono isomorfi. Un isomorfismo è dato ad esempio da:

$$\begin{array}{lcl} A \mapsto a && D \mapsto e\\ B \mapsto b && E \mapsto d\\ C \mapsto f && F \mapsto c \end{array}$$

$G_2$ e $G_3$ non sono isomorfi, infatti $G_2$ contiene un $3$-ciclo $(a,b,c,a)$, (anzi due) mentre $G_3$ non ne contiene nessuno. Per vedere questo fatto si osservi che per ogni vertice $v$ del grafo i tre vertici a lui adiacenti, non sono tra loro adiacenti.