Matematické Fórum

check_drummer · 30. 09. 2009 22:10

Ahoj,
pro n > 3 dokažte:
platí-li $\sum_{i=1}^{n}{a_i} >= n$ a $\sum_{i=1}^{n}{a_i^2} >= n^2$ , potom $max(a_i) >= 2$

musixx · 01. 10. 2009 13:03

Dle mého není $\sum_{i=1}^{n}{a_i} \geq n$ ani potřeba.

Implikace $\left(\sum_{i=1}^{n}{a_i^2} \geq n^2\right)\ \Longrightarrow\ \left(\max(a_i)\geq2\right)$ platí právě tehdy, když platí implikace $\left(\max(a_i)<2\right)\ \Longrightarrow\ \left(\sum_{i=1}^{n}{a_i^2}<n^2\right)$ . No a pro $\left(\max(a_i)<2\right)$ máme $\sum_{i=1}^{n}{a_i^2}<\sum_{i=1}^n2^2=4n\leq n^2$ pro $n\geq4$ .

Rumburak

↑ musixx:
Zdravím. Tvá úvaha je správná za předpokladu, že vždy bude $a_i \ge 0$ , to ale v zadání není řečeno,
místo toho je tam předpoklad $\sum_{i=1}^{n}{a_i}\ge n$ , který má říci, že budou existovat $a_i > 0$ , mající v tomto součtu
"dosti velkou váhu".
Tím ale nechci naznačovat, že bych tuto úlohu měl vyřešenou :-) .

Protipříklad dokazující, že předpokládat pouze druhou nerovnost nestačí: $n = 4$ , $a_1 = a_2 = a_3 = a_4 = -2$
a není těžké najít i nějaký mnohem lepší.

check_drummer · 01. 10. 2009 22:08

Je to tak, pro kladná čísla by bylo samozřejmě řešení triviální.
Dnes jsem o tom venku při dešti a větru lehce přemýšlel:
Je zřejmé (z druhé podmínky), že $(max(a_i))^2 >= n$ , tj. buď max(ai) <= -2 nebo max(ai) >= 2.

Pro případ, kdy n=4 (nejmenší možné n), pokud by nastalo, že max(ai) <= -2 a (pro spor) ai < 2 pro všechna i, pak součet ai (díky tomu, že jsou jen 4) bude menší než 4 a tedy nebude splněna první podmínka.

K případu n > 4 jsem se zatím díky počasí nedostal, ale díky druhé podmínce se intuitivně jeví, že věta bude platit "tím spíše" (díky kvadrátu n na jedné straně, ale sčítáme jen n kvadrátů). Intuice samozřejmě nic neříká. Vidím dvě cesty - buď podobný důkaz sporem jako výše pro n=4 (se složitějšími možnostmi) a nebo indukci.

Takže to vidím pro tuto chvíli jako konec prvního dílu. :-)

Marian · 02. 10. 2009 13:58 — Editoval Marian (02. 10. 2009 14:32)

Mylná úvaha Zobrazit/skrýt!

PS.
Jenže to jsme dokázat nechtěli. Na chybu mě upozornil kolega musixx. Zkusím se zamyslet ještě později.

musixx · 02. 10. 2009 14:12 — Editoval musixx (02. 10. 2009 14:14)

↑ Marian: Tohle řešení bohužel podle mě obsahuje stejný nedostatek, jakého jsem se dopustil výše. Nerovnost $\sum_{i=1}^{n}a_i^2\le\sum_{i=1}^{n}\alpha ^2$ očekává $|a_i|<\alpha$ . Klidně může být $\alpha=3$ , ale nějaké $a_i=-4$ . A pak detail: v definici $\alpha$ se má jít asi přes všechna $i$ , ne? Nebo jsem se v tomto vlákně spálil už podruhé?

check_drummer · 02. 10. 2009 17:35

↑ check_drummer:

Tak jsem se zamyslel podruhé a je tu druhý díl úvah. :-) Případ n=4 máme dokázán. Zkusme indukci:

$\sum_{i=1}^{n}{a_i} >= n \Leftrightarrow \sum_{i=1}^{n-1}{a_i} >= n - a_n$ . Abychom mohli použít indukci, musí platit, že poslední pravá strana je větší než n-1, tj. $a_n <= 1$ .
Podobně, i když trochu zdlouhavěji dokážeme, že abychom mohli použít indukci, musí z druhé podmínky (se čtverci) platit: $a_n^2 <= (2n-1)$ a jelikož pro kladnou hodnotu $a_n$ bychom dostali, že $a_n >= 2$ , zabývejme se jen zápornými $a_n$ , pak $a_n >= -\sqrt{2n - 1}$ .

