Esercizi di Matematica Discreta - Parte II · · 2015-10-18Esercizi di Matematica Discreta -...

Esercizi di Matematica Discreta - Parte II

7 ottobre 2011

AVVISO: Sia i testi che gli svolgimenti proposti possono contenere errori e/o ripetizioni.Essi sono infatti opera di vari collage e, per ovvie questioni di tempo, non sono statirivisti. Pertanto non intendono sostituire alcun libro di esercizi. Gli studenti sono quindipregati di prestare particolare attenzione. Prego infine gli studenti di volermi cortesementeinformare sia direttamente che per e-mail ([email protected]) di qualunque erroreo sospetto di errore notato.

esercizi proposti agli studenti di matematica discreta (a.a. 2011-12) dal prof. s. milici 1

Indice

1 Calcolo combinatorio 3

2 Induzione 15

3 Teoria dei numeri 18


1 Calcolo combinatorio

1. Quante schedine devo giocare per essere certo di fare sei al superenalotto? E per il5 + 1?

2. In quanti anagrammi della parola GATTO la lettera O sta tra le due T (anche se letre lettere non sono consecutive)? Scrivere tutti gli anagrammi che soddisfano talecondizione.

3. In una societa il consiglio di amministrazione e composto da 5 membri: a, b, c, d, e.In quanti modi differenti si puo raggiungere una maggioranza che comprenda i duemembri a e b?. E se c non votera mai come d?

4. Quanti sono gli anagrammi della parola MATEMATICA che iniziano per M efiniscono per A?

5. Quanti sono i numeri interi positivi aventi 5 cifre e la cui terza cifra e uguale a 2?E se la terza cifra compresa fra 0 e 2?

6. Quanti sono i numeri pari di 5 cifre che risultano uguali leggendoli sia da sinistraverso destra che viceversa? Giustificare la risposta. (Esempio: 45154 e valido mentre05150 e 45152 non sono validi).

7. Per conseguire il diploma in una scuola di specializzazione bisogna superare 7 esami,di cui almeno 3 esami di discipline matematiche. Se gli insegnamenti matematicisono 5 ed i rimanenti sono 6, in quanti modi diversi si puo presentare il piano distudi?

8. In uno stabilimento un semilavorato e sottoposto a 5 lavorazioni diverse, a, b, c, d,e. Se la lavorazione a deve precedere quella b, in quanti modi diversi si possonoordinare le lavorazioni? E se anche la lavorazione c deve precedere quella d?

9. Una prova d’esame consiste in 6 domande con risposte del tipo vero o falso. Quantesono le possibili sequenze di risposte tali che ci siano almeno tre risposte vere e alpiu due risposte false?

10. Quanti sono i numeri naturali di sei cifre tali che il prodotto delle prime tre cifrevalga 9?

11. Calcolare (x+ y)5.

12. Trovare il coefficiente di x5y8 nello sviluppo di (x+ y)13.

13. Trovare il coefficiente di x9 nello sviluppo di (2− x)19.

14. Determinare il numero di parole di lunghezza 5 che si possono formare con al piu 4lettere uguali ad E, 2 uguali a R, 1 uguale a V, 1 uguale a G ed una uguale a N.


15. Dimostrare, per via combinatorica, la seguente uguaglianza:

k

(n

k

)= n

(n− 1

k − 1

).

Aiuto: contare il numero di modi in cui si puo partizionare un insieme di n elementiin tre sottoinsiemi A1, A2, A3 tali che |A1| = 1, |A2| = k − 1 e |A3| = n− k.

16. Nel piano cartesiano sono consentite le seguenti mosse (una alla volta):

(a) avanzare di 1 nella direzione positiva dell’asse ~x;

(b) avanzare di 1 nella direzione positiva dell’asse ~y.

Partendo da O ≡ (0, 0) quanti possibili percorsi esistono per raggiungere il puntoP ≡ (6, 7)?

17. Nello spazio sono consentite le seguenti mosse (una alla volta):

(a) avanzare di 1 nella direzione positiva dell’asse ~x;

(b) avanzare di 1 nella direzione positiva dell’asse ~y;

(c) avanzare di 1 nella direzione positiva dell’asse ~z.

Partendo da O ≡ (0, 0, 0) quanti possibili percorsi esistono per raggiungere il puntoP ≡ (6, 7, 5)?

18. Quante differenti partite di doppio possono giocare tra loro otto tennisti? (beatiloro che hanno questo tempo!)

19. In quanti modi 6 persone possono occupare 3 macchine aventi 6 posti ciascunasupposto che:

• sia le persone che le auto sono distinguibili?, oppure

• le persone sono indistinguibili mentre le auto sono distinguibili?, oppure

• le persone sono distinguibili mentre le auto sono indistinguibili?, oppure

• sia le persone che le auto sono indistinguibili?

(Suggerimento: se siete ricchi e non volete impazzire, regalate ad ogni persona unabella auto nuova!)

20. Determinare in quanti modi differenti 12 libri possono essere ordinati in 4 distingui-bili scaffali nel caso in cui

• i libri sono 12 copie identiche dello stesso libro;

• i libri sono tutti diversi fra loro.


21. In quante maniere diverse possono collocarsi due pedine su una scacchiera, sotto lacondizione che le due pedine siano su righe e colonne distinte e che

• le due pedine hanno lo stesso colore? oppure

• le due pedine hanno colore differente?

22. Quante sono le targhe automobilistiche di cui si sa che le prime due lettere sonouguali e le ultime due contengono almeno una B?

23. Alberto, Barbara, Chiara e Davide mescolano un mazzo di 40 carte e poi ne distri-buiscono 10 a testa. Alberto guarda le sue carte ed esclama: “Che strano, non honessuna carta di picche”. Sapendo questa informazione, qual’e al probabilita cheanche Barbara non abbia nessuna carta di picche? (nota: le carte di picche sono10).

24. La professoressa Scappavia insegna matematica in una scuola in cui si fano 6 ore dilezioni al giorno di lezione, dal lunedı al venerdı. Il suo orario settimanale prevede18 ore di insegnamento ed ella, per ragioni personali, gradirebbe non insegnaremai nell’ultima ora di lezione. La commissione che fa l’orario concede pero allaprofessoressa solo di scegliere la suddivisione giornaliera delle sue ore di lavoro,dopodiche il suo orario verra sorteggiato a caso. Quale delle seguenti disposizioniconviene scegliere alla professoressa per avere la maggior probabilita di non averemai l’ultima ora di lezione?

