Compito di Matematica Discreta e Algebra Lineare 31 ottobre 2018

(1)

Compito di Matematica Discreta e Algebra Lineare 31 ottobre 2018

Soluzioni MD

Esercizio 1. (1) Dire per quali valori del parametro intero a la congruenza ax ≡ 6 (mod 8)

`

e risolubile.

(2) Determinare le soluzioni del sistema

( 3x ≡ 6 (mod 8) 5

^x

≡ 4 (mod 11)

Soluzione: (1) L’equazione ` e risolubile se e solo se (a, 8)|6. Dato che le possibilit` a per (a, 8) sono i divisori di 8, e cio` e 1,2,4,8, vanno bene i casi in cui (a, 8) = 1, 2, mentre vanno esclusi i casi in cui (a, 8) = 4, 8. I casi da escludere sono dunque tutti e soli quelli in cui a ` e multiplo di 4, quindi la risposta alla domanda del problema ` e a 6≡ 0 (mod 4).

(2) La prima equazione del sistema si riduce a x ≡ 2 (mod 8).

Per quanto riguarda la seconda equazione, consideriamo il periodo delle potenze di 5 modulo 11. Abbiamo

5

¹

≡ 5, 5

²

≡ 3, 5

³

≡ 4, 5

³

≡ 9, 5

⁵

≡ 1 (mod 11) , Ne segue che il periodo ` e 5 e che la soluzione ` e x ≡ 3 (mod 5).

Poich´ e (8, 5) = 1, il teorema cinese del resto assicura che c’` e un’unica soluzione modulo 8·5 = 40, e con semplici calcoli si trova che questa soluzione ` e x ≡ 18 (mod 40).

Esercizio 2. a) Quante sono le funzioni da {1, ...., 30} a {1, ..., 30} che assumono almeno un valore maggiore di 11?

b) Quante sono quelle che assumono esattamente un valore maggiore di 11?

c) Quanti sono i sottoinsiemi di {1, ...., 30} che contengono esattamente tre numeri pari?

Soluzione: a) Il numero di tutte le funzioni da {1, ...., 30} a {1, ..., 30} ` e 30

³⁰

. Da queste bisogna escludere le funzioni che non assumono nessun valore maggiore di 11, cio` e le funzioni da {1, ...., 30} a {1, ..., 11}, che sono 11

³⁰

. Il risultato ` e dunque 30

³⁰

− 11

³⁰

.

b) Sia a ∈ {12, . . . , 30} il valore della funzione maggiore di 11. Allora a pu` o essere scelto in 19 modi. Per ogni valore di a, le funzioni da contare sono quelle a valori in {1, . . . , 11} ∪ {a} meno quelle a valori in {1, . . . , 11}, quindi sono 12

³⁰

− 11

³⁰

.

La risposta ` e dunque 19 · (12

³⁰

− 11

³⁰

).

c) I sottoinsiemi cercati sono l’unione di:

- un qualsiasi sottoinsieme di 3 elementi dei 15 numeri pari compresi fra 1 e 30, per un totale di

¹⁵₃

possibilit`a;

- un qualsiasi sottoinsieme dei 15 numeri dispari compresi fra 1 e 30, per un totale di 2

¹⁵

possibilit` a.

La risposta ` e dunque

¹⁵₃

· 2

¹⁵