162. Un problema che non vorresti ti capitasse in gara

[Troleito br00tal]

Ma anche nella vita.

$OWN$

Sia $S(n)=(1;2;...;n)$ e sia $f(x)$ una funzione $S(n) \rightarrow S(n)$ tale che $f^{(x)}(x)=x$ per ogni $x \in S$. Un elemento $y$ è detto generativo se per ogni $0<i<y$ allora $f^{(i)}(y) \neq y$. Sia $g(n)$ il massimo numero di elementi generativi in $S(n)$. E' vero che:
\begin{equation}
g(n) = \lfloor \sqrt{n} \rfloor
\end{equation}
?

N.B.: $f^{(1)}(x)=f(x);f^{(n+1)}(x)=f(f^{(n)}(x))$.

Non sapevo se fosse algebra o combinatoria, quindi l'ho postato qua (in realtà è teoria dei numeri).

[Gottinger95]

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.

[Troleito br00tal]

Mi sono fidato dei conti, ma esattamente come concludi?

[Gottinger95]

L'ho editato! Ma tu lo hai fatto in modo sostanzialmente diverso, senza inclusione-esclusione?

[Troleito br00tal]

Forse sarà perché mi sono svegliato un' ora fa e sto guardando diario di una nerd supestar, ma potresti spiegarmi il senso della produttoria iniziale? ^_^

[Gottinger95]

Della sommatoria? Ma ccierto mi rendo conto di averla piazzata lì senza troppe spiegazioni, e ciò è male
1. I numeri \(\le n\) divisibili per \(m\) sono in generale \(\left \lfloor \frac{n}{m} \right \rfloor \).
2. La sommatoria vuole calcolare la quantità di numeri divisibili per \(j\) ma non per \(j+1, \ldots, k\), che chiamiamo \(R_j\).
Chiamiamo \(A(x_1, \ldots, x_m)\) l'insieme dei numeri divisibili per \(x_1, \ldots, x_m\). Allora:
\( \displaystyle R_j = |A(j)| - | \bigcup_{i=j+1}^k{A(j,i)} |\)
3. Detto \(M_j = \{j+1, \ldots,k\}\), con l'inclusione-esclusione ci calcoliamo la cardinalità di quell'unione:
\(\displaystyle | \bigcup_{i=j+1}^k{A(j,i)} | = \sum_{m=1}^{k-j} (-1)^{m+1} \sum_{i_1, \ldots, i_m \in M_j } {|A(j,i_1, \ldots, i_m) |} \)
4. Mettendo tutto insieme ('ttenzione agli spostamenti dei - e al da dove partono le sommatorie):
\(\displaystyle R_j = |A(j)| - \sum_{m=1}^{k-j} (-1)^{m+1} \sum_{i_1, \ldots, i_m \in M_j } {|A(j,i_1, \ldots, i_m) |} =|A(j)| + \sum_{m=1}^{k-j} (-1)^{m} \sum_{i_1, \ldots, i_m \in M_j } {|A(j,i_1, \ldots, i_m) |} = \)
\(\displaystyle = \sum_{m=0}^{k-j} (-1)^{m} \sum_{i_1, \ldots, i_m \in M_j } {|A(j,i_1, \ldots, i_m) |} = \sum_{m=0}^{k-j} (-1)^{m} \sum_{i_1, \ldots, i_m \in M_j } {\left \lfloor \frac{n}{j \cdot i_1 \cdot \ldots \cdot i_m } \right \rfloor}\)

[Troleito br00tal]

Perché $|A(x;y)|=\lfloor \frac{n}{xy} \rfloor$? Non dovrebbe essere $=\lfloor \frac{n}{mcm(x;y)} \rfloor$? Prendi $n=8$ e $x=2;y=4$. Viene $A(2;4)$ formato da $4$ e da $8$ no?

[Gottinger95]

Oddio si, scusa! Per fortuna \(\frac{1}{lcm(x_1, \ldots, x_n)} \ge \frac{1}{x_1 \cdot \ldots \cdot x_n}\), perciò la dimostrazione fila ancora xD

[Troleito br00tal]

Sì ma quando fai inclusione esclusione alcuni segni cambiano no?

[Gottinger95]

Infatti ho detto una stronzata, ero tornato a cancellare le mie velleità xD Ci devo ripensare per bene; infatti mi pareva strano che avessi un margine così alto alla fine ( \(\ge k\) ) invece dell'auspicato \(\ge j\). Grazie di avermelo fatto notare, cercherò di aggiustarla.

[Troleito br00tal]

Grazie a te di averci provato nonostante l'avvertimento <3

[Gottinger95]

Ehm..hintino? Anche piccolino, dai

[Troleito br00tal]

No

[Gottinger95]

Guarda che te vengo sotto casa, so dove abiti

[Troleito br00tal]

SOTTO CASA TUTTO PASA