(a) 5-5-4-2-2;

(b) 5-4-4-3-2;

(c) 4-4-4-4-2;

(d) 4-4-4-3-3;

(e) sono tutte equivalenti.

25. In Italia le targhe automobilistiche sono composte da 2 lettere, seguite da 3 cifreed altre due lettere. Nel paese di Ailati le cose vanno alla rovescia e le targhe sonocomposte da 2 cifre, seguite da 3 lettere ed altre 2 cifre. Supponendo che in entrambii paesi si usino 10 cifre e 22 lettere (I, O, U, Q non sono utilizzate), determinarela differenza tra il numero di tutte le targhe possibili fra quelle italiane e quelle diAilati.

26. Qual’e il numero minimo di carte che bisogna pescare da un ordinario mazzo di52 carte (formato da 13 carte per ogni seme: cuori, fiori, picche, quadri) per averealmeno il cinquanta per cento di probabilita di estrarre una o piu carte di cuori?

27. In una ditta, ogni giorno, vengono assegnate 5 mansioni diverse a 5 impiegati. Inquanti modi si possono assegnare le mansioni in modo che nessun impiegato abbiala stessa mansione del giorno prima?


TRACCIA DELLO SVOLGIMENTO. Si tratta di una diversa formulazione delproblema degli accoppiamenti proibiti risolto a lezione mediante il principio di in-clusione esclusione. Brevemente, denotato con {I1, I2, I3, I4, I5} l’insieme degli im-piegati, il problema equivale a determinare il numero delle permutazioni dell’insieme{I1, I2, I3, I4, I5} verificanti la proprieta che Ii, per ogni i = 1, 2, . . . , 5, non appareal posto i-esimo.

28. (a) Un centro di calcolo ha 9 diversi programmi da far girare. Quattro sono scritti inC++ e cinque in BASIC. I programmi in C++ sono considerati indistinguibilifra loro e cosı quelli scritti in BASIC. Determinare in quanti modi diversi sipossono ordinare i 9 programmi per farli girare se:

• non vi e alcuna condizione;

• i programmi in C++ devono girare consecutivamente;

• sia i programmi in C++ che quelli in BASIC devono girare consecutiva-mente;

• i linguaggi devono essere alternati.

(b) Supponiamo che il costo per passare da un programma in C++ ad uno in BASICsia di 10 unita, quello per passare da uno in BASIC ad uno in C++ sia di 5 unitae che non vi sia alcun costo per passare fra programmi nello stesso linguaggio.Qual’e il piu efficiente (minor costo) modo di ordinare i programmi prima difarli girare?

(c) Ripetere la parte (a) nell’ipotesi che sia i programmi in C++ che quelli in BASICsiano distinguibili l’uno dall’altro.

29. In un magazzino si devono etichettare 625 articoli in modo che articoli distintiricevano etichete distinte. Ogni etichetta viene individuata da una parola di klettere prese da un alfabeto di n distinte lettere.

(a) Se n = 2 determinare il piu piccolo valore di k per cui si possano formaresufficienti parole. Quante parole non utilizzate rimangono?

(b) Esistono alfabeti con n caratteri che, per una opportuna scelta di k, permettonodi formare esattamente 625 parole? Quanti di questi alfabeti esistono? Perognuno di essi si determinino i valori di n e k.

SVOLGIMENTO.

• Quesito (a). Le parole di k lettere formate con un alfabeto di n lettere sononk, cioe le disposizioni con ripetizione delle n lettere prese a k a k. Se n = 2le parole di lunghezza k che si possono formare sono 2k. Avendosi 29 = 512e 210 = 1024, ne viene che k = 10 e il piu piccolo valore per cui si hannosufficienti parole per etichettare i 625 articoli. Le parole non utilizzate risultano1024− 625 = 399.


• Quesito (b). Poiche’ e 625 = 54 = (25)2 = (625)1, e dovendo essere 625 = nk,ne viene che esistono esattamente tre alfabeti rispettivamente con 5, 25 e 625caratteri con i quali si possono etichettare esattamente 625 articoli con parolerispettivamente di 4, 2, 1 caratteri.

30. In un magazzino si devono etichettare 343 articoli in modo che articoli distintiricevano etichete distinte. Ogni etichetta viene individuata da una parola di klettere prese da un alfabeto di n distinte lettere.

(a) Se n = 2 determinare il piu piccolo valore di k per cui si possano formaresufficienti parole. Quante parole non utilizzate rimangono?

SVOLGIMENTO. Le parole di k lettere formate con un alfabeto di n letteresono nk, cioe le disposizioni con ripetizione delle n lettere prese a k a k. Sen = 2 le parole di lunghezza k che si possono formare sono 2k. Avendosi28 = 256 e 29 = 512, ne viene che k = 9 e il piu piccolo valore per cui sihanno sufficienti parole per etichettare i 625 articoli. Le parole non utilizzaterisultano 512− 343 = 169.

(b) Esistono alfabeti con n caratteri che, per una opportuna scelta di k, permettonodi formare esattamente 343 parole? Quanti di questi alfabeti esistono? Perognuno di essi si determinino i valori di n e k.

SVOLGIMENTO. Poiche’e 343 = 73 = (343)1, e dovendo essere 343 = nk,ne viene che esistono esattamente due alfabeti rispettivamente con 7 e 343caratteri con i quali si possono etichettare esattamente 343 articoli con parolerispettivamente di 3 e 1 caratteri.

31. In un ospedale sono ricoverate 2000 persone. Si possono dimettere solo pazienti chenon accusano alcun sintomo di malattia. Fra i pazienti:

• 300 hanno problemi di stomaco,

• 200 hanno problemi di respirazione,

• 400 hanno la febbre.

Inoltre e noto che

• 25 hanno sia problemi di stomaco che di respirazione,

• fra quelli che hanno la febbre 100 hanno problemi di stomaco, 20 hanno pro-blemi di respirazione e 15 hanno entrambe le patologie.

