Lezione 8 (21 marzo 2001 h. 10.30-11.30)

Scrittura in base arbitraria dei naturali.

Definizione 8.1   Sia $b\mathbb N$. Diremo che $n\in\mathbb N$ è rappresentabile in base b se esistono numeri $\varepsilon_0,\varepsilon_1,\dots,\varepsilon_k\in\{0,1,\dots,b-1\}$ tali che $n=\varepsilon_0 +\varepsilon_1b+\varepsilon_2 b^2+\dots \varepsilon_k b^k$.

Osservazione 8.2   La rappresentabilità in base b può essere espressa anche nel seguente modo: esiste una successione $\{\varepsilon_i\}_{i\in\mathbb N}$ di interi tali che:

1.

  $\{\varepsilon_i\}$ è definitivamente nulla (i.e. esiste $i_0\in\mathbb N$ tale che $\varepsilon_i=0$ per ogni i>i₀);

2.

  $0\le\varepsilon_i<b$ per ogni $i\in\mathbb N$;

3.

  $n=\sum_{i=0}^\infty \varepsilon_i b^i$.

Questo perché la condizione (1) implica che la somma in (3) ha un numero finito di addendi non nulli.

Osservazione 8.3   Si osservi che l'unico numero rappresentabile in base 1 è lo 0. In questo caso infatti la condizione (2) implica che ogni $\varepsilon_i=0$.

 

Teorema 8.4 (scrittura dei naturali in base arbitraria)   Sia $b\mathbb N$. Allora ogni $n\in\mathbb N$ è rappresentabile in modo unico in base b. Ossia esiste esiste una successione $\{\varepsilon_i\}_{i\in\mathbb N}$ come nell'osservazione precedente e se $\{\varepsilon'_i\}_{i\in\mathbb N}$ è un'altra tale successione, allora $\varepsilon_i=\varepsilon_i'$ per ogni $i\in\mathbb N$.

Dimostrazione.  Dimostriamo l'esistenza per induzione su n. Se n=0 basta prendere $\varepsilon_i=0$ per ogni $i\in\mathbb N$. Supponiamo ora n>0 e che la tesi sia vera per ogni k<n. Siano q,r tali che n=bq+r con $0\le r<b$. Dato che $b\ge 2$ si ha che $0\le q<bq\le bq+r=n$ e quindi per ipotesi di induzione esiste una successione definitivamente nulla $\{\delta_i\}$, costituita di interi tali che $0\le\delta_i<b$ per ogni i e tale che $q=\sum\limits_{i=0}^\infty \delta_i b^i$. Ma allora

