Università LiberEtà Udine, 25 ottobre 2007
Giuseppina Trifiletti
In matematica una procedura si dice elegante se è sia
chiara che semplice. Per esempio la moltiplicazione può
essere usata per risolvere molti tipi di problemi di
calcolo. Se riesci a creare con i dati del problema una
matrice rettangolare vedrai con chiarezza la
moltiplicazione che ti permette di trovare il risultato
Multiplication Counting Principle: se una
scelta può essere fatta in m modi e una seconda
scelta in n modi, allora ci sono m.n modi di fare la
prima scelta seguita dalla seconda scelta.
Problema 1
Supponi che uno stadio abbia 9 porte. Le porte A, B, C, D sono sul lato
nord. Le porte E, F, G, H, I sono sul lato sud. In quanti modi diversi
puoi entrare nello stadio attraverso una porta a nord e andartene
attraverso una porta a sud?
MATRICE RISOLVENTE
E
F
G
H
I
A
(A,E)
(A,F)
(A,G)
(A,H)
(A,I)
B
(B,E)
(B,F)
(B,G)
(B,H)
(B,I)
C
(C,E)
(C,F)
(C,G)
(C,H)
(C,I)
D
(D,E)
(D,F)
(D,G)
(D,H)
(D,I)
Si può notare che la matrice ha 4 righe e 5 colonne, così che ci sono
4x5=20 coppie nella tabella. Ci sono quindi 20 modi per entrare da una
porta nord e per uscire da una porta sud
Problema 2
Una scuola superiore vuole offrire agli studenti un corso di lingua straniera, un
corso di musica, e un corso di arte. Le classi di lingua straniera sono: una
classe di Francese, una di Spagnolo e una di Tedesco. Le classi di musica sono
coro e banda. Le classi di arte sono disegno e pittura. In quanti modi diversi gli
studenti possono scegliere 3 corsi, uno di lingua straniera, uno di arte, uno di
musica?
Soluzione utilizzando MCP
Si potrebbero usare due matrici: prima una 3x2 e poi una 6x2, perché?
Oppure, più semplicemente:
3
Numero di scelte
per la lingua
3
.
.
2
Numero di scelte
per l’arte
2
.
2
.
= 12
2
Numero di scelte
per la musica
Nel problema-2 the MCP dà rapidamente il numero delle scelte che si
possono effettuare, senza dire quali sono
DIAGRAMMA AD ALBERO
coro
Francese
banda
coro
Spagnolo
banda
coro
Tedesco
banda
disegno
pittura
disegno
pittura
disegno
pittura
disegno
pittura
disegno
pittura
disegno
pittura
Un diagramma ad albero dice quante e quali sono le scelte. Ciascuna scelta
può essere trovata seguendo un percorso da sinistra a destra. Il numero delle
scelte si ottiene moltiplicando, il numero delle scelte ad ogni livello: 3, poi 2, poi
ancora 2, oppure a destra, il numero finale delle uscite, cioè 12
Problema 3
Il prof. Primo Gilone, che i suoi studenti identificano con un soprannome che è
un anagramma del suo nome, il prof. Rompiglione, ha dato per castigo un
difficilissimo, anche se breve, test di algebra. Pierino decide di non spremersi le
meningi per nulla nel fare il compito, convinto com’è che non ci sarebbe molta
differenza nel voto finale comunque lui intenda procedere.
Decide di divertirsi e di rispondere a caso. Però vuole calcolare, sempre per
divertimento, che probabilità ha di rispondere in modo corretto alle domande di
Rompiglione.
Il test ha due domande a scelta multipla (A, B, C, D), di cui una sola è la
risposta esatta, e tre domande Vero-Falso. Copiare è impossibile perché ogni
studente ha risposte diverse.
• Quanti possibili modi ci sono per Pierino di rispondere alle domande?
• Qual è la probabilità che Pierino risponda correttamente a tutte le domande di
Rompiglione?
Ci può aiutare il MCP? E un diagramma ad albero?
4
. Scelte per la .Scelte per la . Scelte per la .Scelte2per la
4
Scelte per la
domanda 1
domanda 2
2
domanda 3
2
domanda 4
domanda 5
 42  23  128
