Staffetta tdn

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
travelsga
Messaggi: 39
Iscritto il: 30 giu 2008, 13:40
Località: Carrara

Messaggio da travelsga »

Problema 31 (Austria 1973)
Si definisca $ g(k) $ il più grande divisore dispari di $ k $. Dimostrare che $ \displaystyle 0<\sum_{i=1}^n{\frac{g(i)}{i}}-\frac{2n}{3}<\frac{2}{3} $
Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd »

per n tendente ad infinito viene..
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn »

Poniamo $ \displaystyle~s(n)=\sum_{i=1}^n{\frac{g(i)}{i}} $. Osserviamo che $ \displaystyle~s(n) $ è una somma di inversi di potenze di 2. Troviamo prima una formula chiusa con $ \displaystyle~n=2^m $ e osserviamo che in $ \displaystyle~s(2^m) $ il termine $ \displaystyle~\frac{1}{2^i} $ si ripete $ \displaystyle~\frac{n}{2^{i+1}} $ volte se $ \displaystyle~0\le i<m $. Il termine $ \displaystyle~\frac{1}{2^m} $ compare solo una volta. Abbiamo dunque $ \displaystyle~s(n)=\sum_{i=0}^{m-1}\frac{n}{2^{i+1}}\cdot\frac{1}{2^i}+\frac{1}{2^m} $, cioè $ \displaystyle~s(n)=\frac{n}{2}\sum_{i=0}^{m-1}\frac{1}{4^i}+\frac{1}{2^m} $$ \displaystyle~=\frac{n}{2}\frac{1-\frac{1}{4^m}}{1-\frac{1}{4}}+\frac{1}{2^m} $$ \displaystyle~=\frac{2n}{3}-\frac{2n}{3\cdot4^m}+\frac{1}{2^m} $. Perciò $ \displaystyle~s(n)-\frac{2n}{3}=\frac{1}{2^m}(1-\frac{2}{3})=\frac{1}{3\cdot2^m} $ (che per inciso rispetta la tesi), da cui $ \displaystyle~3s(2^m)-2\cdot2^m=\frac{1}{2^m}>0. $
Ora per $ \displaystyle~n $ generico sappiamo che la sua scrittura polinomiale in base 2 è una somma di potenze di 2: consideriamo un insieme $ \displaystyle~T\subset\mathbb{N} $ che contiene gli esponenti di queste potenze. Dimostriamo dapprima $ \displaystyle~s(n)-\frac{2n}{3}<\frac{2}{3} $, cioè $ \displaystyle~3s(n)-2n<2 $. È evidente che $ \displaystyle~s(n)\le \sum_{i\in T}s(2^i) $ (dato che in $ \displaystyle~s(k+2^i)-s(k) $ ci sono al più $ \displaystyle~2^{i-1} $ 1, al più $ \displaystyle~2^{i-2} $ $ \displaystyle~\frac{1}{2} $, ...). Quindi $ \displaystyle~3s(n)-2n=3s(n)-2\sum_{i\in T}2^i $$ \displaystyle~\le 3\sum_{i\in T}s(2^i)-2\sum_{i\in T}2^i $$ \displaystyle~\le\sum_{i\in T}\frac{1}{2^i} $ (sommando le uguaglianze con le potenze di 2). Ma $ \displaystyle~\sum_{i\in T}\frac{1}{2^i}<\sum_{i\ge0}\frac{1}{2^i}=2 $, come volevasi dimostrare.
Per dimostrare $ \displaystyle~s(n)-\frac{2n}{3}>0 $, ovvero $ \displaystyle~3s(n)-2n>0 $, osserviamo che effettivamente $ \displaystyle~s(n)=\sum_{i\in T}s(2^i) $. Infatti $ \displaystyle~s(k\cdot2^t+2^t)-s(k\cdot2^t) $ (considerandola come una somma di inversi di potenze di 2) differisce da $ \displaystyle~s(2^t) $ al più per l'ultimo termine, ed è identica a $ \displaystyle~s(2^t) $ se $ \displaystyle~k $ è pari: infatti $ \displaystyle~\frac{g((k+1)2^t)}{(k+1)2^t}=\frac{1}{2^t}=\frac{g(2^t)}{2^t} $. Ordinando i termini di $ \displaystyle~T $ in ordine decrescente con la successione $ \displaystyle~\{a_i\}_{0\le i\le r} $, abbiamo che $ \displaystyle~s(n)=s(2^{a_0})+s(2^{a_0}+2^{a_1})-s(2^{a_0})+\ldots +s(2^{a_0}+2^{a_1} $$ \displaystyle~+\dots+2^{a_r})-s(2^{a_0}+2^{a_1}+\dots+2^{a_{r-1}}) $$ \displaystyle~=s(2^{a_0})+s(2^{a_1})+\dots+s(2^{a_r}) $ (dato che ogni termine è della forma $ \displaystyle~s(2\cdot2^{a_i}(2^{a_0-a_i-1}+\dots $$ \displaystyle~+2^{a_{i-1}-a_i-1})+2^{a_i})-s(2\cdot2^{a_i}(2^{a_0-a_i-1}+\dots+2^{a_{i-1}-a_i-1})) $). Quindi ora basta mostrare che $ \displaystyle~3\sum_{i\in T}s(2^i)-2\sum_{i\in T}2^i>0 $, ovvio ancora una volta sommando le disuguaglianze $ \displaystyle~3s(2^i)-2\cdot2^i>0 $.

