Giochi matematici – Trucchi del mestiere: in quanti modi

È una domanda apparentemente semplice, ma spesso proposta nei quesiti delle gare matematiche. Le risposte possono essere trovate facilmente ricorrendo al calcolo combinatorio

Il calcolo combinatorio e le nozioni di disposizione, permutazione e combinazione sono tra gli strumenti più utili nella risoluzione dei quesiti che vengono proposti nelle gare matematiche. Devono essere “sfoderati”, almeno come idea alla quale fare inizialmente riferimento, ogni volta che si tratta di elencare e poi contare diverse situazioni che si creano facendo intervenire vari oggetti o persone oppure organizzandoli in vari modi e con diversi ordinamenti. Insomma, è opportuno pensare al calcolo combinatorio quando la domanda del quesito è del tipo: «In quanti modi è possibile…?».

Ricordiamo le nozioni di disposizione, permutazione e combinazione e le formule che danno il loro numero.

Quanti sono i numeri di 2 cifre che si possono scrivere con quelle del numero 1234? Abbiamo 4 cifre (quelle del numero 1234) e dobbiamo considerarle a due a due, per formare i numeri di 2 cifre che ci sono richiesti. L’ordine in cui le prendiamo è importante perché, per esempio, il numero 13 è diverso da 31. In generale, se abbiamo n oggetti e li studiamo a k a k (con k < n) distinguendo anche l’ordine nel quale compaiono, avremo tanti allineamenti che vengono chiamati disposizioni di n oggetti di classe k. Il loro numero è indicato con D_n,k. Per trovare il valore di D_n,k e il numero di tutti gli allineamenti di k oggetti scelti tra n, pensiamo a k caselle o posti che dobbiamo occupare in tutti i modi possibili con gli n oggetti di cui disponiamo. Il primo posto può essere occupato in n modi diversi. Per ognuna di queste scelte, il secondo posto può essere occupato in n – 1 modi diversi (abbiamo a disposizione tutti gli n oggetti, tranne quello che già occupa il primo posto); in totale abbiamo quindi n(n – 1) modi diversi di occupare i primi due posti. Ragionando allo stesso modo, per ognuna di queste scelte abbiamo n – 2 modi di occupare il terzo posto e quindi, complessivamente, n(n – 1) (n – 2) modi di occupare i primi tre posti e così via. Arriviamo all’ultimo posto da occupare: il k-esimo. Abbiamo occupato i primi k – 1 posti, sistemando in vari modi k – 1 oggetti. Ce ne rimangono n – (k – 1) = n – k + 1 e quindi vi sono n – k + 1modi di occupare l’ultimo posto. Alla fine, otteniamo: D_n,k = n(n – 1)(n – 2)…(n – k + 1) Il valore di D_n,k è dato dal prodotto di k numeri interi, da n fino a n – k + 1. Per tornare all’esempio iniziale ricaviamo: D_4,2 = 4·3 = 12; D_7,3 = 7·6·5 = 210; D_5,4 = 5·4·3·2 = 120.

Quanti sono gli anagrammi della parola “PRISMA”? Un anagramma è un diverso modo di allineare – l’ordine è importante – le lettere che compongono, in questo caso, la nostra testata PRISMA. Abbiamo 6 lettere e dobbiamo allinearle tutte in modo diverso. È la stessa situazione analizzata prima con la differenza che ora gli oggetti (le lettere della parola in questione) vanno tutti considerati, cioè: k = n. Gli allineamenti di n oggetti, presi tutti in considerazione, vengono chiamati permutazioni. Il loro numero è indicato con P_n. Per trovarlo, possiamo ripetere il ragionamento che ci ha portato a calcolare D_n,k. Solo che adesso vale k = n. Otteniamo quindi: P_n = D_n,n = n(n –1)(n – 2)…1. Questo prodotto di n interi, da n fino a 1, è indicato con n! che si legge “n fattoriale”. Abbiamo quindi: P_n = n!. Il numero di anagrammi della parola “PRISMA”, per tornare all’esempio precedente, è dato da P₆ =6! = 6·5·4·3·2·1 = 720. Torniamo alla condizione k < n.