Determinare il numero massimo di persone da dimettere.

32. Il direttore di una ditta deve scegliere un gruppo di persone da mandare in un paeseavente condizioni climatiche disagiate. Pertanto ogni operaio deve avere eta minoredi 40 anni e nessun problema di salute. Il personale a disposizione e di 1000 operai,di cui


• 200 hanno problemi di vista,

• 100 hanno problemi di cuore,

• 300 superano i 40 anni.

Inoltre e noto che

• 20 persone hanno sia problemi di vista che di cuore,

• fra le persone aventi piu di 40 anni 100 hanno problemi di vista, 40 hannoproblemi di cuore e 5 hanno entrambe le patologie.

Determinare il numero massimo di operai idonei.

33. Determinare la cardinalita dell’insieme di soluzioni intere del sistema

x1 + x2 + x3 + x4 = 20x1 ≥ −1x2 > 0x3 ≥ 0x4 > 3

SVOLGIMENTO. Il sistema assegnato equivale al seguente

x1 + x2 + x3 + x4 = 20x1 ≥ −1x2 ≥ 1x3 ≥ 0x4 ≥ 4

.

Posto z1 = x1 + 1, z2 = x2 − 1, z3 = x3 e z4 = x4 − 4, esso diventa

z1 + z2 + z3 + z4 = 16z1 ≥ 0z2 ≥ 0z3 ≥ 0z4 ≥ 0

.

Se con S denotiamo l’insieme delle sue soluzioni intere, si ha |S| = (16+4−1

3

)= 19!

3!·16! .

34. Determinare le cardinalita degli insiemi di soluzioni intere dei due seguenti sistemi:

(a)

x1 + x2 + x3 + x4 = 15x1 ≥ 3x2 > 0x3 ≥ 0x4 > 2

, (b)

x1 + x2 + x3 + x4 = 15x1 ≥ 0x2 ≥ 0x4 ≥ 0

.


SVOLGIMENTO. Sia Sb l’insieme di soluzioni del sistema (b). La cardinalita diSb non e finita. Infatti si verifica facilmente che (15, 0,−n, n) e soluzione per ognin ∈ N. Poiche la cardinalita di Z × Z × Z × Z coincide con quella di N, si ha|Sb| = |N|.Il sistema (a) equivale al seguente

x1 + x2 + x3 + x4 = 15x1 ≥ 3x2 ≥ 1x3 ≥ 0x4 ≥ 3

.

Posto z1 = x1 − 3, z2 = x2 − 1, z3 = x3 e z4 = x4 − 3, esso diventa

z1 + z2 + z3 + z4 = 8z1 ≥ 0z2 ≥ 0z3 ≥ 0z4 ≥ 0

.

Se Sa denota l’insieme delle soluzioni del sistema (a), si ha |Sa| =(113

)= 11!

3!·8! .


(a)

x1 + x2 + x3 + x4 = 14x1 ≥ 0x2 ≥ 0x3 ≥ 0

, (b)

x1 + x2 + x3 + x4 = 14x1 > 2x2 ≥ 0x3 > 4x4 ≥ 1

.

SVOLGIMENTO. Sia Sa l’insieme di soluzioni del sistema (a). La cardinalita diSa non e finita. Infatti si verifica facilmente che (14, 0, n,−n) e soluzione per ognin ∈ N. Poiche la cardinalita di Z × Z × Z × Z coincide con quella di N, si ha|Sa| = |N|.Il sistema (b) equivale al seguente

x1 + x2 + x3 + x4 = 14x1 ≥ 3x2 ≥ 0x3 ≥ 5x4 ≥ 1

.

Posto z1 = x1 − 3, z2 = x2, z3 = x3 − 5 e z4 = x4 − 1, esso diventa


z1 + z2 + z3 + z4 = 5z1 ≥ 0z2 ≥ 0z3 ≥ 0z4 ≥ 0

.

Se Sb denota l’insieme delle soluzioni del sistema (b), si ha |Sb| =(5+4−1

3

)= 8!

3!·5! .


(a)

x1 + x2 + x3 + x4 = 14x1 > 0x2 > 0x3 > 0

, (b)

x1 + x2 + x3 + x4 = 14x1 > 2x2 > 0x3 ≥ 4x4 > 1

.


(a)

x1 + x2 + x3 + x4 + x5 = 17x1 > −2x2 ≥ 1x3 > 0x4 > 2x5 ≥ 2


x1 + x2 + x3 + x4 + x5 = 30−2 < x1 ≤ 31 ≤ x2 ≤ 40 < x3 < 4x4 > 2x5 ≥ 2

TRACCIA DELLO SVOLGIMENTO. Si considerino i seguenti sistemi:

(a)

x1 + x2 + x3 + x4 + x5 = 30x1 > −2x2 ≥ 1x3 > 0x4 > 2x5 ≥ 2

(b)

x1 + x2 + x3 + x4 + x5 = 30x1 ≥ 4x2 ≥ 1x3 > 0x4 > 2x5 ≥ 2


(c)

x1 + x2 + x3 + x4 + x5 = 30x1 > −2x2 ≥ 5x3 > 0x4 > 2x5 ≥ 2

(d)

x1 + x2 + x3 + x4 + x5 = 30x1 > −2x2 ≥ 1x3 ≥ 4x4 > 2x5 ≥ 2

(e)

x1 + x2 + x3 + x4 + x5 = 30x1 ≥ 4x2 ≥ 5x3 > 0x4 > 2x5 ≥ 2

(f)

x1 + x2 + x3 + x4 + x5 = 30x1 ≥ 4x2 ≥ 1x3 ≥ 4x4 > 2x5 ≥ 2

(g)

x1 + x2 + x3 + x4 + x5 = 30x1 > −2x2 ≥ 5x3 ≥ 4x4 > 2x5 ≥ 2

(h)

x1 + x2 + x3 + x4 + x5 = 30x1 ≥ 4x2 ≥ 5x3 ≥ 4x4 > 2x5 ≥ 2

Per ogni i ∈ {a, b, c, d, e, f, g, h} si indichi con |(i)| il numero delle soluzioni interedel sistema (i). Per il principio di inclusione esclusione, il numero di soluzioni interedel sistema assegnato e dato da