Se il prof. Rompiglione avesse fatto m domande con 4 possibili scelte, n
domande con 7 possibili scelte e p domande con 2 possibili scelte, in
quanti modi possibili si poteva rispondere?
Se il prof. Rompiglione avesse fatto m domande con i possibili scelte, n
domande con j possibili scelte e p domande con k possibili scelte, in quanti
modi possibili si poteva rispondere?
Ed infine quale è nei vari casi la probabilità di rispondere in modo corretto al test di
Rompiglione?
Solo una tra tutti i modi possibili di rispondere al Test è quello esatto. Quindi …
La probabilità di rispondere esattamente a tutte le domande = 1/128 = 0,0078125
In questo caso, sarebbe troppo laborioso un diagramma ad albero
Mettere in fila n oggetti, Permutazioni
I gruppi differiscono solo per l’ordine
Dati n oggetti, essi si possono "mettere in fila" (o
“mettere in coda”, o “mettere in colonna”) in n!
(leggi: “n fattoriale”)
modi diversi, dove il
simbolo n! indica il numero
n·(n-1)·(n-2)· …
·3·2·1.
n·(n-1)·(n-2)· … ·3·2·1 = n!
Infatti,
per la scelta del primo oggetto della fila abbiamo n
possibilità;
a ciascuna di queste n possibilità sono abbinate (n-1)
possibilità di scelta per il secondo oggetto della fila;
ad ognuna delle n·(n-1) possibilità per i primi due oggetti
corrispondono (n-2) possibilità di scelta per il terzo
oggetto della fila; ... ;
in totale, quindi, n oggetti possono essere ordinati (=messi
in fila, o in coda, o in colonna) in
n·(n-1)·(n-2)· … ·3·2·1 = n! modi diversi.
Problema 4
Nella gara di corsa femminile 4x100m del 2005, la squadra italiana era
formata da Cristina, Gaia, Ines e Giorgia
L’allenatore decise che Giorgia avrebbe corso il tratto iniziale. In quanti
modi diversi l’allenatore avrebbe potuto far correre i 3 tratti del percorso
alle altre 3 atlete?
Soluzione
Per la prima atleta, delle tre rimaste, c’erano 3 possibilità. Una volta
scelto il tratto per la prima rimanevano 2 possibilità per la seconda. Dopo
aver fatto queste scelte restava 1 sola possibilità per il terzo tratto del
percorso.
Quindi, applicando MCP, si ottiene 3x2x1=6
Nota bene: 3x2x1=3!
Si può risolvere anche utilizzando un diagramma ad albero.
diagramma ad albero 3x2x1
Cristina
Gaia
risultati
Ines
Problema 4 b
In quanti modi diversi si possono mettere in fila 12 persone se
arrivano tutte contemporaneamente allo sportello della posta? 12!
Problema 5. In quanti modi 20 quadri possono essere messi sulla
parete di un corridoio di una mostra d’arte?
S: 20x19x18x17x16x15x14x13x12x11x10x9x8x7x6x5x4x3x2x1=
…
Problema 6. In quanti modi diversi posso mettere in ordine 6 libri, 4
di matematica e 2 di fisica, in modo tale che i libri di matematica
stiano vicini e così i libri di fisica?
S: 4!x2!x2!=96
Problema 7. In quanti modi diversi si può anagrammare lana, luna,
limbo, torta, carroccio, cartoccio, catino, e perché?
S: Lana in 4!/2!, luna in 4!, limbo in 5!, torta in 5!/2!, carroccio in
9!/(3!x2!x2!), cartoccio in 9!/(3!x2!), catino in 6! Modi
Problema 8
Quante parole di tre lettere possono essere scritte utilizzando solo le
cinque vocali?
a) Con ripetizione
b) Senza ripetizione ( non utilizzare una vocale più di una volta in una
stessa parola)
Soluzioni:
a) 5 scelte per la prima lettera, 5 per la seconda, 5 per la terza; applicando
l’ MCP quindi numero di parole = 5x5x5=125
b) 5 scelte per la prima lettera, 4 per la seconda, 3 per la terza, quindi
numero di parole = 5x4x3
Problema 9
1. Quante sono le parole di sette lettere costruibili utilizzando tutte le
lettere dell’alfabeto italiano, ma senza ripetizione, cioè con il vincolo di
non utilizzare una lettera più di una volta in una stessa parola?
21x20x19x18x17x16x15 = 21!/14!=D21,7=21!/(21-7)!
2. Quante sono le parole di sette lettere costruibili utilizzando tutte le
lettere dell’alfabeto italiano, ma senza consecutività?
Soluzione problema 8a
Per
conoscere
QUANTE SCELTE
basta utilizzare MCP.
Per sapere QUALI
SCELTE ci vuole
l’albero.
Con ripetizione
5x5x5=125
Senza ripetizione devo
togliere qualche percorso
Soluzione problema 9
1. Per la prima scelta ho 21 possibilità, per la seconda 20
(non posso riutilizzare la lettera già utilizzata), per la terza
19, non posso utilizzare le due che ho già utilizzato …
21x20x19x18x17x16x15=27907200 =
= 21!/14!=D21,7=21!/(21-7)!
2. Per la prima scelta ho 21 possibilità, per la seconda 211=20 scelte possibili (non devo considerare la lettera che
ho appena adoperato), per la terza 21-1 scelte (non devo
considerare la lettera che ho appena adoperato, ma tutte le
altre sì) …
21x20x20x20x20x20x20=21x206=1344000000
ENNUPLE ORDINATE E NON ORDINATE
Una sequenza di n elementi si dice, genericamente, n-upla
(per n=2 si parlerà di "coppia", per n=3 di "terna", per n=4 di
"quaterna", per n=5 di "cinquina", per n=6 di "sestina", per n>6 di
"sequenza di 6, 7, 8, ... elementi").
Quando in un'n-upla consideriamo "importante" l'ordine in cui gli
elementi si susseguono, parleremo di n-upla ordinata, e la
indicheremo con parentesi tonde: (x1, x2, …., xn)
Quando consideriamo irrilevante l’ordine, parleremo di n-upla
non ordinata e useremo le graffe: { x1, x2, …., xn}
n-ple (ennuple) non ordinate,
Se in un certo problema noi abbiamo considerato inizialmente le
n-uple ordinate, ma in realtà ci interessano le n-uple NON
ordinate, dobbiamo pensare il nostro elenco di n-uple ordinate ripartito
in tanti gruppi, avendo noi posto in ciascun gruppo tutte le n-uple
"equivalenti" ad un'n-upla data (cioè, contenenti gli stessi elementi, se
pure in ordine diverso).
Abbiamo così tanti gruppi, ciascuno formato da n! n-uple, e ciascun
gruppo va contato "come se si trattasse di una sola n-upla".
E' chiaro allora che il numero totale delle n-uple ordinate andrà
diviso per n!
Per esempio supponiamo di aver fatto con 5 oggetti a disposizione
gruppi di 3 oggetti, senza ripetizione, quindi 5x4x3=60 gruppi
ordinati (due gruppi sono diversi se differiscono per un elemento o per
l’ordine).
I 6 gruppi ordinati
(A,B,C), (A,C,B), (C,A,B), (B,A,C),
(C,B,A), (B,C,A),
sono 1
ordinato
{A,B,C}
gruppo
non
I 6 gruppi ordinati
(A,B,D), (A,D,B), (D,A,B), (B,A,D),
(D,B,A), (B,D,A),
sono 1
ordinato
{A,B,D}
gruppo
non
I 6 gruppi ordinati
(A,B,E), (A,E,B), (E,A,B), (B,A,E),
(E,B,A), (B,E,A),
sono 1
ordinato
{A,B,E}
gruppo
non
…
ECC.
Quindi
(5x4x3)/3!=60/6
=
10 gruppi NON ordinati.
DISPOSIZIONI:
due gruppi di oggetti
differiscono o per l’ordine e per gli oggetti
PERMUTAZIONI:
due gruppi differiscono
solo per l’ordine
COMBINAZIONI:
solo per gli oggetti
due gruppi differiscono
FORMULE: disposizioni D, permutazioni P, combinazioni C
Dn ,k  n( n  1 )( n  2 )  ...  n  k  1 )
Pn  n!
n( n  1 )( n  2 )  ...  ( n  k  1 )

