3 - FORMULE, REGOLE E PRINCIPI INTERESSANTI
3.1 - La formula di Gauss per la somma dei primi n interi positivi
Diversi anni fa domandai
per gioco al mio amico Ernesto P. se sapeva dirmi di quante partite
(incontro “secco”,
niente rivincita) è composto un torneo a 10 squadre.
Nella mia mente mi
figuravo il ragionamento che avrebbe condotto a rispondere correttamente:
“tante quante sono le
coppie non ordinate costruibili con 10 oggetti, ovvero ”.
Banale, per chi avesse
qualche conoscenza di Calcolo Combinatorio … non era però il caso del buon
Ernesto.
Che tuttavia, dopo una
breve riflessione, fu in grado di darmi, sorprendendomi alquanto, la risposta
esatta;
determinata, comunque, con
una strategia completamente diversa dalla mia.
Ernesto aveva
considerato la sequenza e aveva pensato:
“la
squadra a gioca con tutte e 9 le squadre scritte alla sua destra;
la squadra b gioca con tutte e 8
le squadre alla sua destra …
dunque si avranno 9+8+7+6+5+4+3+2+1 = 45 partite”.
L’amico era stato davvero bravo e svelto.
Così io subito, perfidamente, gli
riformulai il quesito con riferimento a 100 squadre.
E quando lui obiettò che ci sarebbe voluto
molto tempo per svolgere il calcolo 99+98+97+…+3+2+1,
gli feci presente che un bambino di otto
anni era stato capace di determinare quella somma in pochi minuti.
Ernesto ci si mise dunque “sotto” con
impegno ... dopo un po’, tuttavia, rinunciò per noia.
Non avevo bluffato. Quel bambino era il piccolo Gauss (1777-1855),
destinato a diventare uno dei più grandi
matematici della Storia. Nella sua classe
il maestro aveva dato da svolgere agli alunni, per farli stare un po’
bravi, la somma 1+2+3+ … +99, e lui ci riuscì in un tempo incredibilmente
breve, dopo aver scritto lo schema
Generalizzando
il procedimento alla somma 1+2+3+…+n dei primi n interi positivi, avremo
Resta così acquisita l’importante
|
FORMULA (DI GAUSS) per la somma dei primi n
numeri interi positivi: |
|
3.2 - Quanti sono i sottoinsiemi di un
insieme di n elementi?
|
Se un insieme I contiene n elementi, quanti elementi ha il suo
insieme delle parti P(I)? Insomma, quanti sono i sottoinsiemi di un insieme di n
elementi? |
|
Risposta: |
Un
modo per provare questo asserto è il seguente.
Immaginiamo di ordinare, in un modo qualsiasi,
gli elementi di I:
Ora, se vogliamo costruire un sottoinsieme di
I, potremo passare in rassegna questi elementi “schierati”
come dei soldatini, per scegliere quali
inserire nel nostro sottoinsieme e quali invece non inserire.
· Per
a abbiamo 2 possibilità: SI’ (inserirlo nel sottoinsieme che stiamo
costruendo) o NO (non inserirlo).
· Per
b abbiamo 2 possibilità (SI’ o NO) …
· Per
c abbiamo 2 possibilità (SI’ o NO) …
· …
In
definitiva, la costruzione di un sottoinsieme di I può avvenire in modi diversi.
Pertanto, i sottoinsiemi di I sono in numero
di .
Ad esempio, quindi, l’insieme dei 12 Apostoli
ha sottoinsiemi.
3.3 - Regola della somma
Se A e B sono due insiemi finiti DISGIUNTI
(
= privi di intersezione = la cui intersezione è l’insieme vuoto = privi di
elementi comuni),
allora
[
indica il numero degli elementi di
,
ecc.]
E
lo stesso vale se gli insiemi finiti di
cui facciamo l’unione sono 3 o più e sono a due a due disgiunti.
3.4 - Principio di Inclusione/Esclusione (PIE)
Se A e B sono due
insiemi finiti QUALSIASI, allora
In
effetti, se per calcolare noi determinassimo la somma
,
sbaglieremmo in quanto
ci
ritroveremmo a CONTARE 2 VOLTE gli elementi di :
se un elemento è comune ad A e a B,
facendo
lo si conta una prima volta come elemento di A
e poi una seconda volta come elemento di B.
Per
cui basterà, partendo da ,
sottrarre
,
per avere il n° esatto degli elementi di
.
Per tre insiemi finiti A, B, C la formula è un po’ più complicata:
.
Prova
tu stesso a cercare la giustificazione di questa uguaglianza!
In
generale, per contare il numero degli elementi dell’unione di N insiemi
finiti ,
la formula è
Esempio 1 - Quanti sono i numeri, da 1 a 1 milione,
divisibili per 2 o per 3?
Risposta:
posto , per il
PIE avremo
3.5
- Regola del complementare
A volte, se ci si trova all’interno di
un insieme universo finito ,
e l’obiettivo è di contare il numero
degli elementi di un suo sottoinsieme A,
risulta invece più agevole contare il
numero degli elementi del complementare
di A, dopodiché si sottrarrà:
.
Questo “passaggio al complementare” è
particolarmente utile, di norma, quando l’insieme A è definito
come l’insieme degli elementi di che soddisfano ad ALMENO UNA fra due o più
condizioni.
Il
complementare di A sarà infatti, in questo caso, l’insieme
degli elementi di
che
non verificano NESSUNA delle condizioni in gioco.
E
di norma calcolare il numero degli elementi di questo sarà più semplice, perché la determinazione
diretta
del
numero di elementi di A, per via della parola “almeno”, comporterebbe una
laboriosa distinzione di casi.
Esempio 2 - Quanti sono i numeri di 3 cifre che
presentano almeno una volta la cifra “1” ?
3.6
- Regola del prodotto cartesiano
Ricordiamo
che il prodotto cartesiano di due insiemi A,
B
è l’insieme i cui elementi sono le coppie
ordinate nelle quali
e
.
Bene, il
numero degli elementi di ,
essendo A, B due insiemi finiti,
è semplicemente dato dal risultato della
moltiplicazione .
E la stessa regola si estende al prodotto cartesiano di tre o più insiemi.
Ad
esempio, in un torneo andata-e-ritorno con 12 squadre, detto S l’insieme di
queste squadre,
l’insieme
di tutte le partite coincide sostanzialmente col prodotto cartesiano ,
PRIVATO però
delle
coppie i cui due elementi coincidono (perché evidentemente una squadra non
gioca contro sé stessa).
Quindi
il numero di partite del torneo è dato da
(risultato,
questo, che si poteva ricavare anche con altre modalità di ragionamento).