Matematica Discreta

Prova informale

25 marzo 1999

Da svolgersi in 2 ore senza l'ausilio di libri o appunti.

Esercizio 1   Siano $F_i$ i numeri di Fibonacci. Si provi che

$$\sum_{i=1}^nF_i=F_{n+2}-1.$$

Soluzione

Esercizio 2   Si trovino le soluzioni del sistema di congruenze:

$$\left\{ \begin{array}{ll} x \cong 2 &\quad{\rm mod}\ 113 \\ x \cong 87 &\quad{\rm mod}\ 84 \end{array}\right.$$

Soluzione

Esercizio 3   Per ogni $x,y\in\mathbb{Q}$ sia $x * y=x+y-xy$. Dire, giustificando la risposta, se $(\mathbb{Q},*)$ è un semigruppo oppure un monoide oppure un gruppo.
Soluzione

Esercizio 4   Si dimostri che $\{\sigma\in S_n\mid \sigma(1)=1\}$ è un sottogruppo di $S_n$.
Soluzione

Esercizio 5   Si dimostri che l'insieme $G=\{(a,b)\mid a\in\mathbb{Q}^*\hbox{\rm { e }}b\in\mathbb{Q}\}$ dotato dell'operazione

$$(a,b)(c,d)=(ac, ad+b)$$

è un gruppo. (Si ricorda che $\mathbb{Q}^*=\mathbb{Q}-\{0\}$)

Detti

$$\begin{array}{rcl} X_1&=&\{(a,b)\in G \mid a=1\} \\ X_2&=&\... ...Z}\} \\ X_3&=&\{(a,b)\in G \mid a,b\in\mathbb{Z}\} \end{array}$$

si dica quali tra $X_1$, $X_2$ e $X_3$ sono sottogruppi e quali no.
Soluzione

Esercizio 6   Sia $X$ un insieme e siano $A_1,\dots,A_n\subseteq X$. Si provi che allora

$$A_1\bigtriangleup A_2\bigtriangleup \dots\bigtriangleup A_n=\{x\mid x\in A_i\hbox{\rm { per un numero dispari di }}i\}$$

essendo $\bigtriangleup$ la differenza simmetrica (i.e. $A\bigtriangleup B=(A-B)\cup(B-A)$).
[Suggerimento: si usi l'induzione su $n$]
Soluzione