k!
Cn ,k
Dn ,k

k!
Cn ,k
n( n  1 )( n  2 )...( n  k  1 )( n  k )!

k ! ( n  k )!
Cn ,k
Cn ,k
n!

k ! ( n  k )!
Cn ,k
n
 
k 
 
Coefficiente
binomiale
Problema 10
In quanti modi un professore può scegliere 5 ragazzi, su un totale di
21, per interrogarli.
21  20 19 18 17 21  20 19 18 17 16!
20!


 20349
5!
5!16!
16!5!
Problema 11
7 amici, Antonio (A), Bruno (B), Mattia (M), Ernesto (E), Piero (P),
Luca(L), Giorgio (G), devono passare una notte in una stanza in cui ci
sono solo 3 letti.
In quanti modi è possibile scegliere 3 tra di loro 7 che dormiranno nei
letti?
(7x6x5)/3!=7x6x5/6=35
Problema 12
Devo fare un viaggio, in quanti modi diversi posso scegliere 3 di 8
magliette e 4 tra 7 gonne per fare i bagagli?
[(8x7x6)/3!]x[(7x6x5x4)/4!]
Problema 13
Un ragazzo che frequenta una ragazza di nascosto dai
genitori di lei, si reca la sera sotto la finestra della sua
bella con quattro luci di colori diversi per poter
comunicare con l’innamorata senza parlare e anche ad
una certa distanza.
Quanti messaggi diversi può formulare per la sua bella,
accendendo o spegnendo le varie luci.
G=gialla
V=verde
R=rossa
B=bianca
4+4x3+4x3x2+4x3x2x1=4+12+24+24=64
SOLUZIONE PROBLEMI PER CASA
A.
In quanti modi diversi si può anagrammare LANA (4!/2!=12), LUNA (4!=24), LIMBO
(5!=120), TORTA (5!/2!=60), CARROCCIO (9!/(3!2!2!)), CARTOCCIO
(9!/(3!2!)), CATINO (6!), e perché?
Perché ad esempio ABCD (LANA) e ACBD (LNAA), sono lo stesso di ADCB (LANA) e
ACDB (LNAA), e così via. Per ogni anagramma di lana ce ne è un altro in cui cambio di
posto B e D (cioè le due A) che è identico al primo: devo quindi dividere per 2.
Per CARTOCCIO invece per ogni anagramma ce ne sono altri 6 in cui cambio di posto le
3 C in tutti i modi possibili, e, per ognuno di questi 6 ce ne sono altri 2 in cui cambio di
posto le due O: devo quindi dividere per 12
Ecc.
B.
In quanti modi diversi posso scegliere 3 di 5 magliette e 2 tra 4 gonne?
Per la scelta delle magliette (non è importante l’ordine) ci sono [(5x4x3)/3!]=10 modi,
per ognuno di questi modi ci sono [(4x3)/2!]=6 modi per la scelta di 2 gonne su
quattro, quindi per la scelta delle 3 magliette seguite dalla scelta di 2 gonne ci
sono in tutto [(5x4x3)/3!] x [(4x3)/2!] = 10x6 = 60 modi
C.
In quanti modi diversi posso mettere in ordine 6 libri di letteratura, 4 di matematica e 2 di
fisica, in modo tale che i libri di letteratura, di matematica e di fisica stiano vicini? In 6!
modi posso mettere in ordine, vicini tra loro, i libri di letteratura. Per ognuno di questi modi
posso mettere in ordine in 4! modi i libri di matematica. Per ognuna delle precedenti 2
scelte posso ordinare in 2! modi i libri di fisica, poi però ci sono ancora 3! Modi di disporre
in ordine il gruppo di libri di letteratura, quelli di matematica e quelli di fisica (LMF, FML,
FLM, …). In tutto quindi 6!x4!x2!x3! modi