OliForum Matematico

Own (anche se di sicuro sarà noto, forse)

Dunoh

Siano $n$ e $k$ interi positivi. Sia $S= \{ 1;2;...;kn \}$. Sia $s(A)$ la somma degli elementi di un insieme $A$. Sia $esse(n;k)$ il numero di sottoinsiemi $S_i$ di $S$ tali che $n|s(S_i)$. Determinare $esse(n;k)$ in funzione di $n$ e $k$.

È difficile, ma è molto molto bello.

Edit: poniamo $s(\varnothing)=0$.

Quanto esplicita si può fare? In particolare, ti va bene o c'è un'espressione più carina? Questa è quella che si ottiene senza pensare, per cui sono pronto a crederti se mi dici che c'è di meglio.

Di meglio non ho trovato :/

Comunque per me se non hai mai visto niente di simile devi pensarci parecchio

Oh sì, assolutamente, ma come per tutte le cose una quantità sufficiente di tecnologia will get you far ^^

Provo con l'enorme hint postato da darkcrystal in un altro post, i.e. il filtro delle radici dell'unità sulle funzioni generatrici, che enuncio e dimostro qui
Filtro delle radici dell'unità. Sia \(A(x)= ogf(a_n)\), e sia \(k \in \mathbb{N}_{0}\). La somma
\[ \sum_{i=0}^{\infty} { a_{ki} } = a_0 + a_k + a_{2k} + a_{3k} +...\]
è data da
\[ \frac{1}{k} \sum_{i=0}^{k-1}{ A(\zeta^i)} = \frac{A(1)+ A(\zeta) + \ldots + A(\zeta^{k-1}) }{k}\]
dove \(\zeta\) è una radice \(k\)-esima primitiva dell'unità (ossia che non è radice \(d\)-esima per \(0 < d < n\) ).
Ricordiamo che, per \(m\) fissato, vale (a chi non fosse noto, è una geometrica, try it on your own ):
\[ \sum_{i=0}^{k-1}{ \zeta^{im} } = \begin{cases} k, & \mbox{ se } m \equiv 0 \pmod{k} \\ 0, & \mbox{ altrimenti} \end{cases} \]
Allora
\[ \frac{1}{k} \sum_{i=0}^{k-1}{ A(\zeta^i)} = \frac{1}{k} \sum_{i=0}^{k-1} \sum_{j=0}^{\infty} {a_j\zeta^{ij}} = \frac{1}{k}\sum_{j=0}^{\infty} a_j \sum_{i=0}^{k-1}{ \zeta^{ij} } = a_0 + a_k + a_{2k} + a_{3k} +...\]
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Siano:
1. \(f(x)\) la funzione generatrice che ha al coefficiente di \(x^j\) il numero di sottoinsiemi di \(S\) con somma \(j\);
2. \( \displaystyle p_k(x) = x^k-1 = \prod_{i=0}^{k-1} { (x-\zeta^i)} \), dove \(\zeta\) è una radice \(k\)-esima primitiva dell'unità.

