[L06] E se una funzionale sta in TdN non può che essere...

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.

[L06] E se una funzionale sta in TdN non può che essere...

Messaggioda cip999 » 06/11/2015, 13:37

Ormai è quasi diventata una moda.

Determinare tutte le funzioni $f : \mathbb{Z}^+ \mapsto \mathbb{Z}^+$ tali che siano soddisfatte le seguenti condizioni:
(i) $f(n!) = f(n)!$ per ogni intero positivo $n$
(ii) $m - n \mid f(m) - f(n)$ per ogni coppia di interi positivi distinti $m$, $n$.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: [L06] E se una funzionale sta in TdN non può che essere.

Messaggioda Federico II » 06/11/2015, 19:35

Non è tanto difficile dai (solo formalizzarlo è un po' rognoso):
Testo nascosto:
Le uniche tre soluzioni sono le funzioni $f(n)=1\ \forall n\in\mathbb{Z^+}$, $f(n)=2\ \forall n\in\mathbb{Z^+}$ e $f(n)=n\ \forall n\in\mathbb{Z^+}$. Le prime due soddisfano le ipotesi perché $f(m)-f(n)=0$ per ogni $m,n\in\mathbb{Z^+}$ con $m\neq n$ e ogni intero divide $0$, e inoltre $f(n!)=1=f(n)!\ \forall n\in\mathbb{Z^+}$ nel primo caso, $f(n!)=2=f(n)!\ \forall n\in\mathbb{Z^+}$ nel secondo caso. La terza soddisfa perché $f(m)-f(n)=m-n$ e quindi $m-n\mid f(m)-f(n)$ per ogni $m,n\in\mathbb{Z^+}$ con $m\neq n$, e inoltre $f(n!)=n!=f(n)!\ \forall n\in\mathbb{Z^+}$. Dimostriamo che non ce ne sono altre. Osserviamo che la (ii) implica che per ogni $k\in\mathbb{Z^+}$ se $m\equiv n\pmod{k}$ con $m\neq n$ interi positivi allora $f(m)\equiv f(n)\pmod{k}$ perché $k\mid m-n\mid f(m)-f(n)$, ovvero $k\mid f(m)-f(n)$, cioè $f(m)\equiv f(n)\pmod{k}$. Ora dimostriamo che se $f(n)\leq2\ \forall n\in\mathbb{Z^+}$ allora $f$ è costante (e quindi è una delle prime due funzioni annunciate all'inizio). Notiamo che $f(6)=f(3!)=f(3)!=f(3)$, perché se $f(3)!=1$ allora $f(3)=1$, e se $f(3)!=2$ allora $f(3)=2$. Inoltre visto che l'immagine contiene solo $1$ e $2$ se due immagini hanno la stessa parità allora sono uguali. Per quanto abbiamo dimostrato, se $m\equiv n\pmod{2}$ (con $m\neq n$) allora $f(m)$ e $f(n)$ hanno la stessa parità, quindi sono uguali. Ne segue che tutti i numeri pari hanno la stessa immagine e lo stesso vale per i dispari. Però visto che $f(6)=f(3)$ tutti gli interi positivi hanno la stessa immagine, quindi $f$ è costante, come voluto. Possiamo quindi supporre che esista un intero positivo $a$ tale che $f(a)\geq3$. Allora $f(a)!$ è divisibile per $3$, quindi per la (i) si ha $3\mid f(a!)$. Osserviamo che $3\mid a!$, perché altrimenti si avrebbe $a=1$ oppure $a=2$, ma $f(1)=f(1!)=f(1)!$ e $f(2)=f(2!)=f(2)!$, quindi $f(a)=f(a)!$, ma per $f(a)\geq3$ (vero per la scelta di $a$) si ha $f(a)<f(a)!$, assurdo. Pertanto $3$ divide $a!$ e $f(a!)$. Allora $3$ deve dividere $f(3)$, perché $3\equiv0\equiv a!\pmod{3}$, quindi $f(3)\equiv3\equiv0\pmod{3}$. Dimostriamo allora che $f(3)=3$. Supponiamo per assurdo che $f(3)\neq3$, visto che $3\mid f(3)$ deve essere $f(3)\geq6$. Definiamo ora la successione $x_0,x_1,x_2,\ldots$ come $x_0=3$ e poi per ricorrenza $x_{n+1}=x_n!\ \forall n\in\mathbb{N}$. Si nota subito che la successione è strettamente crescente (vi compaiono solo termini maggiori o uguali a $3$ e quindi minori del proprio fattoriale). Dimostriamo che $x_j\leq f(x_{j-1})\ \forall j\in\mathbb{Z^+}$, per induzione su $j$. Il passo base ($j=1$) è vero perché $x_1=x_0!=3!=6\leq f(3)=f(x_0)$. Per il passo induttivo supponiamolo vero per un certo $j\in\mathbb{Z^+}$ e dimostriamolo per $j+1$. Osserviamo che $x_{j+1}=x_j!\leq f(x_{j-1})!=f(x_{j-1}!)=f(x_j)$, come voluto (si usano nell'ordine la definizione di $x_{j+1}$, l'ipotesi induttiva, la (i) e la definizione di $x_j$). Dimostriamo ora che $f(3)\geq x_l-3$ per ogni intero $l\geq2$. Notiamo che $f(x_l)=f(x_{l-1})=f(x_{l-1})!$, quindi visto che $x_l-3<x_l\leq f(x_{l-1})$ per quanto abbiamo dimostrato si ha $x_l-3\mid f(x_{l-1})!$ e quindi $x_l-3\mid f(x_l)$. Però visto che $3\equiv x_l\pmod{x_l-3}$ si ha $f(3)\equiv f(x_l)\pmod{x_l-3}$, ovvero $x_l-3\mid f(x_l)-f(3)$, ma visto che $x_l-3\mid f(x_l)$ deve essere $x_l-3\mid f(3)$, da cui $f(3)\geq x_l-3$, come volevamo. Visto che la successione $x_0,x_1,x_2,\ldots$ è strettamente crescente $x_l-3$ assume valori arbitrariamente grandi al crescere di $l$, assurdo per un intero positivo fisso. Supponendo $f(3)\neq3$ siamo così giunti ad un assurdo, quindi $f(3)=3$. Dimostriamo ora per induzione su $i$ che $f(x_i)=x_i\ \forall i\in\mathbb{N}$. Il passo base ($i=0$) è vero perché $f(x_0)=f(3)=3=x_0$. Per il passo induttivo supponiamolo vero per un certo $i\in\mathbb{N}$ e dimostriamolo per $i+1$. Abbiamo $f(x_{i+1})=f(x_i!)=f(x_i)!=x_i!=x_{i+1}$, come voluto (la terza uguaglianza segue dall'ipotesi induttiva). A questo punto passiamo a dimostrare che $f(n)=n\ \forall n\in\mathbb{Z^+}$. Sia $z$ un naturale tale che $x_z>n+max\{n,f(n)\}$ (esiste perché $x_0,x_1,x_2,\ldots$ è strettamente crescente). Allora per la (ii) si ha $x_z-n\mid f(x_z)-f(n)$ (abbiamo $x_z\neq n$ perché $x_z>n+max\{n,f(n)\}>n$), ma visto che $f(x_z)=x_z$ per quanto dimostrato prima deve essere $x_z-n\mid x_z-f(n)$, quindi $f(n)\equiv x_z\equiv x_z-(x_z-n)\equiv n\pmod{x_z-n}$. Da $x_z>n+max\{n,f(n)\}\geq n+f(n)$ si ottiene $x_z-n>f(n)$, e da $x_z>n+max\{n,f(n)\}\geq2n$ si ottiene $x_z-n>n$ Essendo quindi $f(n)$ e $n$ congrui modulo un intero maggiore di entrambi (cioè $x_z-n$) devono essere uguali, quindi $f(n)=n$. Questo conclude la dimostrazione.

Source?
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53

Re: [L06] E se una funzionale sta in TdN non può che essere.

Messaggioda cip999 » 06/11/2015, 21:19

No, difficile sicuramente no, più o meno l'ho trovato come la tua seconda f.c.d. (quella più recente). Poi il livello l'ho scelto più che altro in base alla provenienza (è il BMO 2012/4).

Comunque giusta ovviamente! :D
Però potevi risparmiarti parecchia roba ad esempio uccidendo il caso $f(3) \ge 6$ notando che se così fosse si avrebbe $5 = 6 - 1 \mid f(6) - f(1) = f(3)! - f(1)$, che è assurdo perché $5 \mid f(3)!$ ma $5 \nmid f(1)$.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: [L06] E se una funzionale sta in TdN non può che essere.

Messaggioda Federico II » 07/11/2015, 12:01

Sì non ci ho pensato avendo trovato subito la soluzione nel caso $f(3)=3$ credevo che quello fosse il caso facile e non potesse essere così banale... :roll:
Comunque ho scritto in stile dimostrativo per la valutazione della forma della dimostrazione.
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53


Torna a Teoria dei Numeri

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti