Cose che wow

[Troleito br00tal]

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$.

[darkcrystal]

Quanto esplicita si può fare? In particolare, ti va bene

Testo nascosto:

$\displaystyle \frac{1}{n} \sum_{d|n, d \mbox{ dispari}} \varphi(d) \cdot 2^{\frac{nk}{d}}$

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.

[Troleito br00tal]

Di meglio non ho trovato :/

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

[darkcrystal]

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

[Gottinger95]

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).

[Drago96]

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...

[darkcrystal]

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.

[Gottinger95]

@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