Quante sono le possibili terne nel gioco del Lotto? Al Lotto si gioca con i numeri 1, 2, …, 90 e una terna è costituita da tre numeri estratti tra i 90. Abbiamo quindi n = 90 e k = 3 ma in questo esempio, l’ordine in cui vengono estratti i tre numeri non è importante. Quando l’odine è irrilevante gli allineamenti di k oggetti, scelti tra gli n che si hanno a disposizione, sono chiamati combinazioni di n oggetti di classe k. Per trovare il loro numero C_{n, k}, possiamo pensare alle analoghe disposizioni e al loro numero D_{n, k}. Se in una qualunque disposizione permutiamo tra loro i k oggetti queste k! permutazioni corrispondono a un’unica combinazione (perché gli elementi sono sempre gli stessi e nelle combinazioni l’ordine non è importante). Abbiamo allora: C_n,k = D_n,k/k! = n(n – 1) (n – 2) … (n – k + 1)/k!

Possiamo scrivere la formula che dà C_n,k anche in un altro modo. Se moltiplichiamo numeratore e denominatore per (n – k)!, ricaviamo: C_n,k = n(n – 1)(n – 2) … (n – k + 1)(n – k)!/k! (n – k)! = = n(n –1)(n – 2)…·2· 1 = n! k!(n – k)! k!(n – k)! . Tornando al gioco del Lotto abbiamo, quindi, che il numero delle terne possibili è dato da: C_90,3 = 90! = 90·89·88·87!= 90·89·88= 117.480 3!87! 3!87! 3!

Sveliamo a questo punto un’ipotesi che abbiamo tenuto nascosta (ma che al lettore avveduto non sarà certo sfuggita). Le cifre del numero 1234 erano tutte diverse tra loro; anche le lettere della parola “PRISMA” erano distinte, così come i numeri del gioco del Lotto. Quando i k oggetti che si prendono in considerazione sono tutti distinti tra loro, come accadeva negli esempi fatti finora, si parla di disposizioni, permutazioni e combinazioni semplici. Facciamo invece riferimento a disposizioni, permutazioni e combinazioni con ripetizione quando negli allineamenti di k elementi è anche possibile ripetere più volte uno stesso oggetto. Indichiamo con D′ _n,k, C′ _n,k, P′ _n1,…,nh, , rispettivamente, il numero delle disposizioni e delle combinazioni con ripetizioni di n oggetti di classe k e il numero delle permutazioni di n oggetti di cui n₁ sono uguali tra loro, …, n_h sono uguali tra loro (e distinti dai precedenti). Si dimostra che: D′ _n,k = n^k , C′ _n,k = (n + k – 1)!/k!(n – 1)!, P′ _n1,…,nh =n!/n1 ! … nh ! Per esempio quanti sono i numeri di due cifre che si possono scrivere con le cifre 1, 2, …, 9? Abbiamo nove cifre e le dobbiamo prendere in considerazione a due a due. In questo caso, però, uno stesso elemento può essere ripetuto. Ci riferiamo dunque alle disposizioni (l’ordine in cui scriviamo le cifre è importante!) con ripetizione. Il numero richiesto è D′ _9,2 = 92 = 81. Quante sono le possibili terne nel gioco del Lotto, se ogni numero estratto viene poi rimesso nell’urna? La formula delle combinazioni con ripetizione ci dà il numero C′ _90,3 = 92!/3!89! = … Quanti sono gli anagrammi della parola “MATEMATICA”? Sono le permutazioni di dieci elementi ma la lettera “M” compare due volte, la “A” compare tre volte e la “T” compare due volte. Gli anagrammi richiesti sono quindi: 10!/2!3!2! = 151.200.