La funzionale che risolleverà il forum
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
La funzionale che risolleverà il forum
Own.
Sia $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ tale che $f(\phi(x))=\phi(f(x))$ per ogni $x \in \mathbb{Z}^+$ ($\phi$ è la funzione di Eulero). Determinare la più piccola costante $c$ tale che $f(x+1) \le 2x^c$ per ogni $x \in \mathbb{Z}^+$.
Sia $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ tale che $f(\phi(x))=\phi(f(x))$ per ogni $x \in \mathbb{Z}^+$ ($\phi$ è la funzione di Eulero). Determinare la più piccola costante $c$ tale che $f(x+1) \le 2x^c$ per ogni $x \in \mathbb{Z}^+$.
Re: La funzionale che risolleverà il forum
Dato che questa funzionale risolleverà il forum (o almeno dovrebbe) non la risolvo (anche perché non l'ho risolta) ma faccio delle osservazioni da cui altri potranno trarre spunto e risollevare il forum:
1. Sostituendo valori bassi ottengo che $f(1)=\phi(f(1))$, quindi $f(1)=1$, che deriva dal fatto che l'unico numero uguale alla sua $\phi$ è $1$.
2. So che $f$ non è univocamente determinata. Infatti, $f(x)\equiv1$ costantemente e $f(x)=x$ rispettano la condizione (basta sostituire).
3. Provando i numeri piccoli, ottengo che $f(2)\in\{1,2\}$, che $f(3)\in\{1,2,3,4,6\}$, che $f(4)\in\{1,2,3,4,6\}$... insomma, posso dire che:
\[f(x)\in\{y\mid \phi(y)<x\}\]
che è una scrittura carina che però non serve a niente, se non a dire che:
\[\max\{f(x+1)\}=\max\{y\mid \phi(y)\le x\}.\]
E poi boh...
EDIT: con $f(x)\in A$ intendo che tutti i valori raggiungibili da $f(x)$ sono nell'insieme $A$.
1. Sostituendo valori bassi ottengo che $f(1)=\phi(f(1))$, quindi $f(1)=1$, che deriva dal fatto che l'unico numero uguale alla sua $\phi$ è $1$.
2. So che $f$ non è univocamente determinata. Infatti, $f(x)\equiv1$ costantemente e $f(x)=x$ rispettano la condizione (basta sostituire).
3. Provando i numeri piccoli, ottengo che $f(2)\in\{1,2\}$, che $f(3)\in\{1,2,3,4,6\}$, che $f(4)\in\{1,2,3,4,6\}$... insomma, posso dire che:
\[f(x)\in\{y\mid \phi(y)<x\}\]
che è una scrittura carina che però non serve a niente, se non a dire che:
\[\max\{f(x+1)\}=\max\{y\mid \phi(y)\le x\}.\]
E poi boh...
EDIT: con $f(x)\in A$ intendo che tutti i valori raggiungibili da $f(x)$ sono nell'insieme $A$.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
-
- Messaggi: 169
- Iscritto il: 28 lug 2014, 10:01
- Località: Genova, Pisa
Re: La funzionale che risolleverà il forum
Io ieri sera avevo trovato una bella linea da seguire, però ho ancora dei buchi.. diciamo che con il tuo fatto 3 dovrei avere la soluzione.. come lo dimostri?
$ x^2 + (y - \sqrt {|x|} )^2 = 2 $
Re: La funzionale che risolleverà il forum
In mente l'idea ce l'ho, ma formalizzarla... comunque era falso (o meglio, non del tutto vero), quindi boh, faccio il mio lemma:
Lemma overpowered che serve (solo) ad erFuricksen. Siano definiti infiniti insiemi (disgiunti, ma chissene frega?) $A_n:=\{x\mid \phi(x)=n\}$ per tutti gli $n$ interi positivi. Allora $A_1=\{1,2\}$, $A_2=\{3,4,6\}$, $A_3=\emptyset$ etc. Cosa mi piace di questi insiemi? Che, in pratica il mio lemma è:
\[\max\{f(x)\}=\max\left\{\bigcup_{i=1}^{\phi(x)} A_i\right\},\]
che deriva dal fatto che:
\[f(x)\in\bigcup_{i=1}^{\phi(x)} A_i\hspace{1cm}(\star).\]
Ora quindi devo dimostrare $(\star)$ per avere il lemma. Considerazione: cos'è cambiato dall'osservazione 3 (falsa) al mio lemma (che ora dimostrerò vero?) Be', semplicemente la 3 aveva un $x-1$ che in realtà era una $\phi(x)$, dovuto al fatto che per i casi piccoli era vero...
Allora, induciamo estesamente. Passo base, per $2$ è banalmente vero (non posso farlo per $1$ perché ci sarebbe un'unione di nessun insieme...).
Passo induttivo, suppongo per tutti i numeri fino a $n-1$, in particolare per $\phi(n)$, $(\star)$ vera. Allora $f(m)=\phi(f(n))$. Ora dunque $f(\phi(n))$ può per ipotesi induttiva variare su tutti gli elementi di tutti gli insiemi $A_i$ per $i$ da $1$ a $\phi(n)$: quindi $f(n)$ può variare su tutti gli elementi $z$ con $\phi(z)\le\phi(n)$, che è proprio $(\star)$ per il numero $n$. Evvai! Ce l'ho fatta!
[_] (solito quadratino di "dimostrato!" che non so fare, \qed non va). Credo sia vero...
Lemma overpowered che serve (solo) ad erFuricksen. Siano definiti infiniti insiemi (disgiunti, ma chissene frega?) $A_n:=\{x\mid \phi(x)=n\}$ per tutti gli $n$ interi positivi. Allora $A_1=\{1,2\}$, $A_2=\{3,4,6\}$, $A_3=\emptyset$ etc. Cosa mi piace di questi insiemi? Che, in pratica il mio lemma è:
\[\max\{f(x)\}=\max\left\{\bigcup_{i=1}^{\phi(x)} A_i\right\},\]
che deriva dal fatto che:
\[f(x)\in\bigcup_{i=1}^{\phi(x)} A_i\hspace{1cm}(\star).\]
Ora quindi devo dimostrare $(\star)$ per avere il lemma. Considerazione: cos'è cambiato dall'osservazione 3 (falsa) al mio lemma (che ora dimostrerò vero?) Be', semplicemente la 3 aveva un $x-1$ che in realtà era una $\phi(x)$, dovuto al fatto che per i casi piccoli era vero...
Allora, induciamo estesamente. Passo base, per $2$ è banalmente vero (non posso farlo per $1$ perché ci sarebbe un'unione di nessun insieme...).
Passo induttivo, suppongo per tutti i numeri fino a $n-1$, in particolare per $\phi(n)$, $(\star)$ vera. Allora $f(m)=\phi(f(n))$. Ora dunque $f(\phi(n))$ può per ipotesi induttiva variare su tutti gli elementi di tutti gli insiemi $A_i$ per $i$ da $1$ a $\phi(n)$: quindi $f(n)$ può variare su tutti gli elementi $z$ con $\phi(z)\le\phi(n)$, che è proprio $(\star)$ per il numero $n$. Evvai! Ce l'ho fatta!
[_] (solito quadratino di "dimostrato!" che non so fare, \qed non va). Credo sia vero...
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
-
- Messaggi: 169
- Iscritto il: 28 lug 2014, 10:01
- Località: Genova, Pisa
Re: La funzionale che risolleverà il forum
Grazie mille!
Ora dovrebbe andare tutto, spero non ci siano errori:
Chiamiamo per comodità di scrittura
$$ \max\{f(x)\}=\max\left\{\bigcup_{i=1}^{\phi(x)} A_i\right\} = \alpha $$
Ovviamente $ f(x) \le \alpha $
e dalla definizione è evidente che $ \phi ( \alpha) \le \phi (x)$
Fatto importante: $ \phi (n) \ge \sqrt{{n \over 2}}$
Usando questo fatto ricaviamo che $ 2 (\phi (\alpha)) ^2 \ge \alpha $ da cui
$f(x) \le \alpha \le 2 (\phi (\alpha))^2 \le 2(\phi(\alpha))^2 \le 2(x-1)^2$ perciò $c=2$
Notiamo che $c$ non può essere minore perché se considero la valida relazione $f(3)=6$ ad esempio, vedo che $c=1$ non è accettabile
Ma per non lasciare nulla al caso, dimostriamo il fatto importante!
Vogliamo che $\phi (n) \ge \sqrt{{n \over 2}}$
che equivale a ${p_1}^{\alpha _1 -1} \cdot {p_2}^{\alpha _2 -1} ... {p_k}^{\alpha _k -1} (p_1 -1)(p_2 -1) ... (p_k - 1) \ge \sqrt{{n \over 2}}$
${p_1}^{2\alpha _1 -2} \cdot {p_2}^{2\alpha _2 -2} ... {p_k}^{2\alpha _k -2} (p_1 -1)^2(p_2 -1)^2 ... (p_k - 1)^2 \ge {n \over 2}$
$2{p_1}^{\alpha _1 -2} \cdot {p_2}^{\alpha _2 -2} ... {p_k}^{\alpha _k -2} (p_1 -1)^2(p_2 -1)^2 ... (p_k - 1)^2 \ge 1$
Ora, se $\alpha _i \ge 2$ non ci sono problemi, se invece $\alpha _i =1$ accoppiamo in questo modo:
${p_i}^{-1}(p_i -1)^2$ , e questa cosa è maggiore di 1 per ogni $p \ne 2$ , se invece ci fosse nella fattorizzazione $p=2$ allora sarebbe compensato dal 2 che compare all'inizio del prodotto... dovremmo esserci
Ora dovrebbe andare tutto, spero non ci siano errori:
Chiamiamo per comodità di scrittura
$$ \max\{f(x)\}=\max\left\{\bigcup_{i=1}^{\phi(x)} A_i\right\} = \alpha $$
Ovviamente $ f(x) \le \alpha $
e dalla definizione è evidente che $ \phi ( \alpha) \le \phi (x)$
Fatto importante: $ \phi (n) \ge \sqrt{{n \over 2}}$
Usando questo fatto ricaviamo che $ 2 (\phi (\alpha)) ^2 \ge \alpha $ da cui
$f(x) \le \alpha \le 2 (\phi (\alpha))^2 \le 2(\phi(\alpha))^2 \le 2(x-1)^2$ perciò $c=2$
Notiamo che $c$ non può essere minore perché se considero la valida relazione $f(3)=6$ ad esempio, vedo che $c=1$ non è accettabile
Ma per non lasciare nulla al caso, dimostriamo il fatto importante!
Vogliamo che $\phi (n) \ge \sqrt{{n \over 2}}$
che equivale a ${p_1}^{\alpha _1 -1} \cdot {p_2}^{\alpha _2 -1} ... {p_k}^{\alpha _k -1} (p_1 -1)(p_2 -1) ... (p_k - 1) \ge \sqrt{{n \over 2}}$
${p_1}^{2\alpha _1 -2} \cdot {p_2}^{2\alpha _2 -2} ... {p_k}^{2\alpha _k -2} (p_1 -1)^2(p_2 -1)^2 ... (p_k - 1)^2 \ge {n \over 2}$
$2{p_1}^{\alpha _1 -2} \cdot {p_2}^{\alpha _2 -2} ... {p_k}^{\alpha _k -2} (p_1 -1)^2(p_2 -1)^2 ... (p_k - 1)^2 \ge 1$
Ora, se $\alpha _i \ge 2$ non ci sono problemi, se invece $\alpha _i =1$ accoppiamo in questo modo:
${p_i}^{-1}(p_i -1)^2$ , e questa cosa è maggiore di 1 per ogni $p \ne 2$ , se invece ci fosse nella fattorizzazione $p=2$ allora sarebbe compensato dal 2 che compare all'inizio del prodotto... dovremmo esserci
Ultima modifica di erFuricksen il 02 giu 2015, 13:55, modificato 2 volte in totale.
$ x^2 + (y - \sqrt {|x|} )^2 = 2 $
Re: La funzionale che risolleverà il forum
Grande!!! Avevo congetturato fosse $c=2$, ma dimostrarlo... comunque c'è un typo nella dimostrazione del fatto importante: accorpi $p_i^{-1}(p_i)^2$ invece di $p_i^{-1}(p_i-1)^2$ però il resto è a posto... Adesso manca solo il punto (b): risollevare il forum...
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
-
- Messaggi: 169
- Iscritto il: 28 lug 2014, 10:01
- Località: Genova, Pisa
Re: La funzionale che risolleverà il forum
L'ho corretto!
Avevo già provato a dimostrare per induzione che $f(\phi (x)) < x$ ma non sono arrivato da nessuna parte, non avevo pensato a fare un'induzione sulle immagini della funzione!
Avevo già provato a dimostrare per induzione che $f(\phi (x)) < x$ ma non sono arrivato da nessuna parte, non avevo pensato a fare un'induzione sulle immagini della funzione!
$ x^2 + (y - \sqrt {|x|} )^2 = 2 $
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: La funzionale che risolleverà il forum
Non ho del tutto capito: perché?Talete ha scritto: Ora dunque $f(\phi(n))$ può per ipotesi induttiva variare su tutti gli elementi di tutti gli insiemi $A_i$ per $i$ da $1$ a $\phi(n)$: quindi $f(n)$ può variare su tutti gli elementi $z$ con $\phi(z)\le\phi(n)$.
@erFuricksen: quello che dici funziona, non sono troppo sicuro del Lemma. Ora prova con $c$ reale
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: La funzionale che risolleverà il forum
@Talete:
Ad esempio dal tuo ragionamento avrei che $f(2)=2$ va bene, come $f(4)=6$, ma allora non andrebbe bene $f(5)=18$ (difatti $\phi(18) > 4$). Però questi valori localmente soddisfano tutti i requisiti dell'ipotesi (e per me volendo si potrebbe costruire una funzione in cui questi valori funzionano...).
Comunque l'idea di lavorare sulle immagini è ottima, anche se mi sa che non ti basta il semplice bound formato da $A_1,...,A_{\phi(x)}$
Ad esempio dal tuo ragionamento avrei che $f(2)=2$ va bene, come $f(4)=6$, ma allora non andrebbe bene $f(5)=18$ (difatti $\phi(18) > 4$). Però questi valori localmente soddisfano tutti i requisiti dell'ipotesi (e per me volendo si potrebbe costruire una funzione in cui questi valori funzionano...).
Comunque l'idea di lavorare sulle immagini è ottima, anche se mi sa che non ti basta il semplice bound formato da $A_1,...,A_{\phi(x)}$
Re: La funzionale che risolleverà il forum
Sapevo del classico $\frac{1}{2}\sqrt{n}\le \varphi \left( n \right)\le n$ …ma anche $\varphi(2)=1$..
$\varphi(5186)=\varphi(5187)=\varphi(5188)$...
se c è reale non saprei…la sparo grossa, magari qualcosa simile al famoso $\frac{{{\pi }^{2}}}{6}$ ??
Sicuramente cancellerò post
$\varphi(5186)=\varphi(5187)=\varphi(5188)$...
se c è reale non saprei…la sparo grossa, magari qualcosa simile al famoso $\frac{{{\pi }^{2}}}{6}$ ??
Sicuramente cancellerò post
Re: La funzionale che risolleverà il forum
$f(3)=6$ non esclude $c=1$ perché la disuguaglianza del testo non è stretta. Anzi, visto che questo è uno dei casi in cui il rasoio di Occam funziona, non dovrebbe esserci molto mistero sul valore di $c$...
PS. dov'è l'own?!
PS. dov'è l'own?!
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: La funzionale che risolleverà il forum
Sono caduto in cespugli di ortiche più simpatici.<enigma> ha scritto: PS. dov'è l'own?!
Ok, tu conoscevi già l'esercizio, probabilmente qualcuno si sarà già posto questa domanda e, se era un matematico di professione, ci ha speculato e poi ci ha pubblicato. Magari c'ha pure un nome. E sticazzi, non ce lo metti?
Re: La funzionale che risolleverà il forum
No, non lo conoscevo, e non so da dove arrivi o se qualcuno ci abbia pubblicato qualcosa su. Per me un problema own è un problema molto difficile che richiede diverso tempo per essere risolto; visto che sul forum è durato la bellezza di un paio di giorni, o ho ragione io e oggettivamente non è own, o la definizione che uso è sbagliata. Ma visto che era un commento in calce a un'osservazione sul problema direi non valga la pena discettare su frivolezze come la definizione che ciascuno ha di problema "own".EvaristeG ha scritto:Ok, tu conoscevi già l'esercizio, probabilmente qualcuno si sarà già posto questa domanda e, se era un matematico di professione, ci ha speculato e poi ci ha pubblicato. Magari c'ha pure un nome. E sticazzi, non ce lo metti?
Per non uscire dal seminato, consiglio ai baldi solutori di mostrare che per ogni $\varepsilon,C>0$, si ha $\varphi(n)/n^{1-\varepsilon}>C$ per tutti gli $n$ abbastanza grandi.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: La funzionale che risolleverà il forum
"Own" vuol dire "proprio" e si riferisce alla provenienza. Se il problema lo ha inventato chi lo sta postando, di solito ci scrive own, per dire che non viene da gare, libri, siti e quindi potrebbe essere arduo involontariamente (avendo ad esempio il postante una soluzione errata) non essendoci alcuna fonte ufficiale da cui trarre la soluzione.
In quale modo contorto la parola "own" potrebbe entrarci con difficoltà e, peggio ancora, tempo medio di vita?
In quale modo contorto la parola "own" potrebbe entrarci con difficoltà e, peggio ancora, tempo medio di vita?
Re: La funzionale che risolleverà il forum
Devo ammettere che forse è che mi sono sempre autocensurato sui problemi che inventavo, evitando di postare quelli che mi prendessero meno di una settimana per essere risolti, e nella mia testa un problema con specificato "own" è per forza molto difficile mentre di per sé non è in effetti necessariamente così, sorry.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)