Notiamo che \(f(x) = \prod_{i=1}^{kn} (1+x^i) \), perchè ogni scelta di un fattore all'interno delle parentesi corrisponde al "metto-o-non-metto-\(i\)-nel-mio-sottoinsieme". Armati del lemma, proviamo a calcolare \(S(n,k)\):
\[ S(n,k) = \frac{1}{n} \sum_{i=0}^n \prod_{j=1}^{kn} (1+ \zeta^{ij} ) = \frac{1}{n} \sum_{i=0}^n \left ( \prod_{j=1}^{n} (1+ \zeta^{ij} ) \right )^k\]
A questo punto, vogliamo tirar fuori dalla produttoria qualcosa che assomigli a \(p_n(x)\); in particolare, detto \(d_i= (i,n)\), nella produttoria compaiono proprio i fattori \(1+\zeta^{d_i}, 1+ \zeta^{2d_i}, \ldots, 1+ \zeta^n\) (radici \(n/d_i\)-esime dell'unità) in qualche ordine ripetuti \(d_i\) volte, perciò
\[ S(n,k) = \frac{1}{n} \sum_{i=0}^n \left ( \prod_{j=1}^{n} (1+ \zeta^{ij} ) \right )^k = \frac{1}{n} \sum_{i=0}^n \left ( (-1)^n \prod_{j=1}^{n} (-1- \zeta^{ij} ) \right )^{k} = \frac{1}{n} \sum_{i=0}^n (-1)^{nk} p_{n/d_i}(-1)^{kd_i} \]
Raggruppiamo \(p_{n/d_i}(-1)\): i numeri che hanno stesso \(d_i\) sono \(\varphi(n/d_i)\) e gli mcd possibili sono tutti i divisori di \(n\). Donc:
\[ S(n,k) = \frac{1}{n} \sum_{d \mid n} \varphi(n/d) (-1)^{nk} p_{n/d}(-1)^{kd} = \frac{1}{n} \sum_{d \mid n} \varphi(d) (-1)^{nk} p_{d}(-1)^{nk/d} = \frac{1}{n} \sum_{d \mid n} (-1)^{nk} \varphi(d) [(-1)^{d}-1 ]^{nk/d} = \]
\[ = \frac{1}{n} \sum_{d \mid n, \ \ d \mbox{ dispari}} (-1)^{nk} \varphi(d) ( -2 )^{nk/d} =\frac{1}{n} \sum_{d \mid n, \ \ d \mbox{ dispari}} \varphi(d) (-1)^{nk+nk/d} 2^{nk/d} = \frac{1}{n} \sum_{d \mid n, \ \ d \mbox{ dispari}} \varphi(d) 2^{nk/d} \]
che è il risultato "finale" (se non ce n'è di meglio, s'intende).

Boh, proviamo la strada con le generatrici suggerita da darkcrystal...
Per chi non ha mai visto soluzioni del genere, consiglio fortemente generatingfunctionology di Wilf.
Perché e cosa vogliono dire le funzioni che si usano? Brevemente, gli esponenti rappresentano gli elementi di un insieme, e facendo il prodotto di vari polinomi il coefficiente di $x^i$ ci dice in quanti modi possiamo ottenere $i$...

Step 1: sottoinsiemi. Bene, il primo passo è trovare la funzione su cui lavorare; per fare ciò, dobbiamo chiederci cos'è un sottoinsieme; la risposta è "una scelta di elementi", cioè per ogni elemento possiamo scegliere se prenderlo o no; al solito le possibili scelte sono i $+$, l'unione di tutte le possibilità e la $\times$. Alla fine arriviamo a definire la nostra funzione: $$\displaystyle f(x):=\prod_{i=1}^{kn}(1+x^i)=(1+x)(1+x^2)\cdots(1+x^{kn})$$
Step 2: multipli di $n$. Noi vorremmo sommare tutti e soli i coefficienti di $f(x)$ i cui esponenti sono multipli di $n$, che è la risposta al problema. Se volessimo trovare il polinomio che ha solo i termini pari, faremmo la cosa abbastanza nota $f_2(x)=\dfrac{f(x)+f(-x)}2$ perché i termini dispari si semplificano. Un discorso simile vale più in generale, a patto di estenderci ai complessi e considerare le radici dell'unità (si chiama infatti roots of unity filter). Detta $\displaystyle\zeta=e^{i\frac{2\pi}{n}}$, abbiamo che il polinomio che contiene solo termini con esponente multiplo di $n$ è $$f_n(x):=\dfrac{f(x)+f(x\zeta)+f(x\zeta^2)+\dots+f(x\zeta^{n-1})}{n}$$ consideriamo infatti il termine $a_mx^m$ in $f(x)$: se $n\mid m$, allora $\zeta^m=1$ per definizione praticamente, quindi $1+\zeta+\zeta^2+\dots+\zeta^{n-1}=n$; se invece $n\nmid m$, allora $\zeta^m\neq1$ e quindi possiamo usare la formula per le progressioni geometriche per dire $1+\zeta^k+\zeta^{2m}+\dots+\zeta^{(n-1)m}=\dfrac{\zeta^{nm}-1}{\zeta^m-1}=0$.
Noi poi vogliamo sapere la somma dei coefficienti, quindi valutiamo il polinomio in 1, e dunque la quantità da calcolare è
$$f_n(1)=\dfrac{f(1)+f(\zeta)+f(\zeta^2)+\dots+f(\zeta^{n-1})}{n}$$
Step 3: chi muore? Abbiamo dei prodotti con $1+\zeta^\text{roba}$; la prima cosa che viene in mente è che spesso fa 0 (-1 è una radice dell'unità parecchio ricorrente), quindi andiamo a vedere quando effettivamente $f(\zeta^m)=0$. Ma questo è abbastanza facile, perché $\displaystyle\zeta^m=e^{i\dfrac{2\pi}{\frac n m}}$; dunque se $2\mid\dfrac n m$, possiamo semplificare e otteniamo $\displaystyle\zeta^m=e^{i\frac{\pi}{h}}$, e quindi quando andiamo a calcolare $1+(\zeta^m)^h$ (che sicuramente c'è in quel produttone, anzi c'è almeno $k$ volte, ma vabbè) otteniamo $1+e^{i\pi}$ che il buon Eulero ci dice essere $0$. Ricapitolando, abbiamo ucciso tutti i termini del tipo $f(\zeta^m)$ con $2\mid\dfrac n m$.

Step 4: quanti superstiti? Bene, vediamo quanto sono simili i termini che ci sono rimasti. Per ogni $m$ chiamiamo $d_m=\gcd(n,m)$; quanti sono gli $m$ che hanno lo stesso $d_m$? Domanda nota, la risposta è $\varphi\left(\dfrac n {d_m}\right)$; infatti se $d_m$ è il massimo comun divisore, $m$ è della forma $d_m\cdot h$, ma dalla definizione di $d_m$ si ha $\gcd(\dfrac n {d_m},\dfrac m {d_m})=1$, inoltre $1\le h\le \dfrac n {d_m}$ e quindi abbiamo proprio la definizione della phi.
Step 4bis: quali superstiti? Cerchiamo di capire quanto valgono le varie $f(\zeta^m)$ che hanno lo stesso $d_m$; è ragionevole pensare che valgano la stessa quantità, dato che con le radici delle unità tutto va secondo divisori comuni. E lo fa per davvero, infatti $\displaystyle\zeta^m=e^{i\frac{2\pi}{\frac{n}{d_m}}\cdot\frac{m}{d_m}}$, ovvero $\zeta^m$ è diventata una radice $\dfrac{n}{d_m}$-esima primitiva (è elevata ad una cosa coprima), quindi le sue potenze sono tutte e sole le altre radici $\dfrac{n}{d_m}$-esime, fino alla potenza $\dfrac{n}{d_m}$-esima, poi si ripetono. Quindi abbiamo, detta $\xi=e^{i\frac{2\pi}{\frac{n}{d_m}}}$, che $f(\zeta^m)=\left((1+\xi)(1+\xi^2)\cdots(1+\xi^{\frac{n}{d_m}}) \right)^{k\cdot d_m}$; ma quel prodotto è qualcosa di abbastanza noto: immaginiamo di espanderlo, otteniamo $1+S+Q+\dots+\dots+P$, ovvero tutti i polinomi simmetrici valutati nelle varie potenze di $\xi$, che però essendo tutte e sole le radici di $x^\frac{n}{d_m}-1=0$ sono $0$; inoltre $P$ vale $1$, in quanto $\frac{n}{d_m}$ è dispari (quindi il termine noto è l'opposto del prodotto). Abbiamo dunque infine $f(\zeta^m)=2^{k\cdot d_m}$.

Step 5: tutto insieme. Non ci resta che riscrivere in modo compatto il tutto; quindi $$\displaystyle f_n(1)=\frac1 n\sum_{d\mid n, \frac n d \text{disp}}\varphi\left(\frac n d\right)\cdot 2^{kd}$$ che è quella scritta nello spoiler, solo con $d$ e $\frac n d$ scambiati...

EDIT: preceduto da Andrea, che ha scritto tutto in modo più compatto e anche più formale...

Ok, bravi entrambi! Ora almeno posso spiegare il mio primo post, che (mi sono reso conto a posteriori) non suonava tanto simpatico, ma era solo per dire che in realtà non avevo capito nulla di come funzionasse questo problema (anzi...), e che la soluzione si poteva trovare semplicemente a suon di conti.

Morale: le generatrici aiutano un sacco.

@Drago96: Dai che con due soluzioni dovrebbe esser chiaro a chi conosce poco l'argomento! Good job buddy
@darkcrystal: effettivamente, quando hai scritto che si faceva senza pensare e io per due settimane non sono riuscito a concludere, mi chiedevo quali oscure magie conoscessi! Poi quando hai postato le generatrici in the other post tutto fu più chiaro