next up previous
Up: Matematica Discreta (II modulo) Previous: Lezione 22 (30 maggio

Soluzione di alcuni degli esercizi proposti

Soluzione dell'esercizio 1.1  

    /icons/back.gif


Soluzione dell'esercizio 1.2  

    /icons/back.gif


Soluzione dell'esercizio 1.3  

    /icons/back.gif


Soluzione dell'esercizio 1.4  

    /icons/back.gif


Soluzione dell'esercizio 1.5  

    /icons/back.gif


Soluzione dell'esercizio 1.6  

    /icons/back.gif


Soluzione dell'esercizio 1.7  

    /icons/back.gif


Soluzione dell'esercizio 1.8  

    /icons/back.gif


Soluzione dell'esercizio 1.9  

    /icons/back.gif


Soluzione dell'esercizio 2.1  

    /icons/back.gif


Soluzione dell'esercizio 2.2  

    /icons/back.gif


Soluzione dell'esercizio 2.3  

    /icons/back.gif


Soluzione dell'esercizio 2.4  

    /icons/back.gif


Soluzione dell'esercizio 2.5  

    /icons/back.gif


Soluzione dell'esercizio 3.1  

    /icons/back.gif


Soluzione dell'esercizio 3.2  Proviamo soltanto l'associatività della somma. Dobbiamo provare che per ogni $n,m,k\in\mathbb N$ si ha che (n+m)+k=n+(m+k). Procediamo per induzione su k. Se k=0 dalla definizione si ha (n+m)+ 0 =n+m e anche n+(m+0)=n+(m)=n+m. Supponiamo la tesi vera per k e proviamola per $\mathop{\rm succ}\nolimits(k)$.

\begin{eqnarray*}(m+n)+\mathop{\rm succ}\nolimits(k) & = & \mathop{\rm succ}\nol...
...thop{\rm succ}\nolimits(n+k)=m+(n+\mathop{\rm succ}\nolimits(k))
\end{eqnarray*}


    /icons/back.gif


Soluzione dell'esercizio 3.3  

    /icons/back.gif


Soluzione dell'esercizio 4.2  Siano $f:X\to I_n$ e $g:Y\to I_n$ due bigezioni, allora l'applicazione $h:I_{n+m}\to X\cup Y$ definita da

\begin{displaymath}h(i)=\Big\langle
\begin{array}{lcl}
f(i) &&\hbox{\rm {se }} i<n \\
g(i-n) && \hbox{\rm {se }} n\le i < m+n
\end{array}\end{displaymath}

è una bigezione.

Per la seconda parte si osservi innanzitutto che $X= (X-Y)\cup (X\cap Y)$ e che $(X-Y)\cap (X\cap Y)=\varnothing$ e che quindi per l'esercizio precedente,

\begin{displaymath}\left\vert X\right\vert = \left\vert X-Y\right\vert + \left\vert X\cap Y\right\vert
\end{displaymath}

osserviamo inoltre che $X\cup Y=(X-Y)\cup Y$ con $(X-Y)\cap Y=\varnothing$e quindi $\left\vert X\cup Y\right\vert= \left\vert X-Y\right\vert+ \left\vert Y\right\vert$, da cui

\begin{displaymath}\left\vert Y\right\vert=\left\vert X\cup Y\right\vert - \left\vert X-Y\right\vert
\end{displaymath}

sommando queste due relazioni si ottiene la tesi.     /icons/back.gif


Soluzione dell'esercizio 4.3  Procediamo per induzione su n. Se n=1 non c'è nulla da dimostrare. Supponiamo la tesi vera per n, usando l'associatività dell'unione si ha

\begin{displaymath}\bigcup_{i=1}^{n+1} X_i= ( \bigcup_{i=1}^{n} X_i )\cup X_{n+1}
\end{displaymath}

e dato che gli Xi sono a due a due disgiunti, anche $ ( \bigcup_{i=1}^{n}
X_i )\cap X_{n+1}=\varnothing$, ma allora per l'esercizio precedente, e l'ipotesi di induzione, si ha che

\begin{displaymath}\left\vert\bigcup_{i=1}^{n+1} X_i\right\vert=
\left\vert\big...
...t X_{n+1}\right\vert=\sum_{i+1}^{n+1}\left\vert X_i\right\vert
\end{displaymath}

    /icons/back.gif


Soluzione dell'esercizio 4.4  

    /icons/back.gif


Soluzione dell'esercizio 4.5  

    /icons/back.gif


Soluzione dell'esercizio 4.6  

    /icons/back.gif


Soluzione dell'esercizio 5.1   Se una tale g esiste, f è surgettiva, dato che per ogni $y\in Y$si ha che f(g(y))=y.

Viceversa, supponiamo che f sia surgettiva, allora $f^{-1}(y)\ne\varnothing$ per ogni $y\in Y$, per l'assioma di scelta, esiste una funzione di scelta, $g:Y\to\bigcup_{y\in
Y}f^{-1}(y)$, tale che $g(y)\in f^{-1}(y)$ per ogni $y\in Y$, ma ciò significa che f(g(y))=y per ogni $y\in Y$, ossia che g è una inversa destra di f.     /icons/back.gif