|(a)| − |(b)| − |(c)| − |(d)|+ |(e)|+ |(f)|+ |(g)| − |(h)|.

Il numero di soluzioni intere di ogni sistema (i) si puo determinare come negli eserciziprecedenti.


x1 + x2 + x3 = 12−1 ≤ x1 ≤ 2x2 ≥ 00 ≤ x3 ≤ 2

SVOLGIMENTO. Si considerino i seguenti sistemi:

(a)

x1 + x2 + x3 = 12x1 ≥ −1x2 ≥ 0x3 ≥ 0

, (b)

x1 + x2 + x3 = 12x1 ≥ 3x2 ≥ 0x3 ≥ 0

,


(c)

x1 + x2 + x3 = 12x1 ≥ −1x2 ≥ 0x3 ≥ 3

, (d)

x1 + x2 + x3 = 12x1 ≥ 3x2 ≥ 0x3 ≥ 3

,

Per il principio di inclusione esclusione, il numero di soluzioni intere del sistemaassegnato e dato dal numero di soluzioni del sistema (a) meno il numero di soluzionidel sistema (b), meno il numero di soluzioni del sistema (c), piu il numero di soluzionidel sistema (d).

Il sistema (a) e equivalente al seguente

x1 + x2 + x3 = 12x1 + 1 ≥ 0x2 ≥ 0x3 ≥ 0

.

Posto z1 = x1 + 1, z2 = x2 e z3 = x3, esso diventa

z1 + z2 + z3 = 13z1 ≥ 0z2 ≥ 0z3 ≥ 0

.

Se con N (a) denotiamo l’insieme delle sue soluzioni intere, si ha |N (a)| = (13+3−1

2

).

Il sistema (b) e equivalente al seguente

x1 + x2 + x3 = 12x1 − 3 ≥ 0x2 ≥ 0x3 ≥ 0

.

Posto z1 = x1 − 3, z2 = x2 e z3 = x3, esso diventa

z1 + z2 + z3 = 9z1 ≥ 0z2 ≥ 0z3 ≥ 0

.

Se con N (b) denotiamo l’insieme delle sue soluzioni intere, si ha |N (b)| = (9+3−1

2

).

Il sistema (c) e equivalente al seguente

x1 + x2 + x3 = 12x1 + 1 ≥ 0x2 ≥ 0x3 − 3 ≥ 0

.


Posto z1 = x1 + 1, z2 = x2 e z3 = x3 − 3, esso diventa

z1 + z2 + z3 = 10z1 ≥ 0z2 ≥ 0z3 ≥ 0

.

Se con N (c) denotiamo l’insieme delle sue soluzioni intere, si ha |N (c)| = (10+3−1

2

).

Il sistema (d) e equivalente al seguente

x1 + x2 + x3 = 12x1 − 3 ≥ 0x2 ≥ 0x3 − 3 ≥ 0

.

Posto z1 = x1 − 3, z2 = x2 e z3 = x3 − 3, esso diventa

z1 + z2 + z3 = 6z1 ≥ 0z2 ≥ 0z3 ≥ 0

.

Se con N (d) denotiamo l’insieme delle sue soluzioni intere, si ha |N (d)| = (6+3−1

2

).

In conclusione il numero di soluzioni intere del sistema assegnato e dato da N (a)−N (b)−N (c) +N (d).


x1 + x2 + x3 = 12−1 < x1 < 2x2 > 00 < x3 < 2

41. Si deve eleggere il presidente di un consiglio di amministrazione di un’azienda. Icandidati sono tre (A, B e C) ed i votanti 20. Quante sono le possibili distribuzionidei voti tali che il candidato A abbia la maggioranza assoluta (cioe maggiore del50%) dei voti?

42. Siano date due liste di candidati: lista A (composta da 10 membri) e lista B (com-posta da 6 membri). Quante diverse composizioni puo avere un organo elettivo di 5membri, sotto la condizione che almeno 3 provengano dalla lista A e al piu 2 dallaB?



x1 + x2 + x3 = 12−1 ≤ x1 < 2x2 > 10 < x3 ≤ 2


x1 + x2 + x3 = 12−1 ≤ x1 < 20 < x3 ≤ 2


x1 + x2 + x3 + x4 = 12−1 ≤ x1 < 20 < x3 ≤ 2

46. Si vogliono riempire quattro differenti recipienti Ri, i = 1, 2, 3, 4, con quattro dif-ferenti liquidi Li. Si tenga inoltre presente che in ogni recipiente si puo versare unsolo liquido e che il recipiente Ri non puo contenere il liquido Li. Determinare inquanti modi distinti sia possibile riempire i recipienti dati rispettando le condizioniimposte.

SVOLGIMENTO. Questo esercizio si risolve ricorrendo al principio di inclusioneesclusione (esso e del tutto equivalente al ben noto problema degli accoppiamentiproibiti). Sia S il numero di tutti i possibili accoppiamenti fra L1, L2, L3, L4 eR1, R2, R3, R4. E evidente che S = 4!. Sia ora Si il numero di tutti gli accoppiamentiliquido-recipiente in cui accade che il liquido Li viene versato nel recipiente Ri. Siha, per ogni i, Si = (4 − 1)! = 3!. Per ogni i, j ∈ {1, 2, 3, 4}, con i 6= j, indichiamocon Sij il numero degli accoppiamenti in cui accade sia il liquido Li viene versatonel recipiente Ri che quello Lj viene versato in Rj. Si ha Sij = (4 − 2)! = 2!. Perogni i, j, t ∈ {1, 2, 3, 4}, con i, j e t a due a due distinti fra loro, indichiamo conSijt il numero degli accoppiamenti in cui accade che i liquidi Li, Lj e Lt vengonorispettivamente versati nei recipiente Ri, Rj e Rt. Si ha Sijt = (4−3)! = 1. Sia infineS1234 il numero degli accoppiamenti in cui il liquido Li viene versato nel recipienteRi. Ovviamente S1234 = 1.

Denotiamo con ρ il valore cercato. Per il principio di inclusione esclusione, si ha

ρ = S −4∑

i=1

Si +∑ij

Sij −∑ijt

