4.1 - Due formule interessanti
Qualche anno fa chiesi al mio amico Ernesto P. quante
partite (sola andata, niente rivincita) si potessero organizzare con 10
squadre.
Nella mia mente avevo l’ovvia risposta: tante quante
sono le coppie non ordinate costruibili con 10 oggetti, ovvero (10·9)/2 = 45.
Dopo qualche secondo, contrariamente alle mie
previsioni, Ernesto trovò la risposta esatta.
Aveva però effettuato il calcolo con una strategia
diversa dalla mia:
a → b → c → d → e → f → g → h → i → l
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…
9+8+7+6+5+4+3+2+1=45 partite.
L’ amico mi aveva “fregato”.
Per consolarmi, gli riformulai il quesito con
riferimento a 100 squadre.
Ernesto obiettò che ci sarebbe voluto molto tempo per
svolgere il calcolo 99+98+97+…+3+2+1
Io gli replicai che sapevo per certo che un bambino di
8 anni era stato capace di calcolare quella somma in pochi minuti ed egli si
mise “sotto” con impegno.
Dopo un po’, tuttavia, rinunciò per noia.
Non avevo bluffato.
Quel bambino era il piccolo Gauss, nella classe del
quale il maestro aveva dato da svolgere come “penso” Il calcolo in questione, e
che ci riuscì in brevissimo tempo dopo aver scritto lo schema
S = 1 +
2 + 3 + ……………
+ 97 + 98 + 99
S = 99 + 98 + 97 + ………………. .+ 3 + 2
+ 1
2S = 100+ 100+100+ ………………. +100
+100 +100
99
addendi, ciascuno uguale a 100
2S = 99∙100
S =
(99∙100)/2=9900/2=4950
Generalizzando il procedimento, avremo
S = 1 +
2 + 3 + …………
+ (n-2) + (n-1) + n
S = n + (n-1)+ (n-2) + ………….
+ 3 + 2 +
1
-----------------------------------------------------------------------------------
2S = (n+1)+(n+1)+(n+1) + ……………. +
(n+1) + (n+1)+(n+1)
n
addendi, ciascuno uguale a (n+1)
2S = n(n+1)
S = n(n+1)/2
|
FORMULA
(DI GAUSS) per la somma dei primi n numeri interi positivi: 1+2+3+……+n = n(n+1)/2 |
Passiamo ora ad un’altra questione assai interessante.
|
Se un insieme I contiene n elementi, quanti elementi
ha il suo insieme delle parti P(I)? In altre parole, quanti sono i sottoinsiemi di un
insieme di n elementi? Si dimostra che la risposta è : 2n |
Un modo per provare questo asserto è il seguente:
Immaginiamo di ordinare, in un modo qualsiasi, gli
elementi di I.
a, b, c, d, …..
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 2n modi diversi.
Pertanto, i sottoinsiemi di I sono in numero di 2n.
Le due formule introdotte in questa pagina ben
completano quanto abbiamo detto a proposito del Calcolo Combinatorio.
q Esercizio
proposto:
Dare una dimostrazione
alternativa delle due formule viste, tramite il Principio di Induzione
Matematica.