Soluzione dell'esercizio 5.2  Se una tale g esiste allora f deve necessariamente essere iniettiva, infatti se f(x1)=f(x2) allora x1=g(f(x1))=g(f(x2))x2.

Viceversa, supponiamo che f sia iniettiva. Allora per ogni $y\in f(X)$ esiste un unico $x_y\in X$ tale che f(xy)=y. Preso un arbitrario $\overline{x}\in X$definiamo $g:Y\to X$ ponendo

\begin{displaymath}g(y)=\Big\langle
\begin{array}{lcl}
x_y &&\hbox{\rm {se }}y...
...) \\
\overline{x} &&\hbox{\rm {se }}y\notin f(X)
\end{array}\end{displaymath}

Dato che per ogni $x\in X$ l'unico elemento avente f(x) come immagine è x stesso, si ha che g(f(x))=x.     /icons/back.gif


Soluzione dell'esercizio 5.3  

    /icons/back.gif


Soluzione dell'esercizio 6.1  

    /icons/back.gif


Soluzione dell'esercizio 6.2  A partire dagli Xm costruiamo dei nuovi insiemi, ponendo

\begin{eqnarray*}Y_0 & = & X_0 \\
Y_{n+1} & = & X_{n+1} - \bigcup_{m=0}^{n} X_m \qquad \forall n \ge 0
\end{eqnarray*}


Gli insiemi in questione sono a due a due disgiunti, e $\bigcup_nY_n=\bigcup_nX_n$. Si consideri l'insieme $A=\{n\in\mathbb N\mid
Y_n\ne\varnothing\}$, allora $Y=\bigcup_{n\in A}Y_n$. Per quanto visto in precedenza Aè finito o numerabile. Nel primo caso A è finito, nel secondo caso è numerabile.     /icons/back.gif


Soluzione dell'esercizio 6.3  Come nell'esercizio precedente, poniamo

\begin{eqnarray*}Y_0 & = & X_0 \\
Y_{n+1} & = & X_{n+1} - \bigcup_{m=0}^{n} X_m \qquad \forall n \ge 0
\end{eqnarray*}


Gli insiemi in questione sono a due a due disgiunti, e $\bigcup_nY_n=\bigcup_nX_n$. Si consideri l'insieme $A=\{n\in\mathbb N\mid
\left\vert Y_n\right\vert=\aleph_0\}$, $B=\{n\in\mathbb N\mid Y_n\ne\varnothing\hbox{\rm { ed \\lq e finito}}\}$, allora $Y=\bigcup_{n\in A}Y_n\cup\bigcup_{n\in B}Y_n$. Per quanto visto in precedenza A, e B sono finiti o numerabili. Dato che Y0 è numerabile, $A\ne\varnothing$e quindi $\bigcup_{n\in A}Y_n$ è numerabile. D'altra parte $\bigcup_{n\in
B}Y_n$ è finito o numerabile e quindi la loro unione è numerabile.     /icons/back.gif