$$n=bq+r=b\sum\limits_{i=0}^\infty \delta_i b^i+r=\sum\limits_{... ...ty\delta_{i-1}b^i+r=\sum\limits_{i=0}^\infty \varepsilon_i b^i$$

dove si è posto $\varepsilon_0=r$ e $\varepsilon_i=\delta_{i-1}$ per ogni i>0. La successione $\{\varepsilon_i\}$ è definitivamente nulla, dato che lo è $\{\delta_i\}$ ed inoltre $0\le\varepsilon_i=\delta_{i-1}<b$ per ogni i>0 e $0\le\varepsilon_0=r<b$.

Dimostriamo ora l'unicità. Procediamo per induzione su n. Se $n=0=\sum_i\varepsilon_ib^i$ allora ogni addendo della somma essendo non negativo, deve essere nullo e quindi $\varepsilon_i=0$ per ogni i.

Supponiamo ora n>0 e che l'espressione in base b sia unica per tutti i numeri k<n. Sia n tale che $n=\sum\limits_{i=0}^\infty \varepsilon_i b^i=\sum\limits_{i=0}^\infty \varepsilon'_i b^i$. Allora possiamo scrivere

$$n=b\sum\limits_{i=1}^\infty \varepsilon_i b^{i-1}+\varepsilon... ...\sum\limits_{i=1}^\infty \varepsilon'_i b^{i-1}+\varepsilon'_0$$

ma per l'unicità della divisione euclidea si ha che $\varepsilon_0=\varepsilon'_0$ e $q=\sum\limits_{i=1}^\infty \varepsilon_i b^{i-1}=\sum\limits_{i=1}^\infty \varepsilon'_i b^{i-1}$. Come prima q<n e quindi per ipotesi di induzione si ha anche che $\varepsilon_i=\varepsilon'_i$ per ogni $i\ge1$.     $\square$

   
Il coefficiente binomiale

Definizione 8.5   Siano n, $k\in \mathbb N$ con $k\le n$ si pone

$${n \choose k}= \frac {n!}{(n-k)! k !}$$

Osservazione 8.6   È immediato verificare che ${n \choose k}={n \choose n-k}$.

Esercizio 8.1      Provare che

$${n+1 \choose k} = {n \choose k}+{n \choose k-1}.$$

Soluzione

   
k-sottinsiemi

Definizione 8.7   Sia X un insieme e $k\in \mathbb N$, un sottinsieme $A\subseteq X$ sarà detto un k-sottinsieme se $\left\vert A\right\vert =k$. Denoteremo con ${X \choose k}$ l'insieme dei k-sottinsiemi di X. I k-sottinsiemi sono anche chiamati k-combinazioni semplici.

Proposizione 8.8   Se X è finito e $k\le \left\vert X\right\vert$, allora

$$\left\vert{X \choose k}\right\vert={\left\vert X\right\vert \choose k}.$$

Dimostrazione.  Procediamo per induzione su $\left\vert X\right\vert$. Se $\left\vert X\right\vert=0$ allora k=0 e $X=\varnothing$. Ma allora

$$\left\vert{\varnothing \choose 0}\right\vert=\left\vert\{\var... ...=1={0 \choose 0}={\left\vert\varnothing\right\vert \choose 0}.$$

Supponiamo ora che $\left\vert X\right\vert>0$. Se $k=\left\vert X\right\vert$, allora ${X \choose k}=\{X\}$ e quindi $\left\vert{X \choose k}\right\vert=1$. D'altra parte anche ${\left\vert X\right\vert \choose k}=1$. ANche il caso k=0 è facile. Supponiamo allora $0<k<\left\vert X\right\vert$. Fissiamo $x_0\in X$ un elemento e poniamo

$$\begin{array}{rcl} {\cal A}_1 & = &\{A\subset X\mid \left\ve... ...\vert A\right\vert=k\hbox{\rm { e }} x_0\not\in A\} \end{array}$$

chiaramente si ha

$${X \choose k}={\cal A}_1\cup{\cal A}_2,\qquad {\cal A}_1\cap{\cal A}_2=\varnothing$$

da cui $\left\vert{X \choose k}\right\vert=\left\vert{\cal A}_1\right\vert+\left\vert{\cal A}_2\right\vert$ )cfr esercizio4.2). Posto $X'=X-\{x_0\}$ si ha che

$${\cal A}_2={X' \choose k}.$$ (7)

inoltre la funzione $F:{X' \choose k-1}\to {\cal A}_1$ definita da $F(A)=A\cup\{x_0\}$ è una bigezione e quindi, dato che $\left\vert X'\right\vert=\left\vert X\right\vert-1$, per ipotesi di induzione si ha

$$\begin{eqnarray*}\left\vert{\cal A}_1\right\vert&=*\left\vert{X' \choose k-1}\ri... ...rt{X' \choose k}\right\vert={\left\vert X'\right\vert \choose k} \end{eqnarray*}$$

Ma allora, usando il risultato dell'esercizio 8.1

$$\left\vert{X \choose k}\right\vert={\left\vert X'\right\vert ... ...'\right\vert+1 \choose k}={\left\vert X\right\vert \choose k}.$$

    $\square$

Esercizio 8.2    Provare che

$${n \choose 0}+{n \choose 1}+\dots+{n \choose n-1}+{n \choose n}=2^n$$

Soluzione

Perché non gioco al Superenalotto!

Una sestina al Superenalotto, è un sottinsieme di 6 elementi dell'insieme dei numeri naturali da 1 a 90, quindi, per la proposizione 8.8 il numero di sestine possibili è dato da:

$${90 \choose 6}=622614630$$

Pertanto, la probabilità di vincere giocando una sestina è pari a $1/622614630=0.000000161\ \%$ di vincere giocando una sestina. Se quindi il gioco fosse equo, la puntata su una giocata dovrebbe essere pagata 622614630volte la posta. Dato che la puntata su una sestina costa 800 L., mi aspetterei, in caso di successo, un premio di $800\cdot 622614630 =498091704000$L.

Un montepremi così alto non si è ancora visto!