Sijt + S1234


dove∑

ij (∑

ijt) indica la somma degli Sij estesa a tutti i sottoinsiemi distin-ti {i, j} ⊂ {1, 2, 3, 4} (degli Sijt estesa a tutti i sottoinsiemi distinti {i, j, t} ⊂{1, 2, 3, 4}). Quindi

ρ = 4!−(4

1

)· 3! +

(4

2

)· 2!−

(4

3

)· 1 + 1 = 9.

2 Induzione

1. Usando il principio di induzione, si dimostri che per ogni n ∈ N valgono le seguentiuguaglianze:

• 1 + 2 + 3 + . . .+ n = n(n+1)2

;

• 12 + 22 + 32 + . . .+ n2 = n(n+1)(2n+1)6

;

• 13 + 23 + 33 + . . .+ n3 = (n(n+1)2

)2;

• 1 + 3 + 5 + . . .+ (2n− 1) = n2;

• 11·2 +

12·3 + . . .+ 1

n·(n+1)= n

n+1.

2. Provare che per ogni n ∈ N si ha 2n > n2 − n.

SVOLGIMENTO. Per induzione. 20 > 0. Supposta vera la disuguaglianza 2n >n2−n, proviamo che vale 2n+1 > (n+1)2− (n+1). Si ha 2n+1 = 2 · 2n > 2(n2−n).Per n ≥ 3 si ha 2n2 − 2n ≥ (n + 1)2 − (n + 1). Inoltre si verifica facilmente che22 > 22 − 2 e 23 > 32 − 3.

3. Provare che per ogni x ∈ R, x ≥ 0, e per ogni n ∈ N vale la disuguaglianza(1 + x)n ≥ 1 + nx.

4. Provare che per ogni x ∈ R, x 6= 1, e per ogni n ∈ N si ha 1−xn+1

1−x= 1+x+x2+. . .+xn.

5. Provare che n3 − n e divisibile per 3 per ogni n ∈ N.6. Provare che 5n − 1 e divisibile per 4 per ogni n ∈ N.7. Verificare che per ogni n ∈ N vale la disuguaglianza 4n ≥ n2

n+1.

SVOLGIMENTO. Dimostriamo la disuguaglianza per induzione. Sicuramente essavale per n = 0, 1. Bisogna quindi dimostrare che se essa e vera per n = m alloralo e anche per n = m + 1. Avendo supposto per ipotesi che 4m ≥ m2

m+1, si ha

4m+1 ≥ 4 m2

m+1. Si verifica facilmente che 4 m2

m+1≥ m2+2m+1

m+2. Da cui la tesi.

8. Provare che la seguente disequazione

log2(n+ 1) ≤ n2


vale per ogni n ∈ N.SVOLGIMENTO. Si proceda per induzione. Sia P (n) la proposizione log2(n+1) ≤n2. P (0) diventa log2 1 ≤ 0, la quale e vera essendo log2 1 = 0.

Supposta vera P (n) proviamo che P (n+ 1) e vera.

Dobbiamo quindi provare che log2((n + 1) + 1) ≤ (n + 1)2 o la disuguaglianzaequivalente 2(n+1)2 ≥ n + 2. Si ha 2(n+1)2 = 2n

2+2n+1 = 2n222n+1. Poiche P (n) e

vera, 2n2 ≥ n+ 1, quindi 2(n+1)2 = 2n

222n+1 ≥ (n+ 1)22n+1 ≥ (n+ 1)2 ≥ n+ 2.

9. Verificare che per ogni n ∈ N vale la disuguaglianza 3n ≥ n2+1n+2

.

10. Verificare che per ogni n ∈ N vale la disuguaglianza 2n ≥ √n2 + 1.

11. Determinare il piu piccolo n0 ∈ N tale che 3n > 4n2+n+2 per ogni n ≥ n0, n ∈ N.

TRACCIA DELLO SVOLGIMENTO: Si verifica facilmente che per n = 0, 1, 2, 3,si ha 3n < 4n2 + n+ 2. Invece, per n = 4, otteniamo 34 = 81 > 4 · 42 + 4 + 2 = 70.Pertanto e possibile supporre che possa essere n0 = 4. Dimostriamo per induzioneche, per ogni n ≥ 4, 3n > 4n2+n+2. A tale scopo basta provare che supposta verala disuguaglianza per n = m ≥ 4, essa vale anche per n = m+ 1. Sia allora

3m > 4m2 +m+ 2.

Moltiplicando entrambi i membri per 3 otteniamo

3m+1 > 12m2 + 3m+ 6.

Per completare la dimostrazione e sufficiente verificare che, per ogni m ≥ 4, vale ladisuguaglianza

12m2 + 3m+ 6 ≥ 4(m+ 1)2 + (m+ 1) + 2.

Si lascia allo studente la verifica di quest’ultima disuguaglianza.

12. Determinare il piu piccolo n0 ∈ N tale che n! > 2n+1 per ogni n ≥ n0, n ∈ N.

SVOLGIMENTO. Si verifica facilmente che per n = 0, 1, 2, 3, 4, si ha n! < 2n+1.Invece, per n = 5, otteniamo 5! = 120 > 25+1 = 64. Pertanto e possibile supporreche possa essere n0 = 5. Dimostriamo per induzione che, per ogni n ≥ 5, n! > 2n+1.A tale scopo basta provare che supposta vera la disuguaglianza per n = m ≥ 5, essavale anche per n = m+ 1. Sia allora

m! > 2m+1.

Moltiplicando entrambi i membri per m+ 1 otteniamo

m!(m+ 1) > 2m+1(m+ 1).

Poiche, per ogni m ≥ 5, 2m+1(m+1) > 2m+1 · 2, otteniamo (m+1)! = m!(m+ 1) >2m+1(m+ 1) > 2m+1 · 2 > 2m+2.


13. Provare che per ogni n ∈ N si ha n3 − n ≡ 0 (mod 6).

14. Dimostrare, utilizzando il principio di induzione, che

32n − 2 · 3n ≡ 3 (mod 4), ∀n ∈ N.


n∑i=1

(3i− 2) =n(3n− 1)

2, ∀n ≥ 1.


23 +n∑

i=3