Soluzione dell'esercizio 6.4  

    /icons/back.gif


Soluzione dell'esercizio 6.5  

    /icons/back.gif


Soluzione dell'esercizio 6.6  

    /icons/back.gif


Soluzione dell'esercizio 6.7  La funzione $f:(0,1)\to\mathbb R$ definita da $f(t)=\tan(\pi t-\pi/2)$ è una bigezione.     /icons/back.gif


Soluzione dell'esercizio 6.8  Osserviamo che X-Y non può essere né finito né numerabile, altrimenti $X=(X-Y)\cup Y$ sarebbe numerabile. Ma allora X-Ycontiene un sottinsieme, Y', numerabile. Dato che Y e Y' sono entrambi numerabili, la loro unione è numerabile, sia quindi $f:Y'\to Y\cup Y'$ una bigezione e si definisca $g:X-Y\to X$ ponendo:

\begin{displaymath}g(x)=\Big\langle
\begin{array}{lcl}
f(x) &&\hbox{\rm {se }} x\in Y' \\
x &&\hbox{\rm {se }} x\in X-(Y\cup Y')
\end{array}\end{displaymath}

g è chiaramente una bigezione.     /icons/back.gif


Soluzione dell'esercizio 6.9  Per ogni $k\in \mathbb N$ sia $F_k=\{A\in 2^\mathbb N\mid \left\vert A\right\vert = k\}$. Chiaramente $F=\bigcup_{k\in\mathbb N}F_k$. Proviamo che $\left\vert F_k\right\vert=\aleph_0$ per ogni $k\ge
1$. Procediamo per induzione su k. Se k=1 allora l'applicazione $n\to \{n\}$è una bigezione $\mathbb N\to F_1$. Supponiamo che Fk sia numerabile, allora per ogni $A\in F_k$ sia $F_{k+1}(A)=\{B\in F_{k+1}\mid B\supseteq A\}$. per ogni Al'insieme Fk+1(A) è numerabile, in quanto in bigezione con $\mathbb N-A$, inoltre $F_{k+1}-\bigcup_{A\in F_k}F_{k+1}(A)$ è numerabile in quanto unione di una famiglia numerabile di insiemi numerabili.     /icons/back.gif


Soluzione dell'esercizio 6.10  

    /icons/back.gif


Soluzione dell'esercizio 7.1  

    /icons/back.gif


Soluzione dell'esercizio 7.2  

    /icons/back.gif


Soluzione dell'esercizio 7.3  

    /icons/back.gif


Soluzione dell'esercizio 7.4  

    /icons/back.gif


Soluzione dell'esercizio 8.1  Dalla definizione del coefficiente binomiale si ha

\begin{displaymath}{n \choose k}+{n \choose k-1} =
\frac{n!}{k!(n-k)!}+\frac{n!...
...)!(n-k+1)!} =
\frac{n!(n+1)}{(k)!(n-k+1)!} =
{n+1 \choose k}
\end{displaymath}

    /icons/back.gif


Soluzione dell'esercizio 8.2  Si osservi che se X è un insieme con n elementi, allora

\begin{displaymath}2^X=\bigcup_{i=0}^n{X \choose k}
\end{displaymath}

e che questi insiemi sono a due a due disgiunti. Quindi

\begin{displaymath}2^n=2^{\left\vert X\right\vert}=\left\vert 2^X\right\vert=\su...
...n{\left\vert X\right\vert \choose k}=\sum_{i=0}^n{n \choose k}
\end{displaymath}

    /icons/back.gif


