Funzione tale che $f(n)$ ha $n$ divisori

[dario2994]

Trovare tutte le funzioni $f:\mathbb{N}\to\mathbb{N}$ (dove $\mathbb{N}=\{1,2,3,\dots \}$) tali che:
$\forall n\in\mathbb{N}: f(n)$ ha esattamente $n$ divisori (positivi)
$\forall m,n\in\mathbb{N}: f(mn)\mid (m-1)n^{mn-1}f(m)$

p.s. un bel problema... molto olimpico

[Mist]

Si nota subito che $f(p) = p_\alpha ^{p-1}$, con $(p,p_\alpha ) \in \mathbb{P}^2$. Si considerino ora due numeri primi distinti $p$ e $q$. Si ha che $f(pq) \mid (q-1)f(p)q^{pq-1}$ e $f(pq) \mid (p-1)f(q) p^{pq-1}$ dove come prima $(p_\alpha , q_\alpha ) \in \mathbb{P}^2$. Si ha quindi che $f(pq) \mid f(p)f(q)(p-1)(q-1)(qp)^{pq-1}$ e si ha quindi che $f(pq) =f(p)f(q)$. Si ha quindi che $f(2)f(p) = f(2p) \mid p^{2p-1}f(2)$ e che quindi $f(p) \mid p^{2p-1}$ e che quindi $p_\alpha = p$. Per $f(p^n)$ si ha invece che $f(2p^n) \mid p^{2np^n-1}$ e che quindi $f(p^n)= p^{p^n-1}$. In conclusione quindi si ha che $$\displaystyle f\left( \prod_{\alpha =1}^{n}p_{\alpha}^{r_\alpha}\right) = \prod_{\alpha =1}^{n}p_{\alpha}^{p_{\alpha}^{r_\alpha}-1}$$

Sperem...

[dario2994]

$f(pq) \mid f(p)f(q)(p-1)(q-1)(qp)^{pq-1}$ e si ha quindi che $f(pq) =f(p)f(q)$

Non penso di aver colto questo passaggio...

[Mist]

Beh, non prendiamo nemmeno in considerazione i fattori (p-1) e (q-1) in quanto il numero dei loro fattori primi è incontrollabile. Ci restano solo quattro casi possibili oltre a quello in cui $f(pq) = f(p)f(q)$: $f(pq) =f(p)q^{q-1}$; $f(pq) = f(q)p^{p-1}$; $f(pq) = f(p)p^{q-1}$ e $f(pq) = f(q)q^{p-1}$. I primi due casi si dimostrano essere equivalenti a quello considerato sopra, mentre per gli altri due assumendo WLOG $p>q$ e notando che $f(p)p^{q-1}\nmid (p-1)f(p)q^{pq-1}$ si ottiene un assurdo. In effetti m'era sfuggita la questione...

[dario2994]

Beh, non prendiamo nemmeno in considerazione i fattori (p-1) e (q-1) in quanto il numero dei loro fattori primi è incontrollabile. Ci restano solo quattro casi possibili oltre a quello in cui $f(pq) = f(p)f(q)$: $f(pq) =f(p)q^{q-1}$; $f(pq) = f(q)p^{p-1}$; $f(pq) = f(p)p^{q-1}$ e $f(pq) = f(q)q^{p-1}$. I primi due casi si dimostrano essere equivalenti a quello considerato sopra, mentre per gli altri due assumendo WLOG $p>q$ e notando che $f(p)p^{q-1}\nmid (p-1)f(p)q^{pq-1}$ si ottiene un assurdo. In effetti m'era sfuggita la questione...

In effetti ti sfugge l'intera questione... devi trovare TUTTE le funzioni $f$ che rispettano le richieste... non solo quelle "belline"... non puoi dire "non prendo in considerazione": non sei tu a decidere, sono le ipotesi del problema e quelle non ti dicono che puoi scordarti di $p-1$ ad esempio

p.s. per farti capire... tutto quello che hai scritto finora in gara sarebbe valso 1 (forse 2) punto su 7...

[Sonner]

Bando alle ciance e caccia all'errore!

