Sequenza con somma di parti intere (BST 2007 ex 2)

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Sequenza con somma di parti intere (BST 2007 ex 2)

Messaggio da dario2994 » 07 gen 2010, 22:47

Per ogni $ $n\in\mathbb{N} $ definisco:
$ $a_n=\frac{1}{n}\left(\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor\right) $
Esistono infiniti n tali che $ $a_n>a_{n+1} $?
Esistono infiniti n tali che $ $a_{n+1}>a_n $?

Bonus question: Esistono infiniti n tali che $ $a_n=a_{n+1} $?



p.s. questo è proprio bello :P ma anche fattibile ;)
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 08 gen 2010, 02:09

Dal problema 24 della staffetta Tdn (ancora :o )
travelsga ha scritto:Lemma (1): $ \displaystyle\sum_{i=1}^n{\left\lfloor\frac{n}{i}\right\rfloor}=\sum_{i=1}^n{\tau(i)} $
Dim. lemma:
Procedo per induzione, suppongo vera la tesi al passo n e la dimostro per n+1: LHS nel passaggio da n ad n+1 incrementa di un'unità per ogni divisore di n+1,
pertanto aumenta di $ \tau(n+1) $, segue la tesi.
Dimostrazione:
(a). Per il lemma (1) posso riscrivere $ a_n>a_{n+1} $ come $ \displaystyle\frac{1}{n}\sum_{i=1}^n{\tau(i)}>\frac{1}{n+1}(\sum_{i=1}^n{\tau(i)}+\tau(n+1))\Longleftrightarrow\frac{1}{n}\sum_{i=1}^n{\tau(i)}>\tau(n+1) $ .
Ponendo $ n+1=p $ primo si ha $ LHS>(p-1)\tau(p)=2(p-1) $, ma $ LHS\ge 2(p-1)+1 $ per ogni $ p\ge 5 $ (in quanto $ \tau(n)\ge 2,\forall n>1 $), segue la tesi.
(b). Per ogni n chiamo $ X=\{1,\cdots,n\} $; sia $ j $ l'elemento di $ X $ che massimizza $ \tau(i) $ tale che $ \tau(h)<\tau(j) , \forall 1\le h\le j $.
Analogamente al punto precedente, occorre dimostrare che esistono infiniti n tali che $ \displaystyle\frac{1}{n}\sum_{i=1}^n{\tau(i)}<\tau(n+1)\Longleftrightarrow\frac{1}{n+1}\sum_{i=1}^{n+1}{\tau(i)}<\tau(n+1) $, ma dalla disuguaglianza $ AM\{b_i\}\le max\{b_i\} $ ho che $ AM\{\tau(i)\}=LHS<max\{\tau(i)\}=\tau(j) $ (vale in senso stretto poichè gli elementi della somma non sono tutti uguali),
basta quindi porre $ n+1=j $. Segue facilmente la tesi.
Spero che funzioni... (mi scuso inoltre se la soluzione appare un po' confusa, ma è stata scritta molto in fretta).
Riguardo la bonus question, non è difficile mostrare che $ a_n \sim \ln(n)+2\gamma-1+O(n^{-\frac{1}{2}}) $, dove $ \gamma $ è la constante di Eulero. Il vincolo richiesto è $ a_n=\sigma_0(n+1) \in \mathbb{Z} $ e almeno asintoticamente non riesco a ottenere alcuna contraddizione.. allora:
1) Sei in possesso di una soluzione costruttiva;
2) Hai messo la bonus question solo per farci(/mi) dannare;
3) Altro..
:?:
The only goal of science is the honor of the human spirit.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 08 gen 2010, 15:10

Premesso che ritengo veramente inutile postare soluzioni gia postate...
Bon la soluzione è ovviamente giusta.
Per la bonus question... avevo concluso una dimostrazione toppata e pure tanto :oops:
Quindi sì direi che ora sta lì aspettando che qualcuno ci si danni sopra xD
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 08 gen 2010, 16:13

