IMO Shortlist 2016 N2

[Stef2008]

Ciao, ho risolto questo problema che mi è sembrato carino... qualcuno magari può provare ed eventualmente chiedere qualche hint se è necessario.


Per ogni intero positivo $n$, indichiamo con $d(n)$ il numero dei divisori positivi di n, e con $d_1(n)$ il numero dei divisori positivi di $n$ che sono congrui ad $1$ modulo $3$.
Determinare, al variare di $n$, l’insieme dei valori interi assunti dalla frazione:
$\displaystyle \frac{d(10n)}{d_1(10n)}$

[TheMathSolver1]

Grazie per averlo pubblicato, in giornata ci provo, ma mi sa che ti chiederò un mano per adesso ci provo

[J23]

Testo nascosto:

WLOG: Nessun \( p \) riscrivibile nella forma \( 6h +1 \) divide \( n \). Infatti,

\[
\frac{{d(p^ax)}}{{d_1(p^ax)}} = \frac{{d(x)\cdot(a+1)}}{{d_1(x)\cdot (a+1)}} = \frac{{d(x)}}{{d_1(x)}}
\]

Pongo \( 10n = 3^kx \), dove \( x \) non è divisibile per nessun primo \( p \equiv 1 \mod 3 \), e \( 3 \nmid x \). In particolare, si ha

\[
\frac{{d(10n)}}{{d_1(10n)}} = \frac{{d(x)}}{{d_1(x)}}(k+1)
\]

Se \( x = p_1^{a_1}\cdot p_2^{a_2} \cdot \ldots \cdot p_m^{a_m} \), allora si consideri \( N_i = p_1^{a_1}\cdot p_2^{a_2} \cdot \ldots \cdot p_i^{a_i} \). Inoltre, sia \( d_2(n) \) il numero dei divisori positivi di \( n \) che sono congrui a \( 2 \) modulo \( 3 \), e \( \Delta(n) = d_1(n) - d_2(n) \). Si osservi che \( d_1(n) + d_2(n) = d(n) \) poiché \( 3 \nmid x \).

Lemma: \( d_1(N_{i+1}) = \lceil \frac{a_{i+1}+1}{2} \rceil d_1(N_i)+ \lfloor \frac{a_{i+1}+1}{2} \rfloor d_2(N_i) \) e \( d_2(N_{i+1}) = \lceil \frac{a_{i+1}+1}{2} \rceil d_2(N_i)+ \lfloor \frac{a_{i+1}+1}{2} \rfloor d_1(N_i) \).

[math]N_{i+1} = N_i \cdot p_{i+1}^{a_{i+1}} quindi per ogni divisore di \( N_i \) congruo a \( 1 \) modulo \( 3 \) si può ottenere un divisore di \( N_{i+1} \) congruo a \( 1 \) modulo \( 3 \) moltiplicandolo per \( p_{i+1}^\alpha \) dove \( 2\mid\alpha \) poiché \( p_{i+1}^\alpha \equiv 1 \mod 3 \) per il piccolo teorema di Fermat. Inoltre, si possono avere ulteriori divisori di \( N_{i+1} \) congrui a \( 1 \) modulo \( 3 \) moltiplicando un divisore di \( N_i \) congruo a \( 2 \) modulo \( 3 \) per \( p_{i+1}^\beta \) dove \( 2\nmid\beta \). Da ciò si giunge alla ricorsione presentata poiché i numeri pari, compreso lo zero, minori o uguali di \( a_{i+1} \) sono \( \lceil \frac{a_{i+1}+1}{2} \rceil \) e i numeri dispari sono \( \lfloor \frac{a_{i+1}+1}{2} \rfloor \). La seconda uguaglianza si dimostra in maniera analoga alla prima.

Sottraendo la seconda uguaglianza dalla prima e raccogliendo [math] \Delta(N_{i}) si trova che

\[
\Delta(N_{i+1}) = \Delta(N_{i})( \lceil \frac{a_{i+1}+1}{2} \rceil - \lfloor \frac{a_{i+1}+1}{2} \rfloor)
\]

Si noti che \( \Delta(N_i) = ( \lceil \frac{a_1 +1}{2} \rceil - \lfloor \frac{a_1+1}{2} \rfloor) \cdot \ldots \cdot ( \lceil \frac{a_i+1}{2} \rceil - \lfloor \frac{a_i+1}{2} \rfloor) \), da cui si può dedurre che \( \Delta(N_i) \) è \( 1 \) solamente se tutti gli esponenti dei primi nella fattorizzazione di \( N_i \) sono pari, ovvero se \( N_i \) è un quadrato, altrimenti è \( 0 \).

Caso \( \Delta(x) = 0 \):

\[
d_1(x) + d_2(x) = 2d_1(x) = d(x) \Longrightarrow \frac{d(x)}{d_1(x)}(k+1) = 2k +2
\]

Quindi \( \frac{d(10n)}{d_1(10n)} \) può assumere tutti gli interi positivi pari.

Caso \( \Delta(x) = 1 \):

\[
d_1(x) + d_2(x) = 2d_1(x) -1 = d(x) \Longrightarrow \frac{d(x)}{d_1(x)}(k+1) = \frac{2d(x)}{d(x)+1}(k+1)
\]

Dal momento che \( d(x) \) non è un primo poiché \( 10 \mid x \), e che \( \text{MCD}[d(x), d(x)+1] =1 \), allora \( d(x)+1 \mid 2(k+1) \), da cui si deduce che \( \frac{d(10n)}{d_1(10n)} \) può assumere anche valori dispari composti.

[Stef2008]

Bravo J23! La soluzione sembra corretta (i risultati finali sono giusti). C'era un modo molto semplice di calcolare $d_1(x)$ usando le funzioni generatrici.

[Stef2008]

Quando ho tempo la posto...

[Stef2008]

Eccola

Testo nascosto:

Consideriamo la scomposizione in fattori primi di $x$:
$x=3^Tp^{a_{1}}_1...p^{a_{n}}_nq^{b_{1}}_...1q^{b_{m}}_m$, con $p_i \equiv 1 \pmod{3}, q_i \equiv 2 \pmod{3}$. Allora i $p_i$, non influiscono con la classe di resto (rimane congrua a 1), 3 chiaramente non lo divide... quindi sono $ (a_1+1)...(a_n+1)f(q^{b_{1}}_1,...,q^{b_{m}}_m)$; dove $f(q^{b_{1}}_1,...,q^{b_{m}}_m)$ è il numero di divisori congrui a 1 di $q^{b_{1}}_1...q^{b_{m}}_m$. Ciò avviene se e solo se la somma degli esponenti è pari. Consideriamo il polinomio (funzione generatrice) $g(x) = (x^{b_1}+...+x+1)...(x^{b_m}+...+x+1)$. Ciascun termine del prodotto rappresenta un divisore (l'esponente della x del primo polinonio rappresenta il primo primo e così via). La somma dei coefficienti di grado pari è la quantità cercata e vale $f(q^{b_{1}}_1,...,q^{b_{m}}_m)=\frac{g(1)+g(-1)}{2}= \begin{cases} \frac{(b_1+1)...(b_m+1)}{2}, \text{se c'è un }b_i \text{ dispari} \\ \frac{(b_1+1)...(b_m+1)+1}{2}, \text{altrimenti}
\end{cases}$
Da qui si conclude facilmente ciò che ha ottenuto J23

Spero di non avere combinato casini con il $ \LaTeX$...

[J23]

La ricorsione che ho utilizzato può apparire un po' più complicata perchè non l'ho esposta adeguatamente. In ogni caso la tua dimostrazione è decisamente più veloce.