$f(2p)\mid p^{2p-1}f(2)$ e $f(2p)\mid (p-1)2^{2p-1}f(p)$. Chiaramente inoltre $f(2)=q$ con $q$ primo. Siccome $f(2p)$ deve avere esattamente $2p$ divisori dalla prima ricavo che $f(2p)=qp^{p-1}$. Passo alla seconda: $p\nmid (p-1)2^{2p-1} \rightarrow p\mid f(p)$. Siccome $p$ ha esattamente p divisori (e quindi è potenza $(p-1)$-esima si deve avere necessariamente $f(p)=p^{p-1}$ (si intende sempre p dispari), $f(p)=p^{2p-1}$ si esclude guardando la seconda equazione. Devo ancora scrivere degnamente $f(2)$. Si deve avere (dalla seconda) $f(2)\mid (p-1)2^{2p-1}$ per ogni $p$, quindi necessariamente $q=2$ (siccome p non è fissato ma varia tra i primi dispari, mentre q è ovviamente indipendente dalla scelta di p). Prendiamo infatti (ad esempio) $p=3$, allora si deve avere $q\mid 2^{2p} \rightarrow f(2)=2$.

A questo punto dimostro per induzione sull'esponente che $f(p^k)=p^{p^k-1}$.
$k=1$ c'è. $k\rightarrow k+1$: scrivo $f(p^{k+1})=f(p\cdot p^k)\mid(p-1)p^{p^{k+1}-1}f(p)=(p-1)p^{p^{k+1}-1}p^{p-1}$ da cui subito la tesi visto che $p-1$ non può avere $p$ divisori e per avere $p^{k+1}$ divisori posso prenderli solo a blocchi di $p$.

Infine dimostro per induzione sul numero di divisori primi che $n=\prod_{i=1}^m p_i^{\alpha_i}\rightarrow f(n)=\prod_{i=1}^m p_i^{p^{\alpha_i}-1}$.
$m=1$ c'è. $m\rightarrow m+1$: scrivo $f(n)\mid (p_2^{\alpha_2}\cdot\dots\cdot p_k^{\alpha_k}-1)p_1^{n-1}(p_2^{\alpha_2}\cdot\dots\cdot p_k^{\alpha_k})$ dove nell'ultimo pezzo ho usato l'ipotesi induttiva. Scrivo anche l'altra: $f(n)\mid (p_1^{\alpha_1}-1)(\frac{n}{p_1^{\alpha_1}})^{n-1}p_1^{p_1^{\alpha_1}-1}$. Se $p_1\nmid f(n)$ allora dalla prima posso prendere al più tutta l'ultima parentesi e ottenere $\frac{n}{p_1^{\alpha_1}}$ divisori, ma allora dalla seconda trovo che dovrei prendere i divisori mancanti dalla prima parentesi, impossibile perchè $p_1^{\alpha_1}-1$ è minore del numero di divisori richiesto. Visto che in effetti manca un pezzo (oltre a millemila typo), continuo domani

[dario2994]

Infine dimostro per induzione sul numero di divisori primi che $n=\prod_{i=1}^m p_i^{\alpha_i}\rightarrow f(n)=\prod_{i=1}^m p_i^{p^{\alpha_i}-1}$.
$m=1$ c'è. $m\rightarrow m+1$: scrivo $f(n)\mid (p_2^{\alpha_2}\cdot\dots\cdot p_k^{\alpha_k}-1)p_1^{n-1}(p_2^{\alpha_2}\cdot\dots\cdot p_k^{\alpha_k})$ dove nell'ultimo pezzo ho usato l'ipotesi induttiva. Scrivo anche l'altra: $f(n)\mid (p_1^{\alpha_1}-1)(\frac{n}{p_1^{\alpha_1}})^{n-1}p_1^{p_1^{\alpha_1}-1}$. Se $p_1\nmid f(n)$ allora dalla prima posso prendere al più tutta l'ultima parentesi e ottenere $\frac{n}{p_1^{\alpha_1}}$ divisori, ma allora dalla seconda trovo che dovrei prendere i divisori mancanti dalla prima parentesi, impossibile perchè $p_1^{\alpha_1}-1$ è minore del numero di divisori richiesto. Visto che in effetti manca un pezzo (oltre a millemila typo), continuo domani

Tutto quello che viene prima di questo è giusto e vale almeno 4 punti su 7... ora però concludi (e chiarisci cosa cavolo vuol dire questo perchè non si capisce proprio )

[bĕlcōlŏn]

Metto la mia soluzione.
Mostro che $f(2)=2$. Innanzitutto $f(2)$ ha 2 divisori, quindi $f(2)=p$ con $p$ primo. Ora se sostiuisco $m=2$ e $n=p$, si ha $f(2p)|p^{2p}$ e avendo $f(2p)$ $2p$ divisori deve essere necessariamente $f(2p)=p^{2p-1}$. Ora se sostituisco $m=p$ e $n=2$ ottengo $p^{2p-1}|(p-1)2^{2p-1}f(p)$. Se per assurdo $p\neq 2$, allora $p^{2p-1}|f(p)$ assurdo perché $f(p)$ avrebbe troppi divisori. Si mostra anche facilmente per induzione che $f(2^k)=2^{2^{k}-1}$.

D'ora in poi i primi saranno diversi da due
Mostro che $f(p^a)=p^{p^a-1}$, con $p\neq 2$. Sostituisco $m=2$ e $n=p^a$. Ottengo $f(2p^a)|2p^{a(2p^a-1)}$. A questo punto si presentano due casi: $f(2p^a)=p^{2p^a-1}$ oppure $f(2p^a)=2p^{p^a-1}$. Nel primo caso sostituisco $m=p^a$ e $n=2$. Si ha $p^{2p^a-1}|(p^a-1)2^{2p^a-1}f(p^a)$, da cui $p^{2p^a-1}|f(p^a)$, assurdo ancora una volta perché avrebbe troppi fattori. Dunque $f(2p^a)=2p^{p^a-1}$. A questo punto sostituendo $m=p^a$ e $n=2$ si ottiene $2p^{p^a-1}|(p^a-1)2^{2p^a-1}f(p^a)$, da cui $p^{p^a-1}|f(p^a)$. Ne segue che $f(p^a)=p^{p^a-1}$ perché se ci fosse un altro fattore, i divisori sarebbero troppi.

Ora voglio mostrare per induzione che vale anche sui prodotti di primi dispari. Suppongo che dati $n$ primi e degli esponenti, valga
$f\left(\displaystyle\prod_{i=1}^n p_i^{a_i}\right)=\displaystyle\prod_{i=1}^n p_i^{p_i^{a_i}-1}$

Mostro che $f\left(\displaystyle\prod_{i=1}^{n+1} p_i^{a_i}\right)=\displaystyle\prod_{i=1}^{n+1} p_i^{x_i}$, con $\displaystyle \prod (x_i+1)= \displaystyle\prod p_i^{a_i}$.
Innanzitutto pongo $m=2$ e $n=\displaystyle\prod_{i=1}^{n+1} p_i^{a_i}$, ottenendo che $f\left(2\displaystyle\prod_{i=1}^{n+1} p_i^{a_i}\right) | 2 \displaystyle\prod_{i=1}^{n+1} p_i^{a_i(2\prod_{i=1}^{n+1} p_i^{a_i}-1)}$.
(D'ora in poi quella produttoria la chiamo $P$). Quindi $f(2P)$ può avere fra suoi fattori solo i $p_i$ con $1\leq i \leq n+1$ e $2$. Suppongo che fra i suoi fattori non sia presente un certo $p_j$. Allora sostituisco $n=2p_j^{a_j}$ e $m=\dfrac{P}{p_j^{a_j}}$. Ottengo $f(2P)|\left(\dfrac{P}{p_j^{a_j}}-1\right) (2p_j)^{a_j(2P-1)}\displaystyle\prod_{i=1, i\neq j}^{n+1} p_i^{p_i^{a_i}-1}$ per ipotesi induttiva, da cui eliminando tutti i termini che sicuramente sappiamo che non ci sono in $f(2P)$ si ottiene $f(2P)|2\displaystyle\prod_{i=1, i\neq j}^{n+1} p_i^{p_i^{a_i}-1}$ assurdo perché i fattori sarebbero pochi.
Dunque ci stanno sempre tutti i $p_i$. Ora, se per assurdo fosse $f(2P)=\displaystyle\prod_{i=1}^{n+1} p_i^{x_i}$, sostituendo $m=P$ e $n=2$ si otterrebbe $\displaystyle\prod_{i=1}^{n+1} p_i^{x_1} | (P-1)2^{2P-1}f(P)$, ovvero $\displaystyle\prod_{i=1}^{n+1} p_i^{x_1} | f(P)$, ma così i divisori di $f(P)$ sarebbero troppi. Dunque $f(2P)=2\displaystyle\prod_{i=1}^{n+1} p_i^{x_i}$, con $\displaystyle\prod(x_i+1)=\displaystyle\prod_{i=1}^{n+1} p_i^{a_i}$. Allora sostituendo $m=P$ e $n=2$ si ottiene $f(P)=\displaystyle\prod_{i=1}^{n+1} p_i^{x_i}$.
A questo punto sostituisco $m=\displaystyle\prod_{i=1}^{n} p_i^{a_i}$ e poi $n=p_{n+1}^{a_{n+1}}$ e ottengo che tutti gli $x_1,x_2,...,x_n$ devono essere minori o uguali di $p_1^{a_1-1},...$. Ponendo poi $m=p_n^{a_n}$ e $n=\dfrac{\displaystyle\prod_{i=1}^{n} p_i^{a_i}}{p_n^{a_n}}$ ottengo che anche $x_{n+1}$ deve essere minore o uguale di $p_{n+1}^{a_{n+1}-1}$. Quindi è chiaro che ora quei minori sono tutti degli uguali, altrimenti il numero di divisori è minore di quello che dovrebbe essere, e quindi la tesi è mostrata anche per $n+1$.

Ora l'ho mostrato per le potenze di due e per il prodotto di primi dispari... non penso sia difficile ottenere il loro prodotto ma ora non ho voglia (e quello che ho scritto fino ad ora potrebbe avere pesanti errori xD)

[Sonner]

Ci riprovo, questo sostituisce l'ultimo paragrafo di sopra.

Per ogni $p_i$ che divide $n$ scrivo: $f(n)=f(p_in_i)\mid (p_i-1)n_i^{p_in_i-1}p_1^{p_i-1}$ (per un opportuno $n_i$) Supponiamo che esista un primo $r$ tale che $r\nmid n, r\mid f(n)$, allora deve valere $r\mid (p_i-1)n_i^{p_in_i-1}p_1^{p_i-1}$ per ogni $p_i$, quindi $r\mid p_i-1$. Se $p_1$ è il più piccolo primo che divide $n$ allora dovrei prendere questo $r$ almeno $r^{p_1-1}$ volte, altrimenti il numero di divisori di $f(n)$ non potrebbe essere $n$, siccome è divisibile per $r$. Questo però è ovviamente assurdo: $r^{p_1-1}>p_1-1$ e quindi non posso trovarne così tanti.
Quindi i primi che dividono $f(n)$ sono da scegliersi tra quelli che dividono $n$. Scrivo adesso $f(n)=f(p_i^{\alpha_i}n_i)\mid (p_i^{\alpha_i}-1)n_i^{p_i^{\alpha_i}n_i-1}p_i^{p^{\alpha_i}-1}$. Siccome $p_i\nmid n_i$, allora ogni primo può comparire al massimo $p^{\alpha_i}-1$ volte (altrimenti fallerebbe la divisibilità di sopra).
Ma allora da una parte ho che mi servono $n$ divisori da scegliersi tra i primi che dividono $n$ e dall'altra ho che, prendendo tutto quello che riesco (ossia scegliendo ogni $p_i$ esattamente ${p_i^{\alpha_i}-1}$ volte) ne ho esattamente $n$. L'unica funzione che soddisfa è quindi $f(n)=\prod_{i=1}^k p_i^{p^{\alpha_i}-1}$ con $n$ fattorizzato al solito modo.

[bĕlcōlŏn]

Dimostro quello che rimaneva. $f\left(2^k\displaystyle\prod_{i=1}^n p_i^{a_i}\right) = 2^{2^k-1}f(\displaystyle\prod_{i=1}^n p_i^{a_i}$. Per $k=1$ il risultato l'ho dimostrato nel precedente post. Lo faccio per induzione su $k$. Scelgo $m=2$, $n=2^k\left(\displaystyle\prod_{i=1}^n p_i\right)$, si ottiene che gli unici fattori in $f\left(2^{k+1}\displaystyle\prod_{i=1}^n p_i^{a_i}\right)$ possono essere i $2$ e i $p_i$. Ora sostituendo $m=2^{k+1}$ e $n=\displaystyle\prod_{i=1}^n p_i^{a_i}$ si ottiene che $v_2f\left(2^{k+1}\displaystyle\prod_{i=1}^n p_i^{a_i}\right) \leq 2^{k+1}-1$, ora sostituendo $m_i=p_i^{a_i}$ e $n_i=\dfrac{2^{k+1}\displaystyle\prod_{i=1}^n p_i^{a_i}}{p_i^{a_i}}$ per ogni $i$ si ottiene che $v_{p_i}f\left(2^{k+1}\displaystyle\prod_{i=1}^n p_i^{a_i}\right) \leq p_i^{a_i}-1$. Ora quei minori o uguale sono tutti uguali, altrimenti i divisori sarebbero pochi, e quindi risulta provato anche nel caso $k+1$.

[dario2994]

Quella di Sonner è perfetta
Quella di belcolon, sintetico come al solito, non ho avuto il cuore di leggerla Poi appena mi viene il coraggio edito almeno per dire che è giusta

p.s. tanto per gasarsi: questo qui a occhio poteva benissimo essere un IMO 2

[dario2994]

Senza troppa accuratezza ho letto quella di belcolon... mi sono fidato ciecamente nei passaggi in cui dici "sostituendo si ottiene" e ho trovato un solo robo che o non ho capito o è un errorino:

Quindi $f(2P)$ può avere fra suoi fattori solo i $p_i$ con $1\leq i \leq n+1$ e $2$. Suppongo che fra i suoi fattori non sia presente un certo $p_j$. Allora sostituisco $n=2p_j^{a_j}$ e $m=\dfrac{P}{p_j^{a_j}}$. Ottengo $f(2P)|\left(\dfrac{P}{p_j^{a_j}}-1\right) (2p_j)^{a_j(2P-1)}\displaystyle\prod_{i=1, i\neq j}^{n+1} p_i^{p_i^{a_i}-1}$ per ipotesi induttiva, da cui eliminando tutti i termini che sicuramente sappiamo che non ci sono in $f(2P)$ si ottiene $f(2P)|\displaystyle\prod_{i=1, i\neq j}^{n+1} p_i^{p_i^{a_i}-1}$ assurdo perché i fattori sarebbero pochi.

Ma $f(2P)$ può avere fattori 2, quindi non puoi eliminare come fai $\left(\dfrac{P}{p_j^{a_j}}-1\right)$ perchè potrebbe essere pieno di fattori 2 che ti danno i divisori mancanti (complimenti per il tuo latex comunque \dfrac non l'avevo mai letto e manco \neq)

[bĕlcōlŏn]

Sto facendo il caso con i primi dispari, quindi per la prima divisibilità $f(2P)$ può avere un solo fattore di $2$ che è comunque troppo poco. (Ho aggiunto il 2 che in effetti mancava prima della produttoria) Grazie per i complimenti!

[patatone]

dico come l'ho fatta io omettendo i dettagli perchè guardando le soluzioni già postate le idee sono più o meno le stesse:
1)dimostro che f(2)=2
2)dimostro che $f(p^a)=p^{p^a-1}$
3)trovo il valore di f(n) per n pari (che è quello che già sapete)
4)questo è il punto in cui la mia soluzione si discosta maggiormente:
dato n dispari ho che $f(2n)|2n^{2n-1}$ e $f(2n)|(n-1)2^{2n-1}f(n)$. Quindi in f(2n) compaiono solo fattori primi presenti in n più eventualmente un 2. Questi fattori primi non possono dividere nè n-1 nè $2^{2n-1}$ quindi devono dividere f(n), ma allora $f(2n)|2f(n)$. Se f(n) ha n divisori, 2f(n) ha massimo 2n divisori (si dimostra facilmente). Ma anche f(2n) ha 2n divisori quindi deve valere f(2n)=2f(n) e da questo ricavo i valori della funzione per n dispari visto che già conosco tutti quelli pari
5)chiudo il mio intervento inutile