2i = 2n+1, ∀n ≥ 3.


42n − 3 · 4n ≡ 4 (mod 3), ∀n ∈ N.

18. Sia an, la successione di numeri reali cosı definita:

a0 = 1, an+1 =√3an, n ∈ N.

Provare che

(a) 0 < an < 3 per ogni n ∈ N.(b) an < an+1 per ogni n ∈ N.

SVOLGIMENTO.

• La (a) si prova per induzione. Evidentemente 0 < a0 = 1 < 3. Supposto veroche 0 < an < 3 provo che 0 < an+1 < 3. Infatti 0 < an+1 =

√3an < 3 e vera se

e solo se e vera 0 < 3an < 9. Quest’ultima catena di disuguaglianze e vera perl’ipotesi induttiva.

• Proviamo la (b). Si ha che an < an+1 se e solo se an <√3an. Elevando al

quadrato (operazione lecita in quanto abbiamo gia provato che an > 0 per ognin) l’ultima disuguaglianza risulta equivalente a a2n < 3an la quale e vera se esolo se an < 3. Quest’ultima disuguaglianza e stata provata vera nel puntoprecedente.

19. Sia an, la successione di numeri reali cosı definita:

a0 = 1, an+1 =√5an, n ∈ N.

Provare che


(a) 0 < an < 5 per ogni n ∈ N.SVOLGIMENTO. L’asserto si prova per induzione. Evidentemente 0 < a0 =1 < 5. Supposto vero che 0 < an < 5 provo che 0 < an+1 < 5. Infatti0 < an+1 =

√5an < 5 e vera se e solo se e vera 0 < 5an < 25. Quest’ultima

catena di disuguaglianze e vera per l’ipotesi induttiva.

(b) an < an+1 per ogni n ∈ N.SVOLGIMENTO. Si ha che an < an+1 se e solo se an <

√5an. Elevando al

quadrato (operazione lecita in quanto abbiamo gia provato che an > 0 per ognin) l’ultima disuguaglianza risulta equivalente a a2n < 5an la quale e vera se esolo se an < 5. Quest’ultima disuguaglianza e stata provata vera nel puntoprecedente.

20. Sia an la successione (di Fibonacci) cosı definita

a0 = 0, a1 = 1, an+1 = an + an−1.

Provare che comunque fissato k ∈ N esiste un n0 ∈ N tale che an > k per ognin > n0.

21. Siano date n ≥ 2 rette nel piano tali che due rette qualsiasi si intersecano in unpunto ma tre qualsiasi non hanno un punto in comune. Sia p(n) il numero di partiin cui viene suddiviso il piano. Dimostrare che:

• p(n+ 1) = n+ 1 + p(n);

• p(n) = n2+n+22

.

3 Teoria dei numeri

1. Calcolare i M.C.D. fra le seguenti coppie di numeri e scrivere la relativa identita diBezout: (421, 90), (572, 364), (5992, 322), (5982, 621), (7341, 522).

2. Dire, giustificando le risposte, se le seguenti equazioni hanno soluzioni:(a) 2x ≡ 3 (mod 6); (b) 2x ≡ 4 (mod 6); (c) 2x ≡ 3 (mod 5).

L’equazione ax ≡ b (mod n) ha soluzioni se e solo se (a, n) | b. Quindi (a) non hasoluzioni mentre (b) e (c) hanno soluzioni.

3. Dire, giustificando le risposte, se le seguenti equazioni hanno soluzioni:(a) 2x ≡ 4 (mod 8); (b) 2x ≡ 5 (mod 8); (c) 2x ≡ 3 (mod 7).

SVOLGIMENTO. L’equazione ax ≡ b (mod n) ha soluzioni se e solo se (a, n) | b.Quindi (b) non ha soluzioni mentre (a) e (c) hanno soluzioni.


4. Dire se ha soluzioni ed eventualmente risolvere la seguente equazione

2x ≡ 5 (mod 6).

SVOLGIMENTO. L’equazione ax ≡ b (mod n) ha soluzioni se e solo se (a, n) | b.Poiche (2, 6) = 2, l’equazione data non ha soluzioni.

5. Dire se ha soluzioni ed eventualmente risolvere l’equazione 18x ≡ 12 (mod 30).

SVOLGIMENTO. Si ha (18, 30) = 6. Poiche 6 | 12, l’equazione ha soluzioni. De-terminiamo tali soluzioni. L’equazione data equivale alla seguente 18x− 30k = 12.L’identita di Bezout per 6 = (18, 30) e 6 = 2·18+(−1)·30. Quindi 12 = 4·18−2·30.Quindi una soluzione e x′ = 4. Tutte le soluzioni sono date da x = 4 + ρ30

6, cioe

x ≡ 4 (mod 5).


SVOLGIMENTO. Si ha (6, 5) = 1. Quindi l’equazione ha soluzioni. Essa equivalealla 6x − 5k = 9. L’identita di Bezout per 1 = (6, 5) e 1 = 6 · 1 + (−1) · 5. Quindi9 = 6 · 9 − 5 · 9. Quindi una soluzione e x′ = 9. Tutte le soluzioni sono date dax = 9 + 5ρ, cioe x ≡ 9 (mod 5).


8. Risolvere le seguenti equazioni:2x ≡ 7 (mod 6), 12x ≡ 16 (mod 14), 9x ≡ 4 (mod 7).

9. Dire, giustificando la risposta, se i seguenti sistemi hanno soluzioni:

(a)

x ≡ 4 (mod 5)x ≡ 3 (mod 4)x ≡ 9 (mod 21)

, (b)

2x ≡ 4 (mod 6)2x ≡ 3 (mod 5)2x ≡ 7 (mod 4)

.

SVOLGIMENTO. Il sistema (a) verifica le ipotesi del teorema cinese del resto, quin-di ha soluzioni. Mentre il sistema (b) non ha soluzioni in quanto la terza equazionenon ha soluzioni

10. Dire, giustificando la risposta, se i seguenti sistemi hanno soluzioni:

(a)

3x ≡ 9 (mod 18)3x ≡ 3 (mod 4)3x ≡ 8 (mod 6)

, (b)

x ≡ 4 (mod 7)x ≡ 3 (mod 5)x ≡ 7 (mod 4)