Jelikož stačí, aby toto platilo pro libovolný index, nikoli n, stačí pro použití indukce najít jediné $a_i$ splňující $-\sqrt{2n - 1} <= a_i <= 1$ .

Pokud takové i neexistuje, pokusím se dojít ke sporu, ale to až příště, teď mě tlačí čas, jako ostatně pořád. :-)

check_drummer · 03. 10. 2009 10:07

↑ check_drummer:

Tak tu máme třetí pokračovaní. :-)

Tedy víme, že pro všechna $a_i$ v této fázi důkazu platí, že $a_i < -\sqrt{2n - 1} \bigvee a_i > 1$ . Tedy buď je a_i kladné a větší než 1 a nebo záporné a menší než $-\sqrt{2n - 1}$ . Pro tuto chvíli předpokládejme, že záporná $a_i$ jsou rovna přesně $-\sqrt{2n - 1}$ . (To je sice zjednodušení i nepřesnost, protože pro záporná $a_i$ platí, že jsou ostře meší než $-\sqrt{2n - 1}$ . Toto budeme muset v budoucnu ještě dořešit.) Označme jako "a" počet záporných $a_i$ a tedy (n-a) je počet kladných $a_i$ . Podle podmínek pro $a_i$ dostáváme (z druhé podmínky - se čtverci): $n^2 <= a.(-\sqrt{2n - 1})^2 + \sum_{a_i>0}^{}{a_i^2} < a.(-\sqrt{2n - 1})^2 + (n-a).4$ , tj. $a > \frac{n(n-4)}{2n-5}$ . Obdobně podle první podmínky: $n <= a.(-\sqrt{2n - 1}) + \sum_{a_i>0}^{}{a_i} < a.(-\sqrt{2n - 1}) + (n-a).2$ , tj. $a < \frac{(\sqrt{2n-1}-2)n}{2n-5}$ . Ovšem porovnáním obou podmínek pro a dostneme: $n-4 < a < {(\sqrt{2n-1}-2)$ , tj. $n-2 < \sqrt{2n-1}$ , z čehož ovšem po umocnění plyne $n^2 - 6n + 5 < 0$ , což je ovšem splněno jen pro n<5 (a indukci uvažujeme pro n>=5). To je spor.

Zbývá dořešit problém, co když bude $a_i$ libovolné záporné menší než $-\sqrt{2n - 1}$ a nikoli přesně rovno $-\sqrt{2n - 1}$ . O tom ale snad někdy příště, pokud mě něco napadne. :-)

Rumburak

Šel jsem na to následovně -

Autor skryl část textu. Zobrazit/skrýt!

Kondr · 05. 10. 2009 14:06

Myslím, že postačí úvaha o znaménkách.

Autor skryl část textu. Zobrazit/skrýt!

check_drummer · 05. 10. 2009 23:14

↑ check_drummer:
Tak jsem na to šel nakonec sporem: dokážeme, že pro $max(a_i) < 2$ nebude mezi $a_i$ žádné záporné číslo a zbytek bude snadný.
Platí tedy: $\sum_{a_i>0}^{}{a_i} + \sum_{a_i<=0}^{}{a_i} >= n$ , tedy $\sum_{a_i<=0}^{}{a_i} > n - 2(n-a)$ , kde $a$ je počet nekladných $a_i$ , obdobně $\sum_{a_i<=0}^{}{a_i^2} > n^2 - 4(n-a)$ . Označme pro $a_i <= 0$ : $c_i = -a_i$ , pak $\sum_{}^{}{c_i} < n - 2a$ a $\sum_{}^{}{c_i^2} > n^2 - 4n + 4a$ . Umocnění první rovnosti na druhou dá: $(\sum_{}^{}{c_i})(\sum_{}^{}{c_i}) < (n - 2a)^2 = n^2 - 4an + 4a^2$ . Nyní využijeme známou nerovnost, jejíž jméno jsem zapomněl :-) (cachy-schwarzova?): $\sum_{}^{}{c_i^2} <= (\sum_{}^{}{c_i})(\sum_{}^{}{c_i})$ .
Teď dáme vše dohromady: $n^2 - 4n + 4a < \sum_{}^{}{c_i^2} <= (\sum_{}^{}{c_i})(\sum_{}^{}{c_i}) < n^2 - 4an + 4a^2$ , tj. $n^2 - 4n + 4a < n^2 - 4an + 4a^2$ , tj. $a(a-n) > a-n$ a protože nemůže nastat a=n (všechna záporná čísla by nesplňovala první podmínku), můžeme nerovnici dělit (a-n) což je záporné číslo, tedy dostaneme a<1, což znamená, že všechna $a_i$ jsou kladná. To ale znamená, že $4n > \sum_{i=1}^{n}{a_i^2} >= n^2$ (dle předpokladu, že $max(a_i) < 2$ a nyní navíc víme, že $a_i > 0$ ), tedy n < 4. což je spor s předpokladem, že n > 3 (n je celé).

