Pagina 8 di 33

Inviato: 13 lug 2009, 15:56
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} $

Inviato: 15 lug 2009, 12:19
da exodd
per n tendente ad infinito viene..

Inviato: 16 lug 2009, 11:41
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!

Inviato: 16 lug 2009, 19:55
da travelsga
Ok, tutto giusto :D

Chi prende il testimone?

Inviato: 16 lug 2009, 20:46
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:

Inviato: 21 lug 2009, 12:04
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!

Inviato: 01 ago 2009, 21:09
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.

Inviato: 02 ago 2009, 12:33
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.

Inviato: 06 ago 2009, 22:36
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..

Inviato: 08 ago 2009, 18:20
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.

Inviato: 14 ago 2009, 20:07
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 $.

Inviato: 14 ago 2009, 20:51
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 $.

Inviato: 04 set 2009, 11:06
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?

Inviato: 05 set 2009, 11:10
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 ***

Inviato: 05 set 2009, 17:34
da jordan
E' un corollario del problema 33.. potresti cambiarlo?