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 PrincipleMultiplication 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:

Numero di scelte per la lingua

Numero di scelte per la musica

Numero di scelte per l’arte

. .3 2 2

..3 2 2 12=

Nel problema-2 the MCP dàMCP dà rapidamenterapidamente il numero delle scelte che si possono effettuare, senza dire quali sono

Spagnolo

Francese

Tedesco

banda

coro

banda

coro

banda

disegnopittura

disegnopitturadisegnopittura

disegnopittura

disegnopittura

disegnopittura

Un diagramma ad albero dice quante e qualidiagramma 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

DIAGRAMMA AD ALBERODIAGRAMMA AD ALBERO

coro

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?

Scelte per la domanda 1

Scelte per la domanda 2

Scelte per la domanda 3

Scelte per la domanda 4

Scelte per la domanda 5

. . . .4 4 2 2 2

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 …

12824 32

La probabilità di rispondere esattamente a tutte le domande = 1/128 = 0,0078125

In questo caso, sarebbe troppo laborioso un diagramma ad albero

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!

Mettere in fila n oggetti, PermutazioniI gruppi differiscono solo per l’ordine

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 4Nella 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?

SoluzionePer 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=6Nota bene: 3x2x1=3!

Si può risolvere anche utilizzando un diagramma ad albero.

diagramma ad albero 3x2x1diagramma ad albero 3x2x1 risultatirisultati

Cristina Gaia Ines

Problema 4 bIn 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 8Quante parole di tre lettere possono essere scritte utilizzando solo le

cinque vocali?a) Con ripetizioneb) 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=125b) 5 scelte per la prima lettera, 4 per la seconda, 3 per la terza, quindi

numero di parole = 5x4x3

Problema 91. 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à?

Con ripetizione5x5x5=125

Per conoscere QUANTE SCELTE basta utilizzare MCP.

Per sapere QUALI SCELTE ci vuole l’albero.

Soluzione problema 8a

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 21-1=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

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}

ENNUPLE ORDINATE E 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!

n-ple (ennuple) non ordinate,

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,D), (A,D,B), (D,A,B), (B,A,D), (D,B,A), (B,D,A),

I 6 gruppi ordinati(A,B,C), (A,C,B), (C,A,B), (B,A,C), (C,B,A), (B,C,A),

I 6 gruppi ordinati(A,B,E), (A,E,B), (E,A,B), (B,A,E), (E,B,A), (B,E,A),

ECC.

sono 1 gruppo non ordinato{A,B,C}

sono 1 gruppo non ordinato{A,B,D}

sono 1 gruppo non ordinato{A,B,E}

…

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: due gruppi differiscono solo per gli oggetti

FORMULE: disposizioni D, permutazioni P, combinazioni C

!k

DC k,n

k,n !k

)kn(...)n)(n(nC k,n

121

)!kn(!k

)!kn)(kn)...(n)(n(nC k,n

121

)!kn(!k

!nC k,n

k

nC k,n

Coefficiente binomiale

)kn...)n)(n(nD k,n 121 !nPn

Problema 117 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 12Devo 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 10In quanti modi un professore può scegliere 5 ragazzi, su un totale di 21, per interrogarli.

20349516

20

165

161718192021

5

1718192021

!!

!

!!

!

!

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

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

SOLUZIONE PROBLEMI PER CASA