Kondr · 06. 10. 2009 00:29

Nerovnost $\sum_{}^{}{c_i^2} <= (\sum_{}^{}{c_i})(\sum_{}^{}{c_i})$ není Cauchy-Schwarzova, v MŘMÚ je uvedena jako speciální případ Jensenovy nerovnosti, ale ne té známé. Její platnost je ale po roznásobení zřejmá, takže není potřeba ji pojmenovávat.

Marian · 07. 10. 2009 12:10

Kondr napsal(a):
Myslím, že postačí úvaha o znaménkách.
...
Máme
z první nerovnosti $n\leq c_1+...+c_n-s\leq lM-s$ , odtud $s\leq lM-n$
...

Myslím, že je tam překlep - citovaný odhad má mít tvar $n\leq c_1+c_2+\cdots \boxed{c_l}-s\le lM-s$ . Ovšem pokud jsem zase cosi neřehlédnul.

Kondrova elementární úvaha je skutečně elegantní.

musixx · 07. 10. 2009 12:13 — Editoval musixx (07. 10. 2009 12:17)

↑ Marian: Ano, a je tam ještě jeden na konci: $M\boxed{\geq}\frac{2n}{(n-1)+1}=2$ . A taktéž se připojuji k pochvale řešení.

EDIT: Říkám si, jesli by nešlo se zbavit podmínky $n>3$ (a zesílit současně tvrzení) tím, že budeme dokazovat, že $\max\,a_i\geq\sqrt n$ . Ale moc jsem nad tím nepřemýšlel, takže je možné, že se najde lehce protipříklad.

Kondr · 07. 10. 2009 14:10

↑ Marian:↑ musixx:Díky, máte pravdu, opraveno.

musixx napsal(a):
EDIT: Říkám si, jesli by nešlo se zbavit podmínky $n>3$ (a zesílit současně tvrzení) tím, že budeme dokazovat, že $\max\,a_i\geq\sqrt n$ . Ale moc jsem nad tím nepřemýšlel, takže je možné, že se najde lehce protipříklad.

To bohužel ne. Jak jsme s Rumburakem dokázali (geometricky i "analyticky"), nerovnost $\max\,a_i\geq\sqrt n$ pro $n>4$ nebude platit pro případ $a_2=\cdots=a_n=2$ a $a_1=2-n$ . Dovolím si takový drobný poznatek (ne ze své hlavy): ke studiu nerovností je dobré určit, kdy nastává rovnost. Je to dobrá indicie pro to, jak silné/slabé odhady si může člověk dovolit.

Matematické Fórum

#1 30. 09. 2009 22:10

Omezení sumy čísel -> omezení jejich maxima

#2 01. 10. 2009 13:03

Re: Omezení sumy čísel -> omezení jejich maxima

#3 01. 10. 2009 16:16 — Editoval Rumburak (02. 10. 2009 09:13)

Re: Omezení sumy čísel -> omezení jejich maxima

#4 01. 10. 2009 22:08

Re: Omezení sumy čísel -> omezení jejich maxima

#5 02. 10. 2009 13:58 — Editoval Marian (02. 10. 2009 14:32)

Re: Omezení sumy čísel -> omezení jejich maxima

#6 02. 10. 2009 14:12 — Editoval musixx (02. 10. 2009 14:14)

Re: Omezení sumy čísel -> omezení jejich maxima

#7 02. 10. 2009 17:35

Re: Omezení sumy čísel -> omezení jejich maxima

#8 03. 10. 2009 10:07

Re: Omezení sumy čísel -> omezení jejich maxima

#9 04. 10. 2009 17:19 — Editoval Rumburak (05. 10. 2009 12:22)

Re: Omezení sumy čísel -> omezení jejich maxima

#10 05. 10. 2009 14:06

Re: Omezení sumy čísel -> omezení jejich maxima

#11 05. 10. 2009 23:14

Re: Omezení sumy čísel -> omezení jejich maxima

#12 06. 10. 2009 00:29

Re: Omezení sumy čísel -> omezení jejich maxima

#13 07. 10. 2009 12:10

Re: Omezení sumy čísel -> omezení jejich maxima

Kondr napsal(a):

#14 07. 10. 2009 12:13 — Editoval musixx (07. 10. 2009 12:17)

Re: Omezení sumy čísel -> omezení jejich maxima

#15 07. 10. 2009 14:10

Re: Omezení sumy čísel -> omezení jejich maxima

musixx napsal(a):

Zápatí