Per una soluzione costruttiva servirebbe una descrizione quantitativa di $ \displaystyle s_n:=\sum_{1\le i\le n}{\sigma_0(i)} $ e anche solo la domanda (più debole) se esistono infiniti n tale che $ n \mid s_n $ non mi pare per nulla ovvia..
The only goal of science is the honor of the human spirit.

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 08 gen 2010, 17:15

jordan sei cattivo :evil:
Oggi a scuola ci ho pensato e l'ho risolto (certo come al solito la mia dimostrazione era molto più brutta, ma funzionava) e tu posti la soluzione!!!! Cosi non è giusto :(
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 08 gen 2010, 19:54

Waa sorry Maioc, era solo che una soluzione era già stata postata di recente e scritta abbastanza decentemente.. se poi la tua cambia qualcosa è sempre buono che la posti :o
The only goal of science is the honor of the human spirit.

abc
Messaggi: 16
Iscritto il: 18 apr 2009, 14:09

Messaggio da abc » 09 gen 2010, 18:52

Premesso che non avevo notato la relazione
travelsga ha scritto: $ \displaystyle\sum_{i=1}^n{\left\lfloor\frac{n}{i}\right\rfloor}=\sum_{i=1}^n{\tau(i)} $
e che avevo risolto solo la prima parte notando la facillima $ a_{2n} >a_n $.
comunque propongo una dimostrazione funny del lemma di travelsga: con un double counting :!:
$ \sum_{i=1}^n{\tau(i)} $ è la somma per ogni $ i $ del numero di divisori di $ i $. Questo conteggio posso anche farlo in un altro modo, cioè invece di partire da ogni numero i compreso in $ \{ 1, ..., n \} $ e vedere quanti divisori ha, posso partire da ogni numero k e vedere quante volte è divisore. Allora fissato k, esso è divisore di $ k, 2k, ... mk $, dove m è il max intero tale che $ mk\leq n $; cioè, per definizione di m, $ m=\left\lfloor\frac{n}{k}\right\rfloor $; cioè un numero k è multiplo di $ \left\lfloor\frac{n}{k}\right\rfloor $ numeri in $ \{ 1, ..., n \} $
Perciò otteniamo
$ \displaystyle\sum_{k=1}^n{\left\lfloor\frac{n}{k}\right\rfloor}= \sum_{k=1}^{n}{\mbox{n° di multipli di k minori di n}}=\sum_{i=1}^{n}{\mbox{n° di divisori di }i}=\sum_{i=1}^n{\tau(i)} $

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 10 gen 2010, 16:16

ecco anche la mia soluzione:
intanto noto che $ \displaystyle\sum_{i=1}^{n+1}\floor\frac {n+1} i=\sum_{i=1}^{n}\floor\frac {n} i+\tau (n+1) $ (uso $ \tau $ perchè l'ho visto nei post precedenti, quindi suppongo sia la notazione ufficiale).
Questo mi permette di calcolare ricorsivamente a_n, infatti
$ a_{n+1}=\frac{na_n+\tau (n+1)}{n+1} $. Ora le tesi diventano queste:

a)$ a_n>\tau (n+1) $ per infiniti n. Allora mi basta prendere n+1 primo e notare che ovviamente vale definitivamente $ a_n>2 $ (in realtà si può provare in modo semplice una cosa molto più forte, cioè che la serie diverge a $ +\infty $, ma a noi non interessa).

b)$ a_n<\tau (n+1) $ per infiniti n. In questo caso uso l'induzione: dimostro che se $ \tau (k)>1+\frac 1 2...+\frac 1 k>a_{k-1} $ allora $ \tau (2k)>1+\frac 1 2...+\frac 1{2k}>a_{2k-1} $. Questo basta a provare l'infinità.
Per k=6 (ad esempio, ma va bene qualsiasi altro k che funzioni come passo base) è vero.
Ora il passo induttivo:
$ \tau (2k)\ge \tau (k)+1 $.
Ma per ipotesi induttiva $ \tau (k)>1+\frac 1 2...+\frac 1 k $
Inoltre $ 1>\frac{k}{k+1}>\frac 1{k+1}+\frac 1{k+2}...+\frac 1{2k} $.
Sommo le precedenti e ho la tesi.
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

Rispondi