Soluzione dell'esercizio 10.1  Procediamo per induzione su k. Se k=1 non c'è nulla da dimostrare. Supponiamo che la tesi sia vera per k e supponiamo che $p\mathrel{\big\vert}n_1n_2\dots n_{k+1}$, ossia $p\mathrel{\big\vert}(n_1n_2\dots
n_k)n_{k+1}$. Per il corollario 10.2, si ha che $p\mathrel{\big\vert}
n_1n_2\dots n_k$ oppure $p\mathrel{\big\vert}n_{k+1}$. Se si verifica la seconda eventualità abbiamo finito, altrimenti, per ipotesi di induzione esiste $i\in \{1,\dots,k\}$ tale che $p\mathrel{\big\vert}n_i$, e quindi si conclude.     /icons/back.gif


Soluzione dell'esercizio 10.2  

    /icons/back.gif


Soluzione dell'esercizio 10.3  

    /icons/back.gif


Soluzione dell'esercizio 10.4  Chiaramente $\prod _{i=1}^s p_i^{k_i\wedge h_i}$ è un divisore comune a n e m. Inoltre se c è un divisore comune non può avere fattori primi diversi dai pi, quindi $c=\prod _{i=1}^s p_i^{l_i}$. Dal fatto che $c\mathrel{\big\vert}n $ segue allora che $l_i\le k_i$ e dal fatto che $c\mathrel{\big\vert}m$ segue che $l_i\le
h_i$ per ogni i, e quindi $l_i\le k_i\wedge h_i$.

La formula per il m.c.m. segue allora dal fatto che $[n,m]=\left\vert nm\right\vert/(n,m)$, e che per ogni coppia di numeri reali si ha che $h+k-h\wedge k=h\vee k$.     /icons/back.gif


Soluzione dell'esercizio 11.1  

    /icons/back.gif


Soluzione dell'esercizio 12.1  

    /icons/back.gif


Soluzione dell'esercizio 12.2  

    /icons/back.gif


Soluzione dell'esercizio 13.1  

    /icons/back.gif


Soluzione dell'esercizio 13.2  

    /icons/back.gif


Soluzione dell'esercizio 13.3  Osserviamo che $(a,pq)\ne1$ se e solo se $p \mathrel{\big\vert}a$ o $p \mathrel{\big\vert}a$, ma i numeri più piccoli di pq che sono divisibili per p sono p, $2p,\dots,qp$, quelli che sono divisibili per q sono invece q, $2q,\dots,pq$ e quindi i numeri più piccoli di pq e non coprimi con pq sono p+q-1. Quindi $\Phi(pq)=pq-(p+q-1)=(p-1)(q-1)$.     /icons/back.gif


Soluzione dell'esercizio 13.4   $\Phi(n)=(p-1)(q-1)=pq -p -q +1= n -p -q +1$ da cui $p+q=n+1-\Phi(n)$. Quindi p e q sono determinati dal sistema di equazioni