Se non ci sono errori, dato che non frequenterò il forum per un po' e che adesso non ho idee, lascio a jordan :twisted: il piacere di porre il prossimo quesito (no, scherzo, a chi vuole). Ciau!
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
travelsga
Messaggi: 39
Iscritto il: 30 giu 2008, 13:40
Località: Carrara

Messaggio da travelsga »

Ok, tutto giusto :D

Chi prende il testimone?
ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 »

travelsga ha scritto:Ok, tutto giusto :D

Chi prende il testimone?
Mi è permesso?

Trovare per quali $ k $ l'equazione $ x^2+y^2+z^2=kxyz $ ha infinite soluzioni. $ (x,y,z,k $ interi)

Sinceramente ho la soluzione ma non la relativa dimostrazione, mi metto anche io all'opera (sperando che quest'ultima sia elementare :P ).

EDIT: trovata anche la dimostrazione, si puo' fare :wink:
ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 »

Vi potrei dare ancora un po' di tempo, ma dato che domani parto e non vorrei dimenticarmene, ecco il link alla soluzione:
http://www.math.uconn.edu/~kconrad/ross2007/descent.pdf
(pagina 7)
Avanti il prossimo!
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

Problema33.
Mostrare che se $ n \in \mathbb{N} $ è sufficientemente grande allora $ \upsilon_2((2x+1)^n+(2y+1)^n)<\ln(\ln(n)) $ per ogni $ (x,y) \in \mathbb{Z}^2 $ fissato tali che $ x+y \neq -1 $.

Ps. Aggiunta la parte in corsivo.
Ultima modifica di jordan il 02 ago 2009, 18:22, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.
Avatar utente
Febo
Messaggi: 47
Iscritto il: 20 set 2007, 15:08

Messaggio da Febo »

Mah, ho come la vaga impressione che manchi qualche ipotesi (del tipo $ (2x+1)+(2y+1)\neq 0 $) nel qual caso il problema è poco definito ma tendenzialmente falso...

Sennò, possiamo notare che per n dispari $ v_2((2x+1)^n+(2y+1)^n)=v_2((2x+1)+(2y+1)) $ che con la nostra ipoitesi aggiuntiva è una costante finita $ \mu _0 $ e quindi per $ n>e^{e^{\mu _0}} $ siamo felici.

Se invece n è pari, beh una somma di 2 quadrati dispari non è mai un multiplo di 4....

Rilancio con problemi dalle formulazioni più ragionevoli:

Sia $ c $ un intero positivo fissato. Siano $ a_i $ al variare di $ i $ tra gli interi positivi una sequenza di razionali tali che, per ogni n, $ \displaystyle\sum_{d|n} d\cdot a_d=c^n $

Si dimostri che tutti gli $ a_i $ sono interi.
Fondatore dell'associazione "Non uno di meno", per lo sterminio massiccio dei nani e affini.
Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd »

Febo ha scritto: Sia $ c $ un intero positivo fissato. Siano $ a_i $ al variare di $ i $ tra gli interi positivi una sequenza di razionali tali che, per ogni n, $ \displaystyle\sum_{d|n} d\cdot a_d=c^n $

Si dimostri che tutti gli $ a_i $ sono interi.
una pseudo-soluzione..

scopriamo che
$ a_1=c $
$ c^p=c+p*a_p $
per p primo
$ c^{pq}=c+p*a_p+q*a_q+pq*a_{pq}=c^p+c^q-c+pq*a_{pq} $
per p,q primi, e, di conseguenza,
$ pq*a_{pq}=c^{pq}-c^p-c^q+c $
se contininuiamo possiamo dire che, se $ \displaystile{b_1,b_2,..,b_s} $ sono i divisori primi di n presi con molteplicità, allora
$ n*a_n=c^n-\sum_{sym} c^{b_1b_2..b_{s-1}}+\sum_{sym} c^{b_1b_2..b_{s-2}}-... c $
dove a_n è intero grazie al piccolo teorema di fermat applicato sul RHS modulo $ \displaystile{b_i} $per ogni i compreso tra 1 e s..

so che c'è qualcosa che non va..
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

