Matematica Discreta, II modulo

Prima prova in itinere, a.a. 2000/2001

27 aprile 2001

Da svolgersi in tre ore. Si richiede che vengano svolti a scelta quattro (e non più di qyuattro) dei cinque esercizi e che si risponda alla domanda di teoria.

Esercizio 1   Siano $X$, $Y$, $A$ insiemi. Si provi che $(X\times Y)^A$ è in corrispondenza biunivoca con $X^A\times Y^A$.
Soluzione

Esercizio 2   Siano $X,Y$ insiemi finiti, e $A\subseteq X$, $B\subseteq Y$. Posto $\left\vert X\right\vert=n$, $\left\vert Y\right\vert = m$, $\left\vert A\right\vert = h$ e $\left\vert B\right\vert = k$ si determini, in funzione di $n,m,k,h$ la cardinalità degli insiemi

$$\begin{eqnarray*} {\cal F}_1 & = & \big\{f\in Y^X \bigm\vert f(A)\cap B \ne \va... ...rm { \\lq e iniettiva e }} \left\vert f(A)\cap B\right\vert=1\big\} \end{eqnarray*}$$

[Suggerimento per il primo punto: si osservi che ${\cal F}_1$ è il complementare di $\big\{f\in Y^X \bigm\vert f(A)\cap B = \varnothing \big\}$.]
Soluzione

Esercizio 3   Dire se il sistema di congruenze

$$\left\{ \begin{array}{ll} x \cong 112 &\quad{\rm mod} 72 \\ x \cong 4 &\quad{\rm mod} 330 \end{array} \right.$$

Soluzione

Esercizio 4   Si determinino le soluzioni della congruenza $x^{23}\cong 5 \quad{\rm mod} 12$.
Soluzione

Esercizio 5   Sia $a\in\mathbb{Z}$ e $\{x_n\mid n\in\mathbb{N}\}$ una successione di interi tali che

$$x_{n+2}=ax_{n+1}+x_{n}\quad\forall n\in\mathbb{N}.$$

Si provi che allora $(x_{n+1},x_{n})=(x_1,x_0)$ per ogni $n\in\mathbb{N}$.

Supponendo che $a\ge 0$ e che $x_0=0$ e $x_1=1$ si provi che $x_n\ge a^{n-1}$ per ogni $n\ge 1$.
Soluzione

Domanda di teoria.  Si dia la definizione di massimo comun divisore tra numeri interi e si enunci e si dimostri il teorema di esistenza e unicità del massimo comun divisore.