ESERCIZI MATEMATICA DISCRETA (04/12/09) Soluzioni 1) Ogni parola del quesito dipende dalle variabili x

(1)

ESERCIZI MATEMATICA DISCRETA (04/12/09) Soluzioni

1) Ogni parola del quesito dipende dalle variabili x

1

= scelta delle 3 posizioni in cui inserire la lettera a

x

2

= scelta dei valori da inserire nella prima delle 2 rimanenti posizioni.

x

3

= scelta dei valori da inserire nella seconda delle 2 rimanenti posizioni.

I valori possibili di x

1

corrispondono alle combinazioni semplici di 5 posizioni prese a 3 a 3 e sono in numero di (

₃⁵

)=10. Fissato un valore di x

1

, i valori possibili di x

2

sono in numero di 4 (in tale posizione si deve inserire un valore scelto fra le 4 lettere b,c,d,e). Fissato un valore di x

1

e un valore di x

2

, i valori possibili di x

3

sono di nuovo in numero di 4. La risposta è il prodotto 1044=160 2) Applichiamo il principio di induzione al predicato P(n)=” (n

⁵

-n+20)/5 è intero ”.

P(1) è vero perché (1

⁷

-1+20)/5=4 è intero. Supponendo vero P(k), dimostriamo vero P(k+1)..

La tesi è dimostrare vero

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

⁵

-(k+1)+20]/5 è intero “.

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

^a

riga del triangolo di Tartaglia-Pascal) si ha:

[(k+1)

⁵

-(k+1)+20]/5=[k

⁵

+5k

⁴

+10k

³

+10k

²

+5k+1-k-1+20]/5=

= [(k

⁵

-k+20)/5]+k

⁴

+2k

³

+2k

²

+k

e tale numero é intero perché somma di interi (ricordando che per ipoetsi (k

⁷

-k+14)/7 è intero, perché supponiamo vero P(k))

3) Si effettuano 4 divisioni successive:

176 = 991+77 99 = 771+22 77 = 223+11 22 = 112+0

e si ottiene mcd(176,99)=11.

Si calcolano poi le successioni s

0

,s

1

,s

2

,s

3

,s

4

; t

0

,t

1

,t

2

,t

3

,t

4

ottenendo i valori : s

0

=1, s

1

=0, s

2

=1, s

3

=-1, s

4

=4; t

0

=0, t

1

=1, t

2

=-1, t

3

=2, t

4

=-7

da cui x=s

4

=4, y=t

4

=-7

4) Se A è l’insieme di tutte le parole di lunghezza 4 sull’alfabeto di 8 lettere, in corrispondenza delle 2 proprietà indicate nel suggerimento, si costruiscono 2 sottoinsiemi di A:

A

1

= { xA / la prima e la seconda lettera di x sono uguali } A

2

= { xA / la seconda e la terza lettera di x sono uguali } La risposta al quesito è la cardinalità dell’unione X

1

X

2

:

A

1

A

2

=A

1

+A

2

-A

1

A

2



Applicando il principio delle scelte multiple si hanno i seguenti valori:

A

1

=8

²

;A

2

=8

²

; A

1

A

2

=8 da cui A

1

A

2

=8

²

+8

²

-8=120

5) Se A è l’insieme di tutte le funzioni f: B={1,2,3,4}  C={1,2,3,4,5,6,7,8,9,10,11,12} (che ha cardinalità 12

⁴

), si costruiscono i 2 sottoinsiemi di A:

A

1

= { fA / f soddisfa la proprietà a)}

A

2

= { fA / f soddisfa la proprietà b)}

e si calcola A-A

1

A

2

. Si ha poi (applicando opportunamente il principio delle scelte multiple):

A

1

A

2

=A

1

+A

2

-A

1

A

2

=10

⁴

+1211109-10987

La risposta al quesito è dunque 12

⁴

-(10

⁴