1) Applichiamo il principio di induzione al predicato P(n)=” (n

(1)

ESERCIZI MATEMATICA DISCRETA (18/12/08) Soluzioni

1) Applichiamo il principio di induzione al predicato P(n)=” (n

⁷

-n+14) è multiplo di 7 ”.

P(1) è vero perché 1

⁷

-1+14 =14 è multiplo di 7. Supponendo vero P(k), dimostriamo vero P(k+1).

La tesi è dimostrare vero

P(k+1)=” [(k+1)

⁷

-(k+1)+14] è multiplo di 7 “.

Sfruttando lo sviluppo della potenza del binomio secondo Newton (utilizzando i coefficienti binomiali della 7

^a

riga del triangolo di Tartaglia-Pascal) si ha:

(k+1)

⁷

-(k+1)+14=k

⁷

+7k

⁶

+21k

⁵

+35k

⁴

+35k

³

+21k

²

+7k+1-k-1+14=

= (k

⁷

-k+14)+7k

⁶

+21k

⁵

+35k

⁴

+35k

³

+21k

²

+7k

e tale numero é multiplo di 7 perché somma di multipli di 7 (ricordando che (k

⁷

-k+14) è multiplo di 7 per ipotesi, perché supponiamo vero P(k)).

2) Si può applicare il principio di induzione al predicato P(n)=” 2

⁴ⁿ⁺¹

ha la cifra delle unità uguale a 2”.

P(1) è vero perché 2

⁴⁺¹

=2

⁵

=32 ha la cifra delle unità uguale a 2.

Supponendo vero P(k)=” 2

^4k+1

ha la cifra delle unità uguale a 2 “, dimostriamo vero:

P(k+1)=” 2

^4(k+1)+1

ha la cifra delle unità uguale a 2 “ Ma sviluppando con le regole sulle potenze si ha:

2

^4(k+1)+1

=2

^4k+4+1

=2

^4k+1

2

⁴

e si può notare che 2

^4k+1

ha la cifra delle unità uguale a 2 (per ipotesi) mentre 2

⁴

=16 ha la cifra delle unità uguale a 6, e moltiplicando un numero che ha la cifra delle unità uguale a 2 per un numero che ha la cifra delle unità uguale a 6 si ottiene certamente un numero che ha la cifra delle unità uguale a 2 (perché 26=12).

3) Essendo a,b coprimi si ha mcd(a,b)=1, e sappiamo che esistono due coefficienti interi relativi x,y tali che 1=ax+by. Se c è un qualunque numero naturale, moltiplicando ambo i membri per c si ha c=a(xc)+b(yc) e si ottiene che c è combinazione lineare di a,b con coefficienti interi relativi xc, yc rispettivamente.

4) Seguendo il suggerimento, si può usare il principio delle scelte multiple: i modi di scegliere i 6 lanci (fra 15) in cui esce un pari sono in numero di (

¹⁵₆

); fissati i 6 lanci, i modi di scegliere i numeri pari che escono in tali lanci sono in numero di 3

⁶

; fissati i 6 lanci e i numeri pari che escono in tali lanci, i modi di scegliere i numeri (dispari) che escono nei rimanenti 9 lanci sono in numero di 3

⁹

. La risposta è dunque il prodotto (

¹⁵₆

)3

⁶

3

⁹

=……….

5) Ognuno dei sottoinsiemi da contare si ottiene dall’unione di {1,2} (insieme fissato) con un sottoinsieme dell’insieme {3,4,5,6,7} (insieme variabile). Quindi il numero di tali sottoinsiemi coincide con il numero dei sottoinsiemi di {3,4,5,6,7} (che ha cardinalità 5) ed è dunque 2

⁵

.

6) Se X è l’insieme di tutte le matrici con 3 righe e 3 colonne nelle cui caselle sono inseriti valori 0,1, il quesito chiede di contare il numero di matrici di X che non soddisfano nessuna delle 3 proprietà seguenti: la prima riga contiene tutti 0; la seconda contiene tutti 0; la terza contiene tutti 0.

Quindi costruiamo i 3 sottoinsiemi di X: X

1

contenente le matrici con la prima riga che contiene tutti 0; X

2

contenente le matrici con la seconda riga che contiene tutti 0; X

3

contenente le matrici con la terza riga che contiene tutti 0. La risposta al quesito è: X-X

1

X

2

X

3

.

Si ha poi (applicando opportunamente il principo delle scelte multiple):

X=2

⁹

; X

1

X

2

X

3

=X

1

+X

2

+X

3

-[X

1

X

2

+X

1

X

3

+X

2

X

3

]+X

1

X

2

X

3

=

= 2

⁶

+2

⁶

+2

⁶

-[2

³

+2

³

+2

³

]+1.

Quindi la risposta è 2

⁹

-{2

⁶

+2

⁶

+2

⁶

-[2

³

+2

³

+2

³