Prova scritta di Matematica Discreta - Soluzioni (11 giugno 2012)
Esercizio 1. Se f è una delle funzioni in questione, ognuno dei 3 numeri pari x di A ha come corrispondente f(x) un qualunque elemento di B, dunque 78 possibili corrispondenti; ma ognuno dei 4 numeri dispari x di A ha come corrispondente f(x) un numero con la seconda cifra =x, dunque 77 possibili corrispondenti. Per il principio delle scelte multiple il numero delle funzioni f è (78)3(77)4=752.
Esercizio 2. Gli elementi x da contare hanno nelle prime 4 cifre 3 possibilità: a) due cifre
=1, una cifra =3, una cifra =4; b) due cifre =1, una cifra =2, una cifra =6; c) due cifre =2, una cifra 3, una cifra =1. Nel caso a) si devono scegliere le 2 posizioni della cifra 1 fra le 4 posizioni disponibili (con 246
scelte possibili); fissata tale scelta, si deve scegliere la posizione della cifra 3 fra le 2 posizioni disponibili rimaste (con 2 scelte possibili); infine, fissata tale scelta, la scelta della posizione della cifra 4 è obbligata; restano poi da inserire le 5 cifre 1,2,3,4,6 nelle 2 posizioni finali (con 52 scelte possibili) dunque il numero di x nel caso a) è (per il principio delle scelte multiple) uguale al prodotto 6252=300. Ragionamenti simili per i casi b),c) portano al risultato 300+300+300=900, per il principio della somma.
Esercizio 3. Ogni vertice con prima cifra 0 o 1 è adiacente a tutti gli altri vertici del grafo, dunque il grafo è connesso (per costruire un cammino fra 2 vertici qualunque basta passare per uno dei suddetti vertici) e nel grafo vi è una sola componente connessa, che ha numero di vertici 45 (il numero di parole di lunghezza 5 su un alfabeto di 4 lettere). Nella colorazione del grafo: per ognuno dei vertici con prima cifra 0 (in numero di 44) si devono usare 44 colori diversi; per ognuno dei vertici con prima cifra 1 (in numero di 44) si devono usare altri 44 colori diversi; i vertici con prima cifra 2 o 3 (essendo adiacenti solo ai vertici con prima cifra 0 o 1) si possono colorare tutti con un ulteriore colore: il numero cromatico del grafo è dunque 44+44+1. Ogni vertice con prima cifra 0 o 1 (adiacente a tutti gli altri vertici del grafo) ha grado 45-1 (dispari); ogni vertice con prima cifra 2 o 3 (adiacente solo ai vertici con prima cifra 0 o 1) ha grado 44+44. Poiché vi sono più di 2 vertici di grado dispari, non esiste nel grafo un cammino Euleriano (ciclico o non ciclico).
Esercizio 4. I sottoinsiemi di B che contengono A e che hanno cardinalità pari si ottengono aggiungendo ad A rispettivamente 1 o 3 o 5 o 7 elementi del complementare B-A (che ha 7 elementi): quindi le possibili scelte, per il principio della somma, sono in numero di
7 7 5 7 3 7 1
7 . I sottoinsiemi di A che hanno cardinalità dispari 1,3,5 o 7 sono in numero esattamente uguale, per le note formule del calcolo combinatorio.
Esercizio 5. a) Si può applicare il principio delle scelte multiple: le coppie possibili da inserire in ognuna delle 9 caselle sono in numero di 68=48, dunque le matrici di A sono in numero di 489.
b) Si può applicare il principio di inclusione-esclusione in forma positiva: se X (rispettivamente Y) è il sottoinsieme di A formato dalle matrici in cui la diagonale principale (rispettivamente la secondaria) contiene solo coppie il cui secondo elemento è >5, la risposta è XY=X+Y-XY.
Tenendo conto che le coppie il cui secondo elemento è >5 sono in numero di 63=18, con il principio delle scelte multiple si ricavaX=Y=183486, XY=185484.