@ exodd: Uhm, l'idea sembra funzionare anche se non ho controllato i dettagli per pigrizia. Però c'è anche un'altra soluzione al problema (che ho postato io, visto che ormai è chiaro a tutti che scrivo anche a nome di Febo, quando mi sento in vena). Prova a definire $ a_n $ come il numero di collane con n perline di c colori di ordine n (considerate a meno di rotazioni). Di ordine n vuol dire che bisogna ruotarle di n volte per mandarle in sé stesse (cioè che non sono uguali a sé stesse ruotate, tranne nel caso banale). Per caso gli $ a_i $ rispettano le ipotesi? A questo punto dal fatto che gli $ a_i $ sono univocamente determinati dalle ipotesi del problema e che hanno ottimi motivi per essere interi, rappresentando una quantità di collane, segue la tesi.
"Sei la Barbara della situazione!" (Tap)
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

exodd ha scritto:[...] se contininuiamo possiamo dire che, se $ \displaystile{b_1,b_2,..,b_s} $ sono i divisori primi di n presi con molteplicità, allora
$ n*a_n=c^n-\sum_{sym} c^{b_1b_2..b_{s-1}}+\sum_{sym} c^{b_1b_2..b_{s-2}}-... c $
dove a_n è intero grazie al piccolo teorema di fermat applicato sul RHS modulo $ \displaystile{b_i} $per ogni i compreso tra 1 e s..
Il fatto della molteplicità come l'aggiusti? :roll:
Febo ha scritto: Sia $ c $ un intero positivo fissato. Siano $ a_i $ al variare di $ i $ tra gli interi positivi una sequenza di razionali tali che, per ogni n, $ \displaystyle\sum_{d|n} d\cdot a_d=c^n $.Si dimostri che tutti gli $ a_i $ sono interi.
Bella la tua soluzione, peccato che la conoscevo..ne provo con un altra più appropriata alla sezione: sia $ b_n:=na_n, u(n)=1, e_c(n)=c^n, \forall n \in \mathbb{N}_0 $ e $ \mu(\cdot) $ la funzione di Moebius, allora per ipotesi $ e_c=b * u $ dove $ * $ denota il prodotto di convoluzione. Grazie alla prima formula di inversione abbiamo $ b=e_c*\mu $. Sia $ p $ un divisore fissato di $ n $ e $ \upsilon_p(n):=k \in \mathbb{N}_0 $ e $ m:=\frac{n}{p^k} \in \mathbb{N}_0 $. Allora $ b_n=\sum_{d|n} \mu (d) c^{\frac {n}{d}} = \sum_{p\nmid d|n} \mu (d) c^{\frac {n}{d}} + \sum_{p|d|n} \mu (d) c^{\frac {n}{d}} $ $ = \sum_{p\nmid d|n} \mu (d)( c^{\frac {mp^k}{d}} - c^{\frac {mp^{k - 1}}{d}}) $, ma per il teorema di Eulero vale $ c^{\frac {mp^k}{d}}=c^{\frac {mp^{k - 1}}{d}} $ in $ \mathbb{Z}/p^k\mathbb{Z} $, che implica quindi $ n \mid b_n $ cioè $ a_n:=\frac{b_n}{n} $ è intero per ogni $ n \in \mathbb{N}_0 $.
The only goal of science is the honor of the human spirit.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

Problema35. Sia $ (a,b) \in (\mathbb{N}_0)^2 $ fissato tale che $ a^n+n \mid b^n+n $ per ogni $ n \in \mathbb{N} $. Mostrare che $ a=b $.
The only goal of science is the honor of the human spirit.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

Up! Dai che è molto facile..

Hint (per chi non volesse leggere non ingrandire): Quanti sono i primi distinti che possono dividere lhs?e di questi quanti sono tali che si possa "eliminare" l'esponente n?
The only goal of science is the honor of the human spirit.
Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra »

Soluzione del problema 35
Sia $ p\in\mathbb P : a,b<p $ e $ n=(a+1)(p-1)+1 $. Allora $ a^n+n \equiv a+n \equiv 0 \pmod p $. Quindi anche $ b^n+n \equiv b+n \equiv 0 \pmod p $. Ma allora $ a \equiv -n \equiv b \pmod p $ e dunque $ a=b $.

Problema 36
Dimostrare che se $ a,b\in\mathbb N^+ $ allora
$ \displaystyle \left( a+\frac12 \right)^n + \left( b+\frac12 \right)^n $
è un intero solo per un numero finito di interi positivi $ n $.
*** ELIMINATO DALLA STAFFETTA ***
Ultima modifica di FeddyStra il 05 set 2009, 18:36, modificato 1 volta in totale.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

E' un corollario del problema 33.. potresti cambiarlo?
The only goal of science is the honor of the human spirit.
Rispondi