Siano $ a_1, ..., a_j $ interi positivi con $ a_1<...<a_j $ e $ a_{i+1} - a_i \geq 2\ \forall \ i \ \in \{1,...,j-1\} $. Sia $ S_j=\sum_{i=1}^{j}{a_i} $, dimostrare che c'è sempre almeno un quadrato perfetto nell'intervallo di interi $ [S_n, \ S_{n+1}-1] $ per ogni n intero positivo.
Che parta la caccia alla soluzione più breve!
Wow, c'è sempre un quadrato!
- Karl Zsigmondy
- Messaggi: 138
- Iscritto il: 09 lug 2011, 14:32
- Località: Città di Altrove, Kansas
Wow, c'è sempre un quadrato!
Ultima modifica di Karl Zsigmondy il 14 lug 2011, 11:27, modificato 1 volta in totale.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
"Life is very short and there's no time for fussing and fighting, my friend!"
- Karl Zsigmondy
- Messaggi: 138
- Iscritto il: 09 lug 2011, 14:32
- Località: Città di Altrove, Kansas
Re: Wow, c'è sempre un quadrato!
Dato che il problema è carino e neanche difficile, ecco un hint:
HINT1 (hintone)
Un altro paio di giorni e do il secondo hint se nessuno lo risolve, anche se non ci giurerei.
HINT1 (hintone)
Testo nascosto:
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
"Life is very short and there's no time for fussing and fighting, my friend!"
Re: Wow, c'è sempre un quadrato!
Ho due domande, non capisco bene il testo:
1)
2) Non capisco come definisci l'insieme S.. E' l'insieme degli $ S_n $ con $ 0<n<j+1 $ a cui aggiungo o tolgo 1 a quali?
Spero di essermi spiegato, scusa il disturbo!
1)
Intendevi dire $ S_n=\sum_{i=1}^{n}{a_i} $? Perchè nella sommatoria non vedo alcun i da far variare...Karl Zsigmondy ha scritto:Sia $ S_j=\sum_{i=1}^{j}{a_j} $, dimostrare...
2) Non capisco come definisci l'insieme S.. E' l'insieme degli $ S_n $ con $ 0<n<j+1 $ a cui aggiungo o tolgo 1 a quali?
Spero di essermi spiegato, scusa il disturbo!
- Karl Zsigmondy
- Messaggi: 138
- Iscritto il: 09 lug 2011, 14:32
- Località: Città di Altrove, Kansas
Re: Wow, c'è sempre un quadrato!
Ma quale disturbo, ora rendo il testo più chiaro e corrego quell'errore nella sommatoria.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
"Life is very short and there's no time for fussing and fighting, my friend!"
Re: Wow, c'è sempre un quadrato!
Beh ci provo così vedo se stavolta ho capito cosa chiede il problema! (e aggiungo che dopo aver sbagliato un paio di volte soluzione ho finalmente capito perchè l'hai postato in algebra e non in tdn.. )
Lo mostro per induzione su $ n $
Passo base: per $ n=2 $ funziona indipendentemente dalla scelta degli $ a_1 $, $ a_2 $
Sostengo che mi basta mostrare che, comunque preso un $ m $ a piacere, tra $ m $ e $ 2m $ estremi inclusi c'è almeno un quadrato! Infatti scelto un $ a_1 $ troverei un quadrato minore di $ 2a_1+1 $ ma il limite destro del mio intervallo vale $ a_1+a_{2}>2a_1+1 $ quindi avrei mostrato l'asserto.
Lo faccio ancora per induzione su $ m $:
Passo base: nell'intervallo [1;2] c'è un quadrato.
Passo induttivo: suppopngo che tra $ m $ e $ 2m $ ci sia un quadrato; possono succedere due cose:
1) questo quadrato è maggiore di $ m $: perfetto, allora anche tra $ m+1 $ e $ 2m+2 $ c'è un quadrato.
2) questo quadrato è proprio $ m $: considero allora il prossimo quadrato, che varrà $ m+2 \sqrt{m} +1 $ e mi piacerebbe che questo sia minore di $ 2m+2 $ ovvero voglio mostrare che $ 2 \sqrt{m}<m+1 $ ma in effetti è proprio così perchè (son tutte quantità positive, elevo al quadrato) $ 4m<m^2+2m+1 $ cioè $ (m-1)^2>0 $ vero $ \forall m $
Passo induttivo: Se tra $ S_{n-1} $ e $ S_{n} $ c'è almeno un quadrato (estremi inclusi) allora ce n'è almeno uno anche tra $ S_n $ e $ S_{n+1} $
Chiamo $ q^2 $ il più grande quadrato dell'intervallo $ [S_{n-1};S_n-1] $. Il prossimo quadrato non apparterrà perciò all'intervallo considerato ed in particolare voglio mostrare che apparterrà a $ [S_{n};S_{n+1}-1] $. Sappiamo che $ q^2 \leq S_n-1 $ e perciò $ (q+1)^2 \leq S_n +2 \sqrt{S_n-1} $ quindi se mostro che $ S_{n+1}-1 \geq S_n+2 \sqrt{S_n-1} $ avrei vinto perchè il quadrato successivo sta nell'intervallo cercato. Svolgo i conti:
$ 2 \sqrt{S_n-1} \leq S_{n+1}-S_n $
$ \displaystyle \sum_{i=1}^{n-1}a_i -1 \leq (\frac{a_{n+1}-1}{2})^2 $ Aggiungo da ambo i membri $ a_{n+1} $
$ \displaystyle \sum_{i=1}^{n}a_i -1 \leq ( \frac{a_{n+1}+1}{2})^2 $
Ora per mostrare quest'ultima disugualianza osservo che indipendentemente da $ n $, una volta scelto il valore di $ a_{n+1} $, la somma al LHS assume valore massimo quando vi si sommano tutti i numeri minori di $ a_{n+1} $ e con la sua stessa parità (così ottengo gli addendi più "grandi e numerosi" possibili). Allora ho due casi:
A) $ a_{n+1} $ è un numero pari: il massimo della sommatoria al LHS vale (somma primi $ \frac{a_{n+1}}{2} $ numeri pari) $ \frac{a_{n+1}^2+a_{n+1}}{4} \leq ( \frac{a_{n+1}+1}{2})^2 $= RHS
B) $ a_{n+1} $ è un numero dispari: il massimo della sommatoria al LHS vale (somma dei primi $ \frac{a_{n+1}+1}{2} $ numeri dispari) $ ( \frac{a_{n+1}+1}{2})^2 $ = RHS
In entrambi i casi quindi RHS > LHS e per quanto detto in precedenza questo prova la tesi.
Lo mostro per induzione su $ n $
Passo base: per $ n=2 $ funziona indipendentemente dalla scelta degli $ a_1 $, $ a_2 $
Sostengo che mi basta mostrare che, comunque preso un $ m $ a piacere, tra $ m $ e $ 2m $ estremi inclusi c'è almeno un quadrato! Infatti scelto un $ a_1 $ troverei un quadrato minore di $ 2a_1+1 $ ma il limite destro del mio intervallo vale $ a_1+a_{2}>2a_1+1 $ quindi avrei mostrato l'asserto.
Lo faccio ancora per induzione su $ m $:
Passo base: nell'intervallo [1;2] c'è un quadrato.
Passo induttivo: suppopngo che tra $ m $ e $ 2m $ ci sia un quadrato; possono succedere due cose:
1) questo quadrato è maggiore di $ m $: perfetto, allora anche tra $ m+1 $ e $ 2m+2 $ c'è un quadrato.
2) questo quadrato è proprio $ m $: considero allora il prossimo quadrato, che varrà $ m+2 \sqrt{m} +1 $ e mi piacerebbe che questo sia minore di $ 2m+2 $ ovvero voglio mostrare che $ 2 \sqrt{m}<m+1 $ ma in effetti è proprio così perchè (son tutte quantità positive, elevo al quadrato) $ 4m<m^2+2m+1 $ cioè $ (m-1)^2>0 $ vero $ \forall m $
Passo induttivo: Se tra $ S_{n-1} $ e $ S_{n} $ c'è almeno un quadrato (estremi inclusi) allora ce n'è almeno uno anche tra $ S_n $ e $ S_{n+1} $
Chiamo $ q^2 $ il più grande quadrato dell'intervallo $ [S_{n-1};S_n-1] $. Il prossimo quadrato non apparterrà perciò all'intervallo considerato ed in particolare voglio mostrare che apparterrà a $ [S_{n};S_{n+1}-1] $. Sappiamo che $ q^2 \leq S_n-1 $ e perciò $ (q+1)^2 \leq S_n +2 \sqrt{S_n-1} $ quindi se mostro che $ S_{n+1}-1 \geq S_n+2 \sqrt{S_n-1} $ avrei vinto perchè il quadrato successivo sta nell'intervallo cercato. Svolgo i conti:
$ 2 \sqrt{S_n-1} \leq S_{n+1}-S_n $
$ \displaystyle \sum_{i=1}^{n-1}a_i -1 \leq (\frac{a_{n+1}-1}{2})^2 $ Aggiungo da ambo i membri $ a_{n+1} $
$ \displaystyle \sum_{i=1}^{n}a_i -1 \leq ( \frac{a_{n+1}+1}{2})^2 $
Ora per mostrare quest'ultima disugualianza osservo che indipendentemente da $ n $, una volta scelto il valore di $ a_{n+1} $, la somma al LHS assume valore massimo quando vi si sommano tutti i numeri minori di $ a_{n+1} $ e con la sua stessa parità (così ottengo gli addendi più "grandi e numerosi" possibili). Allora ho due casi:
A) $ a_{n+1} $ è un numero pari: il massimo della sommatoria al LHS vale (somma primi $ \frac{a_{n+1}}{2} $ numeri pari) $ \frac{a_{n+1}^2+a_{n+1}}{4} \leq ( \frac{a_{n+1}+1}{2})^2 $= RHS
B) $ a_{n+1} $ è un numero dispari: il massimo della sommatoria al LHS vale (somma dei primi $ \frac{a_{n+1}+1}{2} $ numeri dispari) $ ( \frac{a_{n+1}+1}{2})^2 $ = RHS
In entrambi i casi quindi RHS > LHS e per quanto detto in precedenza questo prova la tesi.
- Karl Zsigmondy
- Messaggi: 138
- Iscritto il: 09 lug 2011, 14:32
- Località: Città di Altrove, Kansas
Re: Wow, c'è sempre un quadrato!
La dimostrazione è praticamente la mia, comunque per la cronaca era un USAMO1994/01.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
"Life is very short and there's no time for fussing and fighting, my friend!"