\begin{displaymath}\left\{
\begin{array}{l}
p+q=n+1-\Phi(n) \\
pq=n
\end{array} \right.
\end{displaymath}

Una semplice sostituzione mostra che allora p e q devono essere le due radici dell'equazione $x^2-(n+1-\Phi(n))+n=0$.     /icons/back.gif


Soluzione dell'esercizio 13.5  

    /icons/back.gif


Soluzione dell'esercizio 14.1  

    /icons/back.gif


Soluzione dell'esercizio 14.2  

    /icons/back.gif


Soluzione dell'esercizio 14.3  

    /icons/back.gif


Soluzione dell'esercizio 14.4  

    /icons/back.gif


Soluzione dell'esercizio 14.5  

    /icons/back.gif


Soluzione dell'esercizio 14.6  

    /icons/back.gif


Soluzione dell'esercizio 14.7  

    /icons/back.gif


Soluzione dell'esercizio 14.8  

    /icons/back.gif


Soluzione dell'esercizio 14.9  La colorazione dei lati data in figura 11

  
Figure 11: Soluzione grafica dell'esercizio 14.9
\begin{figure}
\begin{center}
\mbox{\psfig{file=petersen1.ps,width=5cm} ~~~%
\psfig{file=petersen2.ps,width=5cm} }
\end{center} \end{figure}

suggerisce come definire l'isomorfismo. Precismante se si definisce la funzione $f:\{1,2,\dots,10\}\to\{a,b,\dots,j\}$ ponendo

\begin{displaymath}\begin{array}{rclcrclcrclcrclcrcl}
f(1)&=&a &\quad & f(2)&=&...
...d & f(8)&=&h &\quad & f(9)&=&i &\quad &
f(10)&=&j
\end{array}\end{displaymath}

una semplice verifica mostra che f è un isomorfismo.     /icons/back.gif


Soluzione dell'esercizio 14.10  

    /icons/back.gif


Soluzione dell'esercizio 14.11  

    /icons/back.gif


Soluzione dell'esercizio 14.12  Se identifichiamo la lettera a con il numero 0 e la b con l'1, si ottiene una identificazione delle parole con le coordinate dei vertici del cubo di $\mathbb R^3$ dato da $[0,1]\times[0,1]\times[0,1]$. Inoltre due vertici di tale cubo sono congiunti da uno spigolo se solo se differiscono esattamente per una coordinata. L'identificazione data è quindi un isomorfismo di grafi tra G e G'.

  
Figure 12: L'isomorfismo tra i grafi dell'esercizio 14.12
\begin{figure}
\begin{center}
\psfig{file=cubo.ps,width=8cm} \end{center}\end{figure}

    /icons/back.gif


Soluzione dell'esercizio 16.1  La prima segue dal fatto che i vertici delle componenti connesse sono le classi d'equivalenza di una relazione d'equivalenza. La seconda, segue dal fatto che ogni lato di G deve essere lato di una qualche classe d'equivalenza, dato che i suoi estremi sono congiungibili e pertanto appartengono alla stessa classe d'equivalenza.     /icons/back.gif


Soluzione dell'esercizio 19.1  

    /icons/back.gif


Soluzione dell'esercizio 19.2  

    /icons/back.gif


Soluzione dell'esercizio 19.3  

    /icons/back.gif


Soluzione dell'esercizio 19.4  

    /icons/back.gif


Soluzione dell'esercizio 19.5  

    /icons/back.gif


Soluzione dell'esercizio 19.6  

    /icons/back.gif


Soluzione dell'esercizio 19.7  

    /icons/back.gif


Soluzione dell'esercizio 20.1  

    /icons/back.gif


Soluzione dell'esercizio 20.3  

    /icons/back.gif


Soluzione dell'esercizio 20.4  

    /icons/back.gif


Soluzione dell'esercizio 20.5  

    /icons/back.gif


Soluzione dell'esercizio 20.6  Siano $T_1,\dots,T_k$ le componenti connesse di F, allora ogni Ti è un albero, ma allora per ogni i si ha $\left\vert(\right\vert V(T_i))=\left\vert(\right\vert E(T_i))+1$. Dal fatto che $\sum_{i=1}^k\left\vert(\right\vert V(T_i)=\left\vert(\right\vert V)$ e $\sum_{i=1}^k\left\vert(\right\vert E(T_i)=\left\vert(\right\vert E)$segue immediatamente la tesi.     /icons/back.gif


Soluzione dell'esercizio 20.7  Sia T un albero generatore di G. Chiaramente $\left\vert V(T)\right\vert=\left\vert V(G)\right\vert$ e dato che T è un sottografo di G allora $\left\vert E(T)\right\vert\le \left\vert E(G)\right\vert$ e quindi, usando la formula che lega il numero di lati con il numero dei vertici di un grafo, si ha

\begin{displaymath}\left\vert E(G)\right\vert\ge \left\vert E(T)\right\vert = \left\vert V(T)\right\vert - 1 = \left\vert V(G)\right\vert - 1.
\end{displaymath}

    /icons/back.gif


Soluzione dell'esercizio 21.1  

    /icons/back.gif



next up previous
Up: Matematica Discreta (II modulo) Previous: Lezione 22 (30 maggio
Domenico Luminati
2001-06-18