615 35

(1)

Esercizi di Matematica Discreta 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 caselle 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) Se mcd(a,b)=1, 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.

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

¹

+2

²

+…+2

ⁿ

=2

ⁿ⁺¹

-2”.

P(1) è vero perché 2

¹

=2

¹⁺¹

-2. Supponendo vero P(k), dimostriamo vero P(k+1):

P(k+1)=” 2

¹

+2

²

+…+2

^k+1

=2

^k+2

-2 “ (da dimostrare vero).

Ma si calcola che 2

¹

+2

²

+…+2

^k+1

=(2

¹

+2

²

+…+2

^k

)+2

^k+1

=(2

^k+1

-2)+2

^k+1

=22

^k+1

-2=2

^k+2

-2 (dove si è sfruttato che, per ipotesi, è vero P(k)=” 2

¹

+2

²

+…+2

^k

=2

^k+1

-2”).

4) Si può utilizzare il principio di inclusione-esclusione in forma positiva. 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:

X

1

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

2

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

1

X

2

:

X

1

X

2

=X

1

+X

2

-X

1

X

2



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

X

1

=8

²

=X

2

, X

1

X

2

=8 da cui  X

1

X

2

=8

²

+8

²

-8=120

5) Si può utilizzare il principio di inclusione-esclusione in forma negativa. 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:

X

1

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

X

2

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

e si calcola A-X

1

X

2

. Si ha poi:

X

1

X

2

=X

1

+X

2

-X

1

X

2

=10

⁴

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

(dove i valori numerici si ottengono applicando opportunamente il principio delle scelte multiple).

La risposta è dunque 12

⁴

-(10

⁴

+1211109-10987)=…….

6) 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

(2)

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

⁹

=……….

7) Ognuno dei sottoinsiemi da contare si ottiene dall’unione di {1,2} (termine fissato) con un sottoinsieme dell’insieme {3,4,5,6,7} (termine 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

⁵

.

8) Primo caso: nessun palo è colorato di rosso. In questo caso ognuno dei 7 pali può essere colorato con 4 possibili colori, e le colorazioni sono in numero di 4

⁷

.

Secondo caso: esattamente un palo è colorato di rosso e gli altri 6 con uno dei 4 colori rimanenti. In

questo caso si sceglie la posizione del palo rosso (7 scelte possibili) e, fissata questa, si scelgono i

colori per gli altri 6 pali (4

⁶

scelte possibili), quindi il numero di colorazioni è il prodotto 74

⁶

.

Terzo caso: esattamente due pali sono colorati di rosso e gli altri 5 con uno dei 4 colori rimanenti. In

questo caso si scelgono le posizioni dei 2 pali rossi ((

⁷₂

) scelte possibili) e, fissate queste, si

scelgono i colori per gli altri 5 pali (4

⁵

scelte possibili), quindi il numero di colorazioni è il prodotto

(

₂⁷

)4

⁵

. La risposta è la somma 4

⁷

+74

⁶

+(

₂⁷

)4

⁵