.

SVOLGIMENTO. Il sistema (b) verifica le ipotesi del teorema cinese del resto, quindiha soluzioni. Mentre il sistema (a) non ha soluzioni in quanto la terza equazionenon ha soluzioni.


11. Trovare le soluzioni intere del seguente sistema di congruenze

x ≡ 3 (mod 7)x ≡ 4 (mod 6)x ≡ 2 (mod 5)

.

SVOLGIMENTO. Poiche i moduli sono a due a due coprimi, il sistema puo risolversio uguagliando a due a due le congruenze oppure mediante il teorema cinese del resto.

Primo metodo. Si risolva il sistema{

x ≡ 3 (mod 7)x ≡ 4 (mod 6)

.

Si ha 3 + 7k = 4 + 6h e quindi 1 = 7k − 6h. Da cui k = h = 1. Le soluzioni sonocosı x ≡ 10 (mod 42). Si risolva ora il sistema

{x ≡ 10 (mod 42)x ≡ 4 (mod 6)

.

Si ha 10+42ρ = 4+6µ. Da cui 8 = 5µ+42(−ρ). Essendo 1 = (42, 5), per l’identitadi Bezout si ha 1 = 42(−2) + 5 · 9 e quindi 8 = 42(−2)8 + 5 · 9 · 8. Da cui µ = 72 euna soluzione particolare e 682. Tutte le soluzioni del sistema assegnato sono quindix ≡ 52 (mod 210).

Secondo metodo (teorema cinese del resto). Le tre congruenze di cui si cerca unasoluzione particolare sono

30y1 ≡ 1 (mod 7), 35y2 ≡ 1 (mod 6), e 42y3 ≡ 1 (mod 5).

Per l’identita di Bezout si ha

• 1 = (7, 5 · 6) = 7 · 13 + 30(−3), quindi y1 = −3;

• 1 = (6, 7 · 5) = 6 · 6 + 35(−1), quindi y2 = −1;

• 1 = (5, 7 · 6) = 5 · 17 + 42(−2), quindi y3 = −2.

Una soluzione particolare e cosı x = 3 · 30 · (−3)+4 · 35 · (−1)+2 · 42 · (−2) = −578.Tutte le soluzioni sono x ≡ 52 (mod 210).

12. Risolvere i sistemi

(a)

x ≡ 4 (mod 9)x ≡ 3 (mod 4)x ≡ 2 (mod 5)

e (b)

x ≡ 4 (mod 5)x ≡ 3 (mod 4)x ≡ 2 (mod 9)

.


SVOLGIMENTO. Poiche i moduli sono a due a due coprimi, entrambi i sistemipossono risolversi o uguagliando a due a due le congruenze oppure mediante ilteorema cinese del resto.

Primo metodo (uguagliare a due a due le congruenze). Il sistema (a) equivale alseguente

x = 4 + 9kx = 3 + 4mx = 2 + 5n

.

Risolviamo il sistema

(1)

{x = 4 + 9kx = 3 + 4m

.

Si ha 4 + 9k = 3 + 4m, 1 = 4m − 9k, m = −2 e k = −1. Una soluzione di (1) equindi x = −5. Tutte le soluzioni di (1) sono −5 + 36t.


(2)

{x = −5 + 36tx = 2 + 5n

.

Si ha −5+36t = 2+5n da cui 7 = 36t−5n. Poiche 1 = 36−7·5 si ha 7 = 36·7−49·5.Quindi t = 7 e quindi una soluzione di (2) e x′ = −5+36 ·7 = 247. Tutte le soluzionidel sistema (a) sono cosı x = 247 + 180ρ, cioe x ≡ 67 (mod 180).

Risolviamo ora il sistema (b) sempre uguagliando a due a due le congruenze. Essoequivale al seguente

x = 4 + 5kx = 3 + 4mx = 2 + 9n

.


(1)

{x = 4 + 5kx = 3 + 4m

Si ha 4 + 5k = 3 + 4m, 1 = 4m + 5(−k). Essendo (5, 4) = 1, l’identita di Bezout e1 = 5 · 1 + 4 · (−1) e quindi k = −1, m = −1. Una soluzione particolare di (1) ex = −1. Percio tutte le soluzioni di (1) sono x = −1 + 20t.


(2)

{x = −1 + 20kx = 2 + 9n

Si ha −1+ 20t = 2+ 9n, 3 = 20t+9(−n). Essendo (20, 9) = 1, ricaviamo l’identitadi Bezout tramite il metodo delle divisioni successive:

20 = 9 · 2 + 2,

9 = 2 · 4 + 1.


Quindi 1 = 9− 2 · 4 = 9− (20− 9 · 2) · 4, e l’dentita di Bezout e

1 = 9 · 9 + 20 · (−4).

Ne segue3 = 9 · 27 + 20 · (−12),

e quindi t = −12, n = −27. In conclusione una soluzione particolare di (2) ex = −1+20 · (−12) = −241 e tutte le soluzioni di (2), e quindi del sistema (b), sonox = −241 + 180ρ o, equivalentemente, x ≡ 119 (mod 180).

Secondo metodo (teorema cinese del resto). Risolviamo (a). Le tre congruenzedi cui si cerca una soluzione particolare sono

20y1 ≡ 1 (mod 9), 45y2 ≡ 1 (mod 4), e 36y3 ≡ 1 (mod 5).

Si scrivono le identita di Bezout per 1 = (9, 20), 1 = (4, 45), 1 = (5, 36). Esse sonorispettivamente 1 = 20 · (−4) + 9 · 9, 1 = 45 · 1+ 4 · (−11) e 1 = 36 · 1+ 5 · (−7). Leultime due sono immediate, per ricavare la prima usiamo il metodo delle divisionisuccessive: 20 = 9 · 2+2, 9 = 2 · 4+1, 2 = 2 · 1+0. Quindi 1 = 9− 2 · 4 = 9− (20−9 · 2) · 4 = (−4) · 20+ 9 · 9. Abbiamo quindi y1 = −4, y2 = 1, y3 = 1 e una soluzioneparticolare del sistema assegnato e data da x = 4·20·(−4)+3·45·1+2·36·1 = −113.Tutte le soluzioni sono quindi x = −113 + 9 · 4 · 5 · k, per ogni k ∈ Z. Cioe x ≡ 67(mod 180).

Risolviamo (b) mediante il teorema cinese del resto. Si osservi che (a parte l’ordine)i moduli di (b) coincidono con quelli di (a). Pertanto, riscrivendo il sistema nelmodo seguente,

(b)

x ≡ 2 (mod 9)x ≡ 3 (mod 4)x ≡ 4 (mod 5)

,

le congruenze di cui bisogna cercare le soluzioni particolare coincidono con quelle di(a):

20y1 ≡ 1 (mod 9), 45y2 ≡ 1 (mod 4), e 36y3 ≡ 1 (mod 5).

Abbiamo quindi y1 = −4, y2 = 1, y3 = 1 e una soluzione particolare del sistemaassegnato e data da x = 2 · 20 · (−4) + 3 · 45 · 1 + 4 · 36 · 1 = 119. Tutte le soluzionisono quindi x = 119 + 180ρ, per ogni ρ ∈ Z. Cioe x ≡ 119 (mod 180).

13. Trovare le soluzioni intere del seguente sistema di congruenze{

x ≡ 1 (mod 3)2x ≡ 6 (mod 4)

SVOLGIMENTO. Il sistema assegnato equivale al seguente{

x ≡ 1 (mod 3)x ≡ 3 (mod 2)


Sia α una soluzione particolare di quest’ultimo sistema. Tutte le sue soluzioni sonox = α + [3, 2]ρ per ogni ρ ∈ Z, ([3, 2] denota il minimo comune multiplo fra 3 e2, cioe 6). Quindi e sufficiente determinare α. L’intero α e soluzione se e solo seesistono h, k ∈ Z tali che {

α− 1 = 3kα− 3 = 2h

Da cui si ha 2 = 3k − 2h. Si vede facilmente che k = h = 2. Quindi α = 7.

14. Trovare le soluzioni intere del seguente sistema di congruenze{

2x ≡ 4 (mod 6)3x ≡ 5 (mod 4)

SVOLGIMENTO. Il sistema assegnato equvale al seguente{

3x ≡ 6 (mod 9)3x ≡ 5 (mod 4)

.

Posto y = 3x, risolviamo il sistema{

y = 6 + 9hy = 5 + 4k

.

Si ha 6 + 9h = 5 + 4k, 1 = 4k + 9(−h). Essendo 1 = 9 + 4 · (−2), si ha k = −2,h = −1. Poiche soluzione particolare dell’ultimo sistema e y = 6+9h = −3, tutte lesoluzioni sono y = −3+36ρ al variare di ρ ∈ Z. Da cui 3x = −3+36ρ. Quindi tuttele soluzioni del sistema assegnato sono x = −1 + 12ρ o, equivalentemente, x ≡ 11(mod 12).

15. Risolvere i seguenti sistemi di congruenze:

{x ≡ 3 (mod 4)x ≡ 5 (mod 6)

,

{x ≡ 2 (mod 4)x ≡ 5 (mod 6)

,

{x ≡ 3 (mod 4)2x ≡ 5 (mod 6)

,

{5x ≡ 6 (mod 7)2x ≡ 5 (mod 3)

,

x ≡ 3 (mod 5)x ≡ 5 (mod 6)x ≡ 4 (mod 7)

,

x ≡ 3 (mod 4)2x ≡ 4 (mod 5)x ≡ 2 (mod 3)

,

5x ≡ 6 (mod 8)2x ≡ 5 (mod 6)x ≡ 4 (mod 9)

,

x ≡ 0 (mod 3)x ≡ 0 (mod 6)x ≡ 0 (mod 5)

,

x ≡ 4 (mod 5)x ≡ 3 (mod 4)x ≡ 2 (mod 9)

.

16. I seguenti quattro esercizi sono stati presi dal libro: Algebra di Lindsay Childs, ETSeditrice (1989).


(a) Ecco un antico problema cinese. Tre contadini coltivavano insieme il riso, eal tempo del raccolto lo dividevano in parti uguali. Un anno ciascuno andoad un mercato differente per vendere la sua quota di riso. In ciascuno dei tremercati si trattava il riso in multipli di un certo peso base, che era differentein ciascuno dei tre. Il primo contadino vendette il suo riso ad un mercato incui il peso base era di 87 libbre. Vendette tutto quello che pote, e ritorno con18 libbre di riso. Il secondo contadino vendette il suo riso ad un mercato incui il peso base era di 170 libbre. Vendette tutto quello che pote, e ritornocon 58 libbre di riso. Il terzo contadino vendette il suo riso ad un mercato incui il peso base era di 143 libbre. Vendette tutto quello che pote, e ritornocontemporaneamente agli altri due con 40 libbre di riso. Quanto riso avevanoraccolto in totale?

(b) E dato un cesto di uova. Si sa che se si levano le uova 2 alla volta, resta unuovo, se si levano 3 alla volta restano 2 uova, se si levano 4 alla volta restano3 uova, se si levano 5 alla volta restano 4 uova, se si levano 7 alla volta non nerestano. Quante uova c’erano nel cesto?

(c) Due problemi di Gauss:

i. Trovare un numero che sia congruo a 17 (mod 9), a −4 (mod 5), a −4(mod 7) ed a 33 (mod 16).

ii. L’indizione, numero d’oro e ciclo solare degli anni si ripetono ogni 15, 19 e28 anni, rispettivamente. Ogni quanto tempo si ripetono anni con la stessaindizione, numero d’oro e ciclo solare?

(d) Un problema di Yih-hing, 717 D.C. Risolvere

x ≡ 1 (mod 2)x ≡ 2 (mod 5)x ≡ 5 (mod 6)x ≡ 5 (mod 12)

.

17. Trovare le soluzioni intere del seguente sistema di congruenze:

x ≡ 3 (mod 7)x ≡ 2 (mod 5)x ≡ 3 (mod 4)


Esercizi di Matematica Discreta - Parte II · · 2015-10-18Esercizi di Matematica Discreta -...

Documents

Transcript of Esercizi di Matematica Discreta - Parte II · · 2015-10-18Esercizi di Matematica Discreta -...