Matematica Discreta, II modulo

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

14 aprile 2000

Da svolgersi in due ore. Ai cinque esercizi è sono assegnati rispettivamente i seguenti punteggi:

Esercizio 1: $9/30$, Esercizio 2: $9/30$, Esercizio 3: $6/30$, Esercizio 4: $7/30$, Esercizio 5: $9/30$.

Esercizio 1   Siano $n,m\in\mathbb{Z}-\{0\}$, tali che $n\mathrel{\big\vert}m$. Si provi che

1. per ogni $a\in\mathbb{Z}$ si ha $(a,n)\mathrel{\big\vert}(a,m)$
2. per ogni $a\in\mathbb{Z}$ si ha $(a,m)/(a,n)\mathrel{\big\vert}m/n$ [Suggerimento: se $m=kn$, si usi il fatto che $(ka,m)=(ka,kn)=k(a,n)$.]

Soluzione

Esercizio 2   Sia $x_n$ la successione definita ricorsivamente da:

$$\left\{ \begin{array}{rcl} x_{n+2} & = & 3 x_{n+1} + 2 x_n \\ x_{0} & = & 0 \\ x_{1} & = & 1 \end{array} \right.$$

1. Si provi che per ogni $n \ge 1$ il numero $x_n$ è un intero dispari.
2. Si provi che per ogni $n\in \mathbb{N}$ si ha che $(x_{n+1},x_n)=1$.
3. Si determini una forma esplicita di $x_n$.

Soluzione

Esercizio 3   Dire se il sistema di congruenze

$$\left\{ \begin{array}{ll} x \cong 27 &\quad{\rm mod}\ 218 \\ x \cong 31 &\quad{\rm mod}\ 102 \end{array} \right.$$

Soluzione

Esercizio 4   Si determini il numero di anagrammi della parola

ABRACADABRA.

Si determini inoltre il numero di quelli che iniziano con la lettera A.
Soluzione

Esercizio 5   Si consideri l'applicazione $\sigma:\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}14\mathbb{Z}}} {{}_{... ...{}_{\!\scriptstyle {}14\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}14\mathbb{Z}}}$ definita da $\sigma(x)=3x+1$ (somma e prodotto sono intesi in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}14\mathbb{Z}}} {{}_{\!\text... ...{}_{\!\scriptstyle {}14\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}14\mathbb{Z}}}$).

1. Si provi che $\sigma$ è una permutazione.
2. Si determini la decomposizione in cicli disgiunti di $\sigma$
3. Si determini il minimo naturale $n$ tale che $\sigma^n={\rm id}$

Soluzione