Consideriamo l’insieme dei primi sette numeri naturali positivi:
[math]\displaystyle S=\{1,2,3,4,5,6,7\}.[/math]
Quanti sono i suoi sottoinsiemi, compreso quello vuoto, la cui somma degli elementi è divisibile per 7?
A prima vista potrebbe sembrare un semplice esercizio di calcolo combinatorio, nel quale è sufficiente esaminare le diverse combinazioni di elementi e verificare quali producono una somma multipla di 7.
In realtà, il problema permette di sviluppare un ragionamento più interessante, perché mette in relazione il conteggio dei sottoinsiemi con le congruenze, le simmetrie dell’aritmetica modulare e, successivamente, le funzioni generatrici.
Partiremo da una soluzione accessibile, basata sulle proprietà dell’insieme e sul principio del complemento, per arrivare a una seconda dimostrazione che utilizza le radici dell’unità. Gli esercizi successivi permetteranno di modificare le condizioni iniziali, introducendo un resto assegnato, vincoli sulla cardinalità e una generalizzazione valida per qualsiasi numero primo dispari.
Il problema
Sia
[math]\displaystyle S=\{1,2,3,4,5,6,7\}.[/math]
Dobbiamo determinare quanti sottoinsiemi [math]A\subseteq S[/math], compreso l’insieme vuoto, soddisfano la condizione:
[math]\displaystyle \sum_{a\in A}a\equiv 0\pmod 7.[/math]
La congruenza indica che la somma degli elementi di [math]A[/math] deve essere un multiplo di 7. Ricordiamo che anche l’insieme vuoto soddisfa la condizione, perché la sua somma è convenzionalmente uguale a zero.
Soluzione combinatoria: sfruttiamo la struttura dell’insieme
Il numero complessivo dei sottoinsiemi
L’insieme [math]S[/math] contiene sette elementi e ciascuno di essi può essere incluso oppure escluso da un sottoinsieme. Poiché le due possibilità sono indipendenti per ogni elemento, il numero complessivo dei sottoinsiemi è:
[math]\displaystyle 2^7=128.[/math]
Il nostro obiettivo consiste nell’individuare, tra questi 128 sottoinsiemi, quelli la cui somma è divisibile per 7. Non possiamo però dividere direttamente 128 per 7, perché non abbiamo ancora dimostrato che i sottoinsiemi siano distribuiti uniformemente tra le sette possibili classi di resto.
Per arrivare al risultato conviene osservare una proprietà particolare dell’insieme.
Il numero 7 non modifica il resto della somma
Poiché
[math]\displaystyle 7\equiv 0\pmod 7,[/math]
aggiungere oppure togliere il numero 7 da un sottoinsieme non cambia il resto della somma nella divisione per 7.
Consideriamo quindi l’insieme più piccolo:
[math]\displaystyle T=\{1,2,3,4,5,6\}.[/math]
A ogni sottoinsieme [math]B\subseteq T[/math] corrispondono esattamente due sottoinsiemi di [math]S[/math]:
[math]\displaystyle B
\qquad\text{e}\qquad
B\cup\{7\}.[/math]
Le loro somme differiscono di 7 e, di conseguenza, hanno lo stesso resto nella divisione per 7. Se la somma degli elementi di [math]B[/math] è divisibile per 7, lo sarà anche quella di [math]B\cup\{7\}[/math], mentre se la prima non è divisibile per 7, non lo sarà neppure la seconda.
Indicando con [math]N_T[/math] il numero dei sottoinsiemi di [math]T[/math] con somma divisibile per 7 e con [math]N_S[/math] il numero corrispondente per [math]S[/math], otteniamo:
[math]\displaystyle N_S=2N_T.[/math]
Il problema si riduce quindi al conteggio dei sottoinsiemi validi di [math]T[/math].
Classifichiamo i sottoinsiemi in base alla cardinalità
La cardinalità di un insieme è il numero dei suoi elementi. Possiamo quindi organizzare il conteggio considerando separatamente i sottoinsiemi con zero, uno, due e così via fino a sei elementi.
- Cardinalità 0. L’unico sottoinsieme è l’insieme vuoto, la cui somma è zero. Abbiamo quindi una soluzione.
- Cardinalità 1. Nessuno degli elementi da 1 a 6 è divisibile per 7, perciò non esistono sottoinsiemi validi.
- Cardinalità 2. Cerchiamo le coppie di numeri distinti la cui somma è 7. Le possibilità sono:
[math]\displaystyle \{1,6\},\qquad \{2,5\},\qquad \{3,4\}.[/math]
Otteniamo tre sottoinsiemi.
- Cardinalità 3. La somma di tre elementi deve essere un multiplo di 7. Esaminando le combinazioni distinte, troviamo:
[math]\displaystyle \{1,2,4\},\qquad \{3,5,6\}.[/math]
Sono quindi due le soluzioni.
- Cardinalità 4. Possiamo sfruttare il principio del complemento. La somma di tutti gli elementi di [math]T[/math] è:
[math]\displaystyle 1+2+3+4+5+6=21,[/math]
che è divisibile per 7. Di conseguenza, un sottoinsieme di quattro elementi ha somma divisibile per 7 se e solo se anche i due elementi che non gli appartengono hanno somma divisibile per 7. Le possibilità sono quindi tre, corrispondenti alle coppie individuate in precedenza.
- Cardinalità 5. Il complementare contiene un solo elemento. Poiché nessun elemento di [math]T[/math] è divisibile per 7, non esistono soluzioni.
- Cardinalità 6. L’unico sottoinsieme è [math]T[/math] stesso, la cui somma è 21. Abbiamo quindi un’altra soluzione.
Il conteggio complessivo è riassunto nella tabella:
| Cardinalità | Sottoinsiemi validi |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 2 | 3 |
| 3 | 2 |
| 4 | 3 |
| 5 | 0 |
| 6 | 1 |
| Totale | 10 |
Pertanto:
[math]\displaystyle N_T=10.[/math]
Ricordando che ogni sottoinsieme valido di [math]T[/math] può essere considerato sia senza il 7 sia con il 7, otteniamo:
[math]\displaystyle N_S=2\cdot 10.[/math]
Il risultato del problema è dunque:
[math]\displaystyle \boxed{N_S=20}.[/math]
Abbiamo così risolto il problema senza dover esaminare singolarmente tutti i 128 sottoinsiemi. Il passaggio decisivo è stato riconoscere che il numero 7, essendo congruo a zero modulo 7, può essere aggiunto o eliminato senza modificare la proprietà richiesta.
Un secondo metodo: funzioni generatrici e radici dell’unità
Il conteggio precedente funziona bene quando l’insieme contiene pochi elementi. Se invece vogliamo affrontare insiemi più grandi, oppure costruire una formula generale, possiamo rappresentare tutte le somme dei sottoinsiemi attraverso un polinomio.
Questo collegamento è particolarmente interessante perché trasforma le scelte combinatorie in operazioni algebriche.
Per approfondire il tema è utile anche l’articolo dedicato a contare i sottoinsiemi modulo un primo mediante funzioni generatrici e radici dell’unità.
Costruiamo la funzione generatrice
Consideriamo il polinomio:
[math]\displaystyle P(x)=\prod_{k=1}^{7}(1+x^k).[/math]
Per capire il significato di questa espressione, osserviamo che ogni fattore rappresenta una scelta relativa a un elemento dell’insieme.
Nel fattore [math]1+x^k[/math], il termine 1 corrisponde all’esclusione dell’elemento [math]k[/math], mentre il termine [math]x^k[/math] rappresenta la sua inclusione. Sviluppando il prodotto, scegliamo un termine da ciascun fattore e otteniamo così un termine per ogni sottoinsieme possibile.
Per esempio, scegliendo [math]x[/math] dal primo fattore, [math]x^3[/math] dal terzo e [math]x^5[/math] dal quinto, mentre dagli altri fattori scegliamo 1, otteniamo:
[math]\displaystyle x\cdot x^3\cdot x^5=x^9.[/math]
Questo termine corrisponde al sottoinsieme:
[math]\displaystyle \{1,3,5\}.[/math]
L’esponente rappresenta quindi la somma degli elementi selezionati, mentre il coefficiente di [math]x^m[/math] indica quanti sottoinsiemi hanno somma esattamente uguale a [math]m[/math].
Il nostro obiettivo è diverso: vogliamo sommare tutti i coefficienti degli esponenti multipli di 7.
Il filtro delle radici dell’unità
Per selezionare soltanto gli esponenti divisibili per 7 utilizziamo una proprietà delle radici settime dell’unità.
Poniamo:
[math]\displaystyle \omega=e^{2\pi i/7}.[/math]
Questo numero complesso soddisfa:
[math]\displaystyle \omega^7=1.[/math]
Inoltre, le sue potenze generano le sette radici settime dell’unità:
[math]\displaystyle 1,\omega,\omega^2,\ldots,\omega^6.[/math]
La proprietà che ci interessa è:
[math]\displaystyle \frac{1}{7}\sum_{j=0}^{6}\omega^{jm}
=
\begin{cases}
1 & \text{se }7\mid m,\\
0 & \text{se }7\nmid m.
\end{cases}[/math]
Vediamo perché questa identità funziona.
Se [math]m[/math] è divisibile per 7, tutte le potenze [math]\omega^{jm}[/math] sono uguali a 1 e la somma vale 7. Se invece [math]m[/math] non è divisibile per 7, abbiamo una somma geometrica di potenze di una radice dell’unità diversa da 1, che si annulla.
In altre parole, questa somma permette di distinguere gli esponenti divisibili per 7 da tutti gli altri.
Possiamo quindi applicare il filtro direttamente al polinomio generatore e ottenere il numero cercato:
[math]\displaystyle N=\frac{1}{7}\sum_{j=0}^{6}P(\omega^j).[/math]
Il vantaggio di questa rappresentazione è che non dobbiamo sviluppare completamente il polinomio [math]P(x)[/math], operazione che diventerebbe rapidamente onerosa all’aumentare del numero degli elementi.
Calcoliamo i valori del polinomio
Cominciamo dal termine corrispondente a [math]j=0[/math]. Poiché [math]\omega^0=1[/math], otteniamo:
[math]\displaystyle P(1)=\prod_{k=1}^{7}(1+1)=2^7=128.[/math]
Consideriamo ora i valori con [math]j=1,\ldots,6[/math].
Possiamo separare il fattore relativo al numero 7:
[math]\displaystyle P(\omega^j)
=(1+\omega^{7j})
\prod_{k=1}^{6}(1+\omega^{jk}).[/math]
Dato che [math]\omega^7=1[/math], il primo fattore è uguale a 2:
[math]\displaystyle P(\omega^j)
=2\prod_{k=1}^{6}(1+\omega^{jk}).[/math]
Poiché 7 è primo e [math]j[/math] non è divisibile per 7, la moltiplicazione per [math]j[/math] modulo 7 permuta tutte le classi non nulle.
Di conseguenza, i numeri:
[math]\displaystyle \omega^j,\omega^{2j},\ldots,\omega^{6j}[/math]
sono esattamente le sei radici settime diverse da 1, semplicemente disposte in un ordine differente.
Per calcolare il prodotto utilizziamo il polinomio ciclotomico:
[math]\displaystyle \Phi_7(x)=1+x+x^2+\cdots+x^6.[/math]
Questo polinomio ha come radici proprio le sei radici settime non banali dell’unità. Possiamo quindi scriverlo nella forma:
[math]\displaystyle \Phi_7(x)=\prod_{k=1}^{6}(x-\omega^k).[/math]
Valutandolo in [math]x=-1[/math], otteniamo:
[math]\displaystyle \Phi_7(-1)=1-1+1-1+1-1+1=1.[/math]
D’altra parte, utilizzando la rappresentazione come prodotto:
[math]\displaystyle \Phi_7(-1)
=\prod_{k=1}^{6}(-1-\omega^k).[/math]
Ogni fattore contiene un segno negativo e, poiché i fattori sono sei, il segno complessivo è positivo. Pertanto:
[math]\displaystyle \prod_{k=1}^{6}(1+\omega^k)=1.[/math]
La stessa identità vale quando le radici vengono semplicemente riordinate, quindi:
[math]\displaystyle \prod_{k=1}^{6}(1+\omega^{jk})=1.[/math]
Ne consegue che:
[math]\displaystyle P(\omega^j)=2[/math]
per ciascuno dei sei valori non nulli di [math]j[/math].
Sostituendo tutti i risultati nella formula del filtro:
[math]\displaystyle N=\frac{1}{7}(128+6\cdot2).[/math]
Otteniamo:
[math]\displaystyle N=\frac{140}{7}[/math]
e quindi:
[math]\displaystyle \boxed{N=20}.[/math]
Il risultato coincide con quello ottenuto attraverso il conteggio combinatorio.
La dimostrazione algebrica è più articolata, ma offre un vantaggio importante: permette di passare dal singolo esempio a una formula generale. Le radici dell’unità non vengono introdotte per complicare il problema, bensì perché consentono di isolare una determinata classe di resto senza dover calcolare separatamente tutte le somme possibili.
Cinque esercizi di approfondimento risolti e commentati
Gli esercizi seguenti modificano progressivamente le condizioni del problema iniziale. In alcuni casi basterà riconoscere una simmetria, mentre in altri sarà necessario utilizzare il principio del complemento oppure estendere il ragionamento a un insieme parametrico.
Esercizio 1 – Sottoinsiemi con somma congrua a un resto assegnato
Sia:
[math]\displaystyle S=\{1,2,3,4,5,6,7\}.[/math]
Quanti sottoinsiemi [math]A\subseteq S[/math], compreso quello vuoto, soddisfano:
[math]\displaystyle \sum_{a\in A}a\equiv3\pmod7?[/math]
Soluzione
Nel problema iniziale cercavamo i sottoinsiemi con somma congrua a zero. Adesso il resto richiesto è 3, ma possiamo utilizzare una proprietà di simmetria delle classi di resto modulo un numero primo.
Consideriamo la trasformazione che associa a ogni elemento la sua classe moltiplicata per un numero [math]r[/math]:
[math]\displaystyle f_r(x)=rx\pmod7,[/math]
dove:
[math]\displaystyle r\in\{1,2,3,4,5,6\}.[/math]
Poiché 7 è primo, ogni elemento non nullo di [math]\mathbb Z_7[/math] possiede un inverso moltiplicativo. La moltiplicazione per [math]r[/math], quindi, permuta tutte le classi di resto modulo 7.
Per rendere concreta questa corrispondenza, ricordiamo che gli elementi di [math]S[/math] rappresentano esattamente le sette classi:
[math]\displaystyle \mathbb Z_7=\{0,1,2,3,4,5,6\},[/math]
con la classe zero rappresentata dal numero 7.
La trasformazione induce pertanto una corrispondenza biunivoca tra i sottoinsiemi di [math]S[/math]: a ogni sottoinsieme associamo quello ottenuto moltiplicando ciascun elemento per [math]r[/math] modulo 7 e sostituendo il risultato con il suo rappresentante in [math]S[/math].
La somma dei nuovi elementi è congrua a [math]r[/math] volte la somma iniziale.
Di conseguenza, la trasformazione associa i sottoinsiemi con resto [math]s[/math] a quelli con resto [math]rs[/math].
Per [math]s\neq0[/math], scegliendo opportunamente [math]r[/math], possiamo trasformare qualsiasi resto non nullo in un altro resto non nullo. Tutti i sei resti diversi da zero hanno quindi lo stesso numero di sottoinsiemi.
Indichiamo con [math]N_0[/math] il numero dei sottoinsiemi con somma divisibile per 7 e con [math]N_r[/math] il numero dei sottoinsiemi con un determinato resto non nullo [math]r[/math].
Dal problema originale sappiamo che:
[math]\displaystyle N_0=20.[/math]
Poiché il numero complessivo dei sottoinsiemi è 128, abbiamo:
[math]\displaystyle 20+6N_r=128.[/math]
Da cui:
[math]\displaystyle 6N_r=108[/math]
e infine:
[math]\displaystyle \boxed{N_r=18}.[/math]
Il numero dei sottoinsiemi con somma congrua a 3 modulo 7 è dunque:
[math]\displaystyle \boxed{18}.[/math]
Commento
La distribuzione uniforme dei sei resti non nulli non dipende semplicemente dal fatto che l’insieme contenga sette elementi. La proprietà decisiva è che gli elementi rappresentino tutte le classi di resto modulo 7 e che il modulo sia primo, così da garantire l’invertibilità della moltiplicazione per ogni classe non nulla.
Questa distinzione è importante quando si passa a moduli composti, per i quali la stessa argomentazione non può essere applicata automaticamente.
Esercizio 2 – Somma divisibile per 7 e cardinalità esattamente 3
Sia:
[math]\displaystyle S=\{1,2,3,4,5,6,7\}.[/math]
Determiniamo tutti i sottoinsiemi [math]A\subseteq S[/math] che soddisfano contemporaneamente:
[math]\displaystyle |A|=3[/math]
e:
[math]\displaystyle \sum_{a\in A}a\equiv0\pmod7.[/math]
Soluzione
Questa volta dobbiamo considerare soltanto i sottoinsiemi contenenti esattamente tre elementi. La somma minima di tre numeri distinti appartenenti a [math]S[/math] è:
[math]\displaystyle 1+2+3=6,[/math]
mentre quella massima è:
[math]\displaystyle 5+6+7=18.[/math]
I multipli di 7 compresi tra 6 e 18 sono soltanto:
[math]\displaystyle 7,\qquad14.[/math]
Possiamo quindi distinguere due casi.
Somma uguale a 7
Cerchiamo tre numeri distinti tali che:
[math]\displaystyle a+b+c=7.[/math]
Con la condizione [math]1\leq a<b<c\leq7[/math], l’unica possibilità è:
[math]\displaystyle 1+2+4=7.[/math]
Otteniamo il sottoinsieme:
[math]\displaystyle A_1=\{1,2,4\}.[/math]
Somma uguale a 14
Cerchiamo ora le terne di elementi distinti la cui somma è 14. L’unica possibilità senza il numero 7 è:
[math]\displaystyle 3+5+6=14.[/math]
Otteniamo:
[math]\displaystyle A_2=\{3,5,6\}.[/math]
Dobbiamo però considerare anche le terne che contengono il numero 7. In questo caso, gli altri due elementi devono avere una somma divisibile per 7. Le possibilità sono:
[math]\displaystyle 1+6=7,\qquad
2+5=7,\qquad
3+4=7.[/math]
Otteniamo quindi altri tre sottoinsiemi:
[math]\displaystyle \{1,6,7\},\qquad
\{2,5,7\},\qquad
\{3,4,7\}.[/math]
Raccogliendo tutte le soluzioni:
[math]\displaystyle \begin{aligned}
A_1&=\{1,2,4\},\\
A_2&=\{3,5,6\},\\
A_3&=\{1,6,7\},\\
A_4&=\{2,5,7\},\\
A_5&=\{3,4,7\}.
\end{aligned}[/math]
Il numero di sottoinsiemi richiesti è:
[math]\displaystyle \boxed{5}.[/math]
Commento
La condizione sulla cardinalità restringe il problema alle combinazioni di tre elementi. Invece di esaminare tutte le:
[math]\displaystyle \binom{7}{3}=35[/math]
terne possibili, abbiamo individuato prima i valori che la somma poteva assumere e successivamente cercato le combinazioni corrispondenti.
È una strategia particolarmente utile quando il numero degli elementi è limitato e la cardinalità richiesta permette di stabilire un intervallo ristretto per le somme.
Esercizio 3 – Sottoinsiemi con somma divisibile per 7 e cardinalità pari
Sia:
[math]\displaystyle S=\{1,2,3,4,5,6,7\}.[/math]
Quanti sottoinsiemi [math]A\subseteq S[/math] soddisfano contemporaneamente:
[math]\displaystyle \sum_{a\in A}a\equiv0\pmod7[/math]
e:
[math]\displaystyle |A|\equiv0\pmod2?[/math]
Vogliamo quindi contare i sottoinsiemi con somma divisibile per 7 e con un numero pari di elementi, compreso lo zero.
Soluzione
Dal problema iniziale sappiamo che i sottoinsiemi con somma divisibile per 7 sono complessivamente 20. Per stabilire quanti di questi hanno cardinalità pari, possiamo costruire una corrispondenza tra i sottoinsiemi validi di cardinalità pari e quelli di cardinalità dispari.
Consideriamo un sottoinsieme valido [math]A[/math] e definiamo:
[math]\displaystyle f(A)=A\triangle\{7\},[/math]
dove il simbolo [math]\triangle[/math] indica la differenza simmetrica tra insiemi. In pratica, se il numero 7 non appartiene ad [math]A[/math], lo aggiungiamo; se invece appartiene già ad [math]A[/math], lo eliminiamo.
Questa operazione conserva la divisibilità della somma, perché aggiungere o togliere 7 non modifica il resto modulo 7:
[math]\displaystyle \sum_{a\in f(A)}a
\equiv
\sum_{a\in A}a
\pmod7.[/math]
La cardinalità, invece, cambia sempre di una unità. Un sottoinsieme con un numero pari di elementi viene trasformato in uno con un numero dispari di elementi e viceversa.
Inoltre, applicando due volte la trasformazione si ritorna al sottoinsieme iniziale:
[math]\displaystyle f(f(A))=A.[/math]
Abbiamo quindi una corrispondenza biunivoca tra le due categorie di sottoinsiemi validi.
Poiché il loro numero complessivo è 20, metà ha cardinalità pari e metà cardinalità dispari:
[math]\displaystyle N_{\text{pari}}=N_{\text{dispari}}.[/math]
Pertanto:
[math]\displaystyle 2N_{\text{pari}}=20[/math]
e otteniamo:
[math]\displaystyle \boxed{N_{\text{pari}}=10}.[/math]
Commento
Questa dimostrazione è interessante perché non richiede di contare separatamente i sottoinsiemi con cardinalità pari. È sufficiente individuare un elemento congruo a zero rispetto al modulo considerato: aggiungendolo oppure eliminandolo si conserva la proprietà relativa alla somma, mentre cambia la parità della cardinalità.
Il ragionamento può essere riutilizzato anche in altri problemi di conteggio nei quali sia presente un elemento che non modifica la condizione aritmetica richiesta.
Esercizio 4 – Generalizzazione a un numero primo qualsiasi
Sia [math]p[/math] un numero primo dispari e consideriamo l’insieme:
[math]\displaystyle S_p=\{1,2,\ldots,p\}.[/math]
Determiniamo il numero di sottoinsiemi [math]A\subseteq S_p[/math], compreso quello vuoto, che soddisfano:
[math]\displaystyle \sum_{a\in A}a\equiv0\pmod p.[/math]
Soluzione
Il numero complessivo dei sottoinsiemi di [math]S_p[/math] è:
[math]\displaystyle 2^p.[/math]
Come nel problema iniziale, osserviamo che:
[math]\displaystyle p\equiv0\pmod p.[/math]
Possiamo quindi separare il numero [math]p[/math] dagli altri elementi e considerare:
[math]\displaystyle T_p=\{1,2,\ldots,p-1\}.[/math]
A ogni sottoinsieme di [math]T_p[/math] corrispondono due sottoinsiemi di [math]S_p[/math], uno che non contiene [math]p[/math] e uno che lo contiene. Poiché l’aggiunta di [math]p[/math] non modifica il resto della somma modulo [math]p[/math], possiamo scrivere:
[math]\displaystyle N(S_p)=2N(T_p).[/math]
Per ottenere una formula generale utilizziamo il filtro delle radici dell’unità.
Poniamo:
[math]\displaystyle \omega=e^{2\pi i/p}.[/math]
Il numero cercato può essere espresso direttamente attraverso il polinomio generatore:
[math]\displaystyle N(S_p)=
\frac{1}{p}
\sum_{j=0}^{p-1}
\prod_{k=1}^{p}(1+\omega^{jk}).[/math]
Per [math]j=0[/math], il prodotto vale:
[math]\displaystyle 2^p.[/math]
Consideriamo ora un valore [math]j[/math] compreso tra 1 e [math]p-1[/math]. Poiché [math]p[/math] è primo, la moltiplicazione per [math]j[/math] modulo [math]p[/math] permuta tutte le classi non nulle. Di conseguenza:
[math]\displaystyle \omega^j,\omega^{2j},\ldots,\omega^{(p-1)j}[/math]
sono tutte le radici [math]p[/math]-esime dell’unità diverse da 1.
Inoltre:
[math]\displaystyle 1+\omega^{jp}=2,[/math]
perché [math]\omega^p=1[/math].
Per calcolare il prodotto delle altre radici utilizziamo il polinomio ciclotomico:
[math]\displaystyle \Phi_p(x)=1+x+x^2+\cdots+x^{p-1}.[/math]
Essendo [math]p[/math] dispari, la valutazione in [math]x=-1[/math] fornisce:
[math]\displaystyle \Phi_p(-1)=1-1+1-\cdots+1=1.[/math]
D’altra parte, il polinomio può essere scritto come:
[math]\displaystyle \Phi_p(x)=\prod_{k=1}^{p-1}(x-\omega^k).[/math]
Sostituendo [math]x=-1[/math]:
[math]\displaystyle 1=\prod_{k=1}^{p-1}(-1-\omega^k).[/math]
Poiché [math]p-1[/math] è pari, i segni negativi si compensano e otteniamo:
[math]\displaystyle \prod_{k=1}^{p-1}(1+\omega^k)=1.[/math]
La moltiplicazione per [math]j[/math] riordina semplicemente le radici, quindi la stessa identità vale per ogni [math]j\neq0[/math]:
[math]\displaystyle \prod_{k=1}^{p-1}(1+\omega^{jk})=1.[/math]
Ogni prodotto corrispondente a un valore non nullo di [math]j[/math] vale dunque 2, mentre quello relativo a [math]j=0[/math] vale [math]2^p[/math].
Nella formula iniziale abbiamo un termine pari a [math]2^p[/math] e altri [math]p-1[/math] termini pari a 2. Pertanto:
[math]\displaystyle N(S_p)=\frac{2^p+2(p-1)}{p}.[/math]
La formula generale è:
[math]\displaystyle \boxed{N(S_p)=\frac{2^p+2(p-1)}{p}}.[/math]
Verifichiamo la formula con un esempio
Poniamo [math]p=5[/math]. L’insieme diventa:
[math]\displaystyle S_5=\{1,2,3,4,5\}.[/math]
Applicando la formula:
[math]\displaystyle N(S_5)=\frac{2^5+2(5-1)}{5}[/math]
[math]\displaystyle =\frac{32+8}{5}[/math]
e quindi:
[math]\displaystyle \boxed{N(S_5)=8}.[/math]
Per [math]p=7[/math], invece, ritroviamo il problema iniziale:
[math]\displaystyle N(S_7)=\frac{2^7+2(7-1)}{7}
=\frac{140}{7}
=\boxed{20}.[/math]
Commento
La formula mostra che il numero dei sottoinsiemi con somma divisibile per [math]p[/math] è vicino a [math]2^p/p[/math], ma non coincide esattamente con questa quantità.
La differenza è rappresentata dal termine:
[math]\displaystyle \frac{2(p-1)}{p}.[/math]
Questa correzione dipende dalla particolare struttura dell’insieme, che contiene una rappresentazione di ciascuna classe di resto modulo [math]p[/math].
La primalità del modulo è essenziale per la dimostrazione, perché garantisce che ogni moltiplicazione per un elemento non nullo permuti tutte le classi non nulle. La formula non deve quindi essere applicata automaticamente ai moduli composti.
Esercizio 5 – Sottoinsiemi di cardinalità esattamente 4
Sia:
[math]\displaystyle S=\{1,2,3,4,5,6,7\}.[/math]
Determiniamo quanti sottoinsiemi [math]A\subseteq S[/math] soddisfano:
[math]\displaystyle |A|=4[/math]
e:
[math]\displaystyle \sum_{a\in A}a\equiv0\pmod7.[/math]
Risolviamo il problema utilizzando il principio del complemento.
Soluzione
La somma di tutti gli elementi di [math]S[/math] è:
[math]\displaystyle 1+2+3+4+5+6+7=28.[/math]
Poiché:
[math]\displaystyle 28\equiv0\pmod7,[/math]
la somma degli elementi di un sottoinsieme è divisibile per 7 se e solo se lo è anche quella del suo complementare.
Indichiamo con:
[math]\displaystyle B=S\setminus A[/math]
il complementare di [math]A[/math]. Poiché [math]A[/math] contiene quattro elementi, [math]B[/math] ne contiene tre.
Inoltre:
[math]\displaystyle \sum_{a\in A}a+\sum_{b\in B}b=28.[/math]
Passando alle congruenze modulo 7:
[math]\displaystyle \sum_{a\in A}a+\sum_{b\in B}b
\equiv0\pmod7.[/math]
Di conseguenza:
[math]\displaystyle \sum_{a\in A}a\equiv0\pmod7[/math]
se e solo se:
[math]\displaystyle \sum_{b\in B}b\equiv0\pmod7.[/math]
Abbiamo quindi una corrispondenza biunivoca tra i sottoinsiemi validi di quattro elementi e quelli validi di tre elementi.
Nell’esercizio precedente abbiamo già individuato tutti i sottoinsiemi di tre elementi con somma divisibile per 7:
[math]\displaystyle \{1,2,4\},[/math]
[math]\displaystyle \{3,5,6\},[/math]
[math]\displaystyle \{1,6,7\},[/math]
[math]\displaystyle \{2,5,7\},[/math]
[math]\displaystyle \{3,4,7\}.[/math]
Calcoliamo i rispettivi complementari:
| Sottoinsieme di 3 elementi | Complementare |
|---|---|
| [math]\{1,2,4\}[/math] | [math]\{3,5,6,7\}[/math] |
| [math]\{3,5,6\}[/math] | [math]\{1,2,4,7\}[/math] |
| [math]\{1,6,7\}[/math] | [math]\{2,3,4,5\}[/math] |
| [math]\{2,5,7\}[/math] | [math]\{1,3,4,6\}[/math] |
| [math]\{3,4,7\}[/math] | [math]\{1,2,5,6\}[/math] |
I cinque complementari hanno tutti somma divisibile per 7. Pertanto il numero dei sottoinsiemi richiesti è:
[math]\displaystyle \boxed{N=5}.[/math]
Commento
Il principio del complemento è particolarmente utile quando la somma di tutti gli elementi dell’insieme è divisibile per il modulo considerato.
Più in generale, se:
[math]\displaystyle \sum_{s\in S}s\equiv0\pmod m,[/math]
allora, per ogni sottoinsieme [math]A\subseteq S[/math], la condizione:
[math]\displaystyle \sum_{a\in A}a\equiv0\pmod m[/math]
è equivalente a:
[math]\displaystyle \sum_{b\in S\setminus A}b\equiv0\pmod m.[/math]
Questa proprietà permette di sostituire il conteggio dei sottoinsiemi di cardinalità [math]k[/math] con quello dei sottoinsiemi di cardinalità [math]n-k[/math], quando l’insieme di partenza contiene [math]n[/math] elementi.
Verifica complessiva dei risultati
Prima di concludere, possiamo controllare nuovamente il risultato principale classificando tutti i sottoinsiemi di [math]S[/math] in base alla loro cardinalità.
Ricordiamo che:
[math]\displaystyle S=\{1,2,3,4,5,6,7\}[/math]
e che la somma complessiva degli elementi è:
[math]\displaystyle 1+2+3+4+5+6+7=28.[/math]
Poiché 28 è divisibile per 7, un sottoinsieme ha somma divisibile per 7 se e solo se anche il suo complementare soddisfa la stessa condizione.
Possiamo quindi utilizzare i risultati già ottenuti per ricostruire il conteggio completo:
| Cardinalità | Numero di sottoinsiemi validi |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 3 |
| 3 | 5 |
| 4 | 5 |
| 5 | 3 |
| 6 | 1 |
| 7 | 1 |
| Totale | 20 |
La somma dei conteggi restituisce:
[math]\displaystyle 1+1+3+5+5+3+1+1=20.[/math]
Possiamo inoltre verificare la simmetria rispetto alla cardinalità:
[math]\displaystyle N_k=N_{7-k}.[/math]
Questo risultato non è casuale, ma deriva direttamente dal principio del complemento, perché la somma totale degli elementi è un multiplo di 7.
Raccogliamo anche i risultati dei cinque esercizi:
| Problema | Risultato |
|---|---|
| Somma congrua a 3 modulo 7 | 18 |
| Somma divisibile per 7, cardinalità 3 | 5 |
| Somma divisibile per 7, cardinalità pari | 10 |
| Sottoinsiemi di [math]\{1,\ldots,5\}[/math], somma divisibile per 5 | 8 |
| Somma divisibile per 7, cardinalità 4 | 5 |
I conteggi sono coerenti con le proprietà di simmetria e con le corrispondenze utilizzate nelle dimostrazioni.
Errori da evitare
Nei problemi che riguardano le somme dei sottoinsiemi modulo un numero intero è facile applicare una regola apparentemente ragionevole senza averne verificato le condizioni. Alcuni errori meritano quindi particolare attenzione.
Dividere automaticamente il numero totale dei sottoinsiemi per il modulo.
Il fatto che un insieme contenga [math]2^n[/math] sottoinsiemi non significa che questi siano distribuiti uniformemente tra le diverse classi di resto. Nel problema iniziale, ad esempio:
[math]\displaystyle \frac{128}{7}\notin\mathbb N.[/math]
La distribuzione uniforme, quando esiste, deve essere dimostrata attraverso una simmetria o un’altra proprietà matematica.
Dimenticare l’insieme vuoto.
L’insieme vuoto ha somma pari a zero:
[math]\displaystyle \sum_{a\in\varnothing}a=0.[/math]
Poiché zero è divisibile per qualsiasi intero non nullo, l’insieme vuoto deve essere incluso nel conteggio, salvo diversa indicazione del problema.
Confondere sottoinsiemi e combinazioni con ripetizione.
In un sottoinsieme ogni elemento può comparire al massimo una volta. Non possiamo quindi considerare espressioni come [math]\{1,1,5\}[/math], perché un elemento di un insieme non può essere ripetuto.
Applicare il principio del complemento senza verificarne le condizioni.
La proprietà secondo cui un sottoinsieme ha somma divisibile per [math]m[/math] se e solo se anche il suo complementare ha somma divisibile per [math]m[/math] vale quando la somma totale degli elementi dell’insieme è multipla di [math]m[/math]. Senza questa condizione, la conclusione non è generalmente valida.
Estendere automaticamente ai moduli composti le proprietà dei numeri primi.
La moltiplicazione per una classe non nulla modulo un numero primo è sempre invertibile. Per un modulo composto, invece, possono esistere classi non nulle prive di inverso moltiplicativo, e la trasformazione non è necessariamente una permutazione di tutte le classi.
Formulario: gli strumenti matematici da ricordare
Raccogliamo le principali formule utilizzate nell’articolo, così da avere un riferimento sintetico quando si affrontano problemi analoghi.
Numero totale dei sottoinsiemi
Per un insieme con [math]n[/math] elementi:
[math]\displaystyle \boxed{2^n}.[/math]
Congruenza modulo [math]m[/math]
La scrittura:
[math]\displaystyle a\equiv b\pmod m[/math]
significa che [math]a-b[/math] è divisibile per [math]m[/math].
Numero di sottoinsiemi con cardinalità [math]k[/math]
Per un insieme di [math]n[/math] elementi, il numero di sottoinsiemi contenenti esattamente [math]k[/math] elementi è:
[math]\displaystyle \boxed{\binom nk=\frac{n!}{k!(n-k)!}}.[/math]
Principio del complemento
Se la somma totale degli elementi è divisibile per [math]m[/math], allora:
[math]\displaystyle \boxed{
\sum_{a\in A}a\equiv0\pmod m
\iff
\sum_{b\in S\setminus A}b\equiv0\pmod m
}.[/math]
Funzione generatrice delle somme dei sottoinsiemi
Per un insieme di elementi [math]a_1,a_2,\ldots,a_n[/math]:
[math]\displaystyle \boxed{
P(x)=\prod_{k=1}^{n}(1+x^{a_k})
}.[/math]
Il coefficiente di [math]x^s[/math] indica quanti sottoinsiemi hanno somma esattamente uguale a [math]s[/math].
Formula per gli insiemi [math]\{1,\ldots,p\}[/math]
Se [math]p[/math] è un numero primo dispari, il numero dei sottoinsiemi con somma divisibile per [math]p[/math], compreso quello vuoto, è:
[math]\displaystyle \boxed{
N=\frac{2^p+2(p-1)}{p}
}.[/math]
Dalla combinatoria all’aritmetica modulare
Il problema iniziale chiedeva di contare i sottoinsiemi di un insieme di sette elementi la cui somma fosse divisibile per 7. La risposta è 20, ma il valore numerico rappresenta soltanto il punto di partenza di un ragionamento più ampio.
Abbiamo visto come il principio moltiplicativo permetta di calcolare il numero totale dei sottoinsiemi, mentre le congruenze consentono di studiare le somme senza doverne conoscere ogni volta il valore esatto. Le corrispondenze biunivoche hanno permesso di sfruttare le simmetrie, il principio del complemento ha ridotto alcuni conteggi e le funzioni generatrici hanno fornito una rappresentazione algebrica capace di condurre a una formula generale.
Il passaggio più significativo è quello dalla soluzione particolare alla generalizzazione:
[math]\displaystyle \boxed{
N(S_p)=\frac{2^p+2(p-1)}{p}
}.[/math]
Una formula che nasce da un insieme molto piccolo e che, grazie alle proprietà delle classi di resto e delle radici dell’unità, si estende a tutti i numeri primi dispari.
È proprio questa la parte interessante del problema: riconoscere che dietro un conteggio apparentemente semplice si trovano relazioni tra strutture matematiche diverse, ciascuna delle quali offre un modo nuovo per affrontare la stessa domanda.
📚 Congruenze, aritmetica modulare e strumenti combinatori
Il conteggio dei sottoinsiemi con somma divisibile per 7 mette in relazione la combinatoria con l’aritmetica modulare. Per approfondire questi strumenti, affrontare nuove dimostrazioni e comprendere il ruolo delle funzioni generatrici, puoi proseguire con gli articoli seguenti:
- 👉Contare i sottoinsiemi modulo p: funzioni generatrici e radici dell’unità
Un approfondimento diretto sul conteggio dei sottoinsiemi attraverso le radici dell’unità e il filtro delle congruenze.
- 👉Equazioni diofantee e aritmetica modulare: come dimostrare l’assenza di soluzioni
Le congruenze diventano uno strumento per dimostrare che determinate equazioni non ammettono soluzioni intere.
- 👉Alla ricerca dei numeri primi: quando l’aritmetica modulare batte i tentativi
Un esempio di come scegliere il modulo opportuno possa trasformare una verifica numerica in una dimostrazione.
- 👉Cos’è il Principio dei Cassetti (o di Dirichlet)? Spiegazione ed esercizi svolti
Un principio fondamentale della combinatoria, utile per dimostrare l’esistenza di configurazioni con determinate proprietà.
- 👉Come dimostrare la divisibilità con l’aritmetica modulare: guida ed esercizi svolti
Una guida per utilizzare le classi di resto nelle dimostrazioni di divisibilità.
- 👉Funzioni generatrici: guida completa con esercizi risolti, Fibonacci e applicazioni
Per approfondire il legame tra coefficienti di un polinomio, successioni e problemi di conteggio.
- 👉Teoria dei numeri: congruenze, divisione e semplificazione
Le proprietà algebriche delle congruenze, con particolare attenzione alle condizioni che consentono di semplificare.
(6)
Altri articoli nella categoria "Calcolo combinatorio"
- Contare i sottoinsiemi modulo p: funzioni generatrici e radici dell’unità
- Formulario di probabilità: distribuzioni, variabili aleatorie e formule essenziali
- Teoria di Ramsey e R(3,3)=6: Dimostrazione, Grafo di K6 e Significato Combinatorio
- Cos’è la Teoria di Ramsey: Spiegazione, Esempi e il Teorema R(3,3)=6
- Funzioni Generatrici: Guida Completa con Esercizi Risolti, Fibonacci e Applicazioni
- Come Risolvere le Equazioni con i Fattoriali: Esercizi Svolti, Formule e Strategie
- Test di Calcolo Combinatorio: Esercizi Svolti sulle Permutazioni (Base e Avanzati)
- Combinazioni con Ripetizione: Test, Esercizi Svolti e Formule Spiegate
- Come Calcolare le Funzioni Suriettive: Guida Pratica con Inclusione-Esclusione e Numeri di Stirling
- Calcolo Combinatorio Pratico: 6 Esercizi Svolti dal Principio di Moltiplicazione ai Vincoli Complessi