• Non ci sono risultati.

14 Gennaio 2019

N/A
N/A
Protected

Academic year: 2021

Condividi "14 Gennaio 2019"

Copied!
2
0
0

Testo completo

(1)

Matematica Discreta AAAA (6 crediti)

14 Gennaio 2019

1. Si determini il resto della divisione di 7218 per 11.

Soluzione: Possiamo applicare il Teorema di Fermat, perch´e 11 `e primo e 7 non `e divisibile per 11. Quindi, 71011 1. Dividiamo 218 per 10: 218 = 10 × 21 + 8. Allora si ha

7218 = 710×21+8= 710×2178 = (710)217811 12178 = 78 = (72)41154 = (52)211 32 = 9.

2. (a) In quanti modi si possono disporre 10 palline distinguibili in 4 contenitori distinti?

Soluzione: Le palline sono distinguibili. Quindi le possiamo numerare da 1 a 10. I contenitori sono distinti: quindi, li possiamo chiamare con nomi diversi c1, c2, c3, c4. Ogni disposizione delle palline nei contenitori corrisponde ad una funzione dall’insieme {1, 2, . . . , 9, 10} nell’in- sieme {c1, c2, c3, c4} dei quattro contenitori. Si tratta quindi di disposizioni con ripetizione di un insieme di quattro elementi di ordine 10: Dn,k0 = 410.

(b) In quanti modi si possono disporre 10 palline indistinguibili in 4 contenitori distinti?

Soluzione: Le palline sono indistinguibili. Quindi, NON le possiamo numerare. Porre le 10 palline nei contenitori corrispondere a prendere un multinsieme di ordine 10 di un insieme di quattro elementi (combinazioni con ripetizione). Per esempio, il multinsieme [c1, c1, c3, c3, c3, c3, c4, c4, c4, c4] corrisponde a mettere 2 palline nel contenitore c1; 4 palline nel contenitore c3; 4 palline nel contenitore c4, e 0 palline nel contenitore c2.

Considerando che n = 4 e k = 10, in totale abbiamo n+k−1n  = 4+10−110  = 1310 = 133 =

n+k−1

k−1  possibilit`a.

3. Dimostrare per induzione che la somma dei primi n numeri dispari `e n2:

n−1

X

k=0

(2k + 1) = n2.

Soluzione: Un numero x `e dispari se e solo se esiste un numero naturale k tale che y = 2k + 1.

Quindi, per considerare i primi n numeri dispari, bisogna far variare l’indice k nel termine 2k + 1 nell’intervallo [0, n − 1]. Dobbiamo quindi provare che

X

0≤k≤n−1

(2k + 1) = n2.

Caso base: n = 1: Allora 1 = 12. Vero.

1

(2)

Supponiamo per ipotesi d’induzione che la somma dei primi n numeri dispari sia uguale ad n2, cio`e P

0≤k≤n−1(2k + 1) = n2. Allora dimostriamo la stessa relazione per la somma dei primi n + 1 numeri dispari:

X

0≤k≤n

(2k + 1) = X

0≤k≤n−1

(2k + 1) + (2n + 1) =Ip.Ind. n2+ 2n + 1 = (n + 1)2.

4. Si consideri la seguente relazione binaria R sull’insieme degli studenti del corso di laurea in informatica: xRy se e solamente se x e y hanno la stessa et`a e x ha superato un numero di esami strettamente inferiore al numero di esami superati da y.

Quali propriet`a verifica la relazione R?

Soluzione: Indichiamo con e(x) l’et`a dello studente x e con n(x) il numero di esami superati dallo studente x. Allora la relazione R pu`o essere riscritta come segue:

xRy ⇔ e(x) = e(y) ∧ n(x) < n(y).

Prop. Riflessiva ∀x(xRx): Non vale. Controesempio per lo studente g. Se gRg, allora e(g) = e(g), che `e vero, e n(g) < n(g), che `e palesemente falso.

Prop. Simmetrica ∀xy(xRy → yRx): Non vale. Controesempio per gli studenti g e c.

Supponiamo che gRc, cio´e, e(g) = e(c) e n(g) < n(c). Allora cRg NON vale perch´e n(c) <

n(g) `e falsa.

Prop. Transitiva ∀xyz(xRy ∧ yRz → xRz): Vale. Supponiamo che xRy e yRz. Questo significa che e(x) = e(y), n(x) < n(y), e(y) = e(z) e n(y) < n(z). Allora e(x) = e(y) = e(z) e n(x) < n(y) < n(z). Per la propriet`a transitiva dell’uguaglianza e degli ordinamenti parziali, ricaviamo e(x) = e(z) e n(x) < n(z), cio´e xRz.

Prop. Antisimmetrica ∀xy(xRy ∧ yRx → x = y): Vale. Ricordiamo che un’implicazione ´e vera se l’antecedente `e falso. In questo caso l’antecedente xRy ∧yRx `e sempre falso comunque scegliamo x, y tra gli studenti.

Riferimenti

Documenti correlati

- di poter prevenire almeno un terzo delle irregolarità tributarie constatate nell’ultimo quinquennio settore dei prodotti alcolici, per un gettito di circa 11

La delibera di archiviazione del caso T.F./S.G viene approvata all’unanimità dei presenti con 12 voti favorevoli (Parolin, Mazzucchelli, Longo, Bertani, Bozzato,

• Relatore durante la cerimonia di inaugurazione della 55^ Fiera Nazionale dell’Agricoltura 2016, intervento su “Il punto di vista degli infortuni agricoli e le

3.1 Considerato un esperimento che consiste nel lanciare due volte un dado in cui le facce contrassegnate con 1 e 2 punti hanno probabilità doppia rispetto alle altre,

Quando una matrice A viene ridotta per righe, eventua- li relazioni tra le colonne

(a) In quanti modi si possono disporre 8 palline indistinguibili in 16 contenitori distinti in maniera tale che ogni contenitore contenga al pi` u una pallina?. Soluzione: Le

OLMOPONTE ARNO CASTIGLIONI LATERINA sq.b COLONNA INDICATORE COMUNALE GIUNTI CAMPO A - AREZZO.. RAGGRUPPAMENTO PRIMI CALCI I ANNO –

- Il numero dei componenti del Consiglio (determinato in base al numero delle imprese ed unità locali iscritte nel registro delle imprese ovvero annotate nello stesso) per la Camera