Ehi, bello bello!
Necessario.
Sia \(k\) il minimo tale che \(f^k(x) = x\). Visto che \(k \mid x\) (altrimenti col picchio che ritorno a \(x\) dopo \(x\) iterazioni), abbiamo \(gcd(x, f(x), \ldots, f^{k-1}(x) ) = k\). Allora \(f\) è una permutazione con cicli tali che la lunghezza di ogni ciclo divide tutti gli elementi del ciclo stesso.
Il numero di generativi è uguale al numero di cicli di lunghezza \(m\) che contengono \(m\). Affinchè ci siano \(m\) numeri divisibili per \(m\) (quelli che servono per comporre il ciclo), deve valere \(m^2 \le n\), i.e \(m \le \left \lfloor \sqrt{n} \right \rfloor\). Perciò \(g(n) \le \left \lfloor \sqrt{n} \right \rfloor\).
Costruzione.
Detto \(k= \left \lfloor \sqrt{n} \right \rfloor\), dimostriamo che effettivamente possiamo costruire \(k\) insiemi \(H_1, \ldots, H_k \subset S(n) \) disgiunti e tali che:
1. \(|H_i| = i\);
2. \(x \in H_i \Leftrightarrow i \mid x\);
3. \(i \in H_i\).
Per farlo, ci basta dimostrare che i numeri \(\le n\) divisibili per \(j\) ma non divisibili per \(j+1, \ldots, k\) sono almeno \(j\).
Per contarli, usiamo il principio di inclusione-esclusione( |divisibili per j| - |divisibili per j e un altro| + |divisibili per j e altri due| ... ) :
\(\displaystyle \sum_{m=0}^{k-j} \sum_{ i_1, \ldots, i_m \in M_j } { \left \lfloor \frac{(-1)^m n}{j i_1 \cdot \ldots \cdot i_m } \right \rfloor } \ge \sum_{m=0}^{k-j} \sum_{ i_1, \ldots, i_m \in M_j } {\frac{(-1)^m n}{j i_1 \cdot \ldots \cdot i_m } } - \sum_{m=0}^{k-j}{(-1)^m \binom{k-j}{m} } = \)
\( \displaystyle = \frac{n}{j} \left (\sum_{m=0}^{k-j} \sum_{ i_1, \ldots, i_m \in M_j } {\frac{(-1)^m}{i_1 \cdot \ldots \cdot i_m } } \right )= \frac{n}{j}\prod_{i=j+1}^k {1-\frac{1}{i} } = \frac{n}{j}\prod_{i=j+1}^k {\frac{i-1}{i} } = \frac{n}{j} \frac{j}{k} \ge k \)
Les jeux son faits, garçon! Spero che i passaggi siano chiari, in caso non esitate a chiedere
I passaggi più oscuri comunque li spiego brevemente:
1. Quando levo le parti intere, in pratica i -1 necessari per la maggiorazione si semplificano, usando \(\sum_{m=0}^n{(-1)^n \binom{n}{m} }=0\);
2. Quando la sommatoria di un botto di roba diventa una produttoria piccina picciò, è per le relazioni radici-coefficienti: entrambi i membri sono il polinomio con soluzioni \(\frac{1}{j+1}, \ldots, \frac{1}{k}\) calcolato in 1, LHS sviluppato, RHS no.
3. Quando la produttoria si semplifica, è una telescopica: i denominatori si semplificano con i numeratori del termine successivo.
EDIT:
A questo punto, immaginiamo di selezionare da \(S(n)\) gli insiemi \(H_1, \ldots, H_k\) (che sono i cicli della permutazione \(f(x)\), elementi fissi a parte ):
prima scegliamo \(k\) numeri divisibili per \(k\) (che è \(H_k\) ), poi \(k-1\) numeri divisibili per \(k-1\) che non abbiamo già scelto (ossia non divisibili per \(k\)), poi \(k-2\) numeri divisibili per \(k-2\) ma non per \(k,k-1\) ... Per ciò che abbiamo appena dimostrato, esistono sempre \(j\) numeri divisibili per \(j\) che "non abbiamo già scelto", ossia non divisibili per \(j+1, \ldots, k\). I numeri non selezionati alla fine di tutto li lasciamo fissi.
