Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Ja, syn polskiej ziemi, chciałem spytać, czy moje rozwiązanie rzeczonego zadania jest poprawne.
Oto treść problematu: Dowieść, że dla każdej liczby naturalnej \(\displaystyle{ n}\) i ciągu liczb rzeczywistych \(\displaystyle{ a_1, a_2, \ldots a_n}\) istnieje liczba naturalna \(\displaystyle{ k\le n}\) taka, że \(\displaystyle{ \left| \sum_{i=1}^{k}a_i- \sum_{i=k+1}^{n}a_i \right|\le \max_{1\le i\le n}|a_i|}\)
moja propozycja rozwiązania:
Lemat: dla dowolnych liczb rzeczywistych \(\displaystyle{ x,y}\) zachodzi następująca równość: \(\displaystyle{ |x+y|+|x-y|=2\max\left\{ |x|, |y|\right\}}\)
Dowód tej własności zostawiam jako nietrudne ćwiczenie.
Będziemy przeprowadzać indukcję po \(\displaystyle{ n\in \NN^+, \ n\ge 2}\).
\(\displaystyle{ 1^{\circ}}\) Dla \(\displaystyle{ n=2}\) odnotujmy, że \(\displaystyle{ |a_1-a_2|+|a_1+a_2|=2\max\left\{ |a_1|, |a_2|\right\}}\), a zatem zachodzi \(\displaystyle{ |a_1-a_2|\le \max\left\{ |a_1|, |a_2|\right\} \vee |a_1+a_2|\le \max\left\{ |a_1|, |a_2|\right\}}\)
(jak to za mało, to łatwo dowodzimy przez sprzeczność: nie wprost \(\displaystyle{ |a_1-a_2|>\max\left\{ |a_1|, |a_2|\right\}\wedge |a_1+a_2|>\max\left\{ |a_1|, |a_2|\right\}}\) i dodajemy stronami).
Czyli OK.
\(\displaystyle{ 2^{\circ}}\) Przypuśćmy, że dla pewnego \(\displaystyle{ n\ge 3}\) teza zachodzi dla dowolnego ciągu liczb rzeczywistych długości \(\displaystyle{ n-1}\). Weźmy dowolny ciąg liczb rzeczywistych długości \(\displaystyle{ n}\): \(\displaystyle{ a_1, a_2, \ldots a_n}\).
Istnieje wówczas \(\displaystyle{ k\in\left\{ 2, \ldots n\right\}}\) oraz \(\displaystyle{ l\in\left\{ 1, \ldots n\right\}\setminus\left\{ k\right\}}\) takie, że \(\displaystyle{ \left| \sum_{i=1}^{k-1}a_i- \sum_{i=k+1}^{n}a_i \right|\le |a_l|}\)
Zaprzeczenie powyższego stwierdzenia daje bowiem natychmiast kontradykcję z założeniem indukcyjnym.
Teraz odnotujmy, że \(\displaystyle{ \left| \sum_{i=1}^{k}a_i- \sum_{i=k+1}^{n}a_i \right|+\left| \sum_{i=1}^{k-1}a_i- \sum_{i=k}^{n}a_i \right|=2\max\left\{ |a_k|, \left|| \sum_{i=1}^{k-1}a_i- \sum_{i=k+1}^{n}a_i \right| \right\}\le 2\max\left\{ |a_k|, |a_l|\right\} \le 2\max_{1\le i\le n}|a_i|}\)
Wobec tego któraś z liczb \(\displaystyle{ \left| \sum_{i=1}^{k}a_i- \sum_{i=k+1}^{n}a_i \right|, \ \left| \sum_{i=1}^{k-1}a_i- \sum_{i=k}^{n}a_i \right|}\) musi być nie większa niż \(\displaystyle{ \max_{1\le i\le n}|a_i|}\) (uzasadnienie przez sprzeczność jak przy bazie indukcji), co kończy dowód.
Będę wdzięczny za zauważenie jakichkolwiek błędów w tej próbie rozwiązania, a jeśli takowe nie wystąpiły, to za potwierdzenie poprawności. Jeśli napisałem jakieś straszne bzdury, to sorry za marnowanie czasu.
A tutaj macie wzorcówkę:
Dodatkowe pytania: jak wpadać na takie rzeczy, jak to w rozwiązaniu wzorcowym? Nie wiem, biegać na 40 km, jeść jagody Goji, czy co A może to kwestia wrodzonej spostrzegawczości, jak ktoś nie ma „tego czegoś", to już mieć nie będzie?
EDIT: Ech, już widzę, to powyżej do niczego się nie nadaje, chyba „udało" mi się pomylić kwantyfikatory, nie mogę sobie tak luźno traktować tej „przerwy". W każdym razie chętnie zobaczę inne rozwiązanie niż wzorcowe, które jest według mnie z sufitu wzięte.
Archom aktualnie nie działa, więc przestawię swój pomysł.
Najpierw może, jak na to wpaść:
Analizuję, jak się zmienia wartość wnętrza wartości bezwzględnej wraz ze zmianą \(\displaystyle{ k}\). Analizując powstałe wyrazy mam intuicję, że trzeba skupić się takim \(\displaystyle{ k}\), że wartość tego wnętrza zmieniła znak w stosunku do poprzedniego wyrazu (o ile taka sytuacja ma miejsce - będziemy dążyć, żeby to też wykazać). Wtedy wnętrze powinno być w tym otoczeniu wystarczająco małe, żeby spełniło tezę zadania.
Oznaczenia i założenia, które się przydadzą później.
* Niech \(\displaystyle{ S=\sum_{i=1}^n a_i}\).
* Niech \(\displaystyle{ b_i=\sum_{i=1}^{k}a_i- \sum_{i=k+1}^{n}a_i}\) - definiuję to nieco szerzej niż w zadaniu, bo przyda mi się wartość ciągu \(\displaystyle{ b_i}\) zaczynając już od \(\displaystyle{ i=0}\) (wyjaśni się później, czemu zaczynamy już tutaj, a nie od \(\displaystyle{ i=1}\)), a kończąc na \(\displaystyle{ i=n}\).
* Niech też dla ustalenia uwagi \(\displaystyle{ S \ge 0}\) (zamiana wszystkich \(\displaystyle{ a_i}\) na \(\displaystyle{ -a_i}\) nic nie zmieni w zadaniu).
* Niech \(\displaystyle{ M=\max_{1\le i\le n}|a_i|}\), oczywiście \(\displaystyle{ M \ge 0}\).
Rozważania i dowód:
Czym się więc różni \(\displaystyle{ b_{i+1}}\) od \(\displaystyle{ b_i}\)? Pierwsza suma (odjemna) zawiera jeden więcej składnik, a druga suma (odjemnik) właśnie ten składnik "traci". Formalnie: \(\displaystyle{ b_{i+1}-b_i=2a_i}\), czyli: \(\displaystyle{ b_0=-S \\ b_1=b_0+2a_1 \\ b_2=b_1+2a_2 \\ \ldots \\ b_n=b_{n-1}+2a_n=2S-S=S.}\)
Ponieważ przyjęliśmy \(\displaystyle{ S \ge 0}\), to \(\displaystyle{ b_0 \le 0}\) oraz \(\displaystyle{ b_n \ge 0}\). Muszą więc istnieć takie dwa kolejne wyrazy ciągu - niech to będą \(\displaystyle{ b_i}\) oraz \(\displaystyle{ b_{i+1}}\), że następuje "moment zmiany znaku" (zgodnie z intuicją). Formalnie - istnieje takie \(\displaystyle{ i \in \lbrace 0, 1, \ldots, n-1 \rbrace}\), że \(\displaystyle{ b_i \le 0 \le b_{i+1}}\). Kluczowe teraz będzie to, że \(\displaystyle{ b_{i+1}-b_i=2a_i \le 2M}\) (tu już widać dalszy kierunek rozumowania).
Gdyby \(\displaystyle{ |b_i|>M}\) oraz \(\displaystyle{ |b_{i+1}|>M}\), to, pamiętając o ich znakach, mamy \(\displaystyle{ b_i < -M \le 0 \le M < b_{i+1}}\). Jednak to oznacza, że \(\displaystyle{ 2a_i=b_{i+1}-b_i>2M}\), czyli \(\displaystyle{ a_i>M}\) - sprzeczność z definicją \(\displaystyle{ M}\). Zatem zachodzi \(\displaystyle{ |b_i| \le M}\) lub \(\displaystyle{ |b_{i+1}| \le M}\), co kończy dowód.
To znaczy... prawie kończy... bo jedyną opcją, która nie daje nam tezy, jest wzięte "na doczepkę" \(\displaystyle{ b_0}\) i gdyby to właśnie dla niego zachodziło \(\displaystyle{ |b_0| \le M}\). Ale... nie ma z tym problemu, bo \(\displaystyle{ b_n=-b_0}\), czyli wtedy \(\displaystyle{ |b_n|=|b_0| \le M}\), co już ostatecznie kończy dowód.
Może dziwić moje zapotrzebowanie na \(\displaystyle{ b_0}\) - potrzebowałem po prostu dwóch liczb przeciwnych, aby mieć pewność zmiany znaku, czasem takie sztuczki techniczne bardzo ułatwiają zapis i ograniczają liczbę dodatkowych przypadków.
dla \(\displaystyle{ k=1,...,n}\) oraz niech \(\displaystyle{ M = \max_{1\leq k\leq n}|a_k|}\). Ponadto niech
\(\displaystyle{ s_0 = -\sum_{i=1}^na_i}\)
Teraz trzeba coś prostego z tymi liczbami zrobić i coś ciekawego zauważyć. Dlaczego? To kwestia osobistych preferencji. Jeśli czegoś w matematyce się w taki sposób nie da zrobić, to ja po prostu tego nie zamierzam robić (i pewnie też nie umiem). Mamy
Uważam, że to jest bardzo ciekawe w kontekście zadania, bo teraz mogę podać taką interpretację. Załóżmy, że mam żabę, która skacze po prostej rzeczywistej \(\displaystyle{ \mathbb{R}}\). Na początku żaba siedzi w punkcie \(\displaystyle{ s_0}\), potem przeskakuje do punktu \(\displaystyle{ s_1}\), potem przeskakuje do punktu \(\displaystyle{ s_2}\) itd. aż znajdzie się w punkcie \(\displaystyle{ s_n}\). Teraz:
(1) Z nierówności powyżej (i dlatego ona jest świetna) wynika, że długość każdego skoku żaby nie przekracza \(\displaystyle{ 2\cdot M}\).
(2) Z faktu, że \(\displaystyle{ s_0 = -s_n}\) widzimy, że żaba początkowo znajduje się po jednej stronie \(\displaystyle{ 0\in \mathbb{R}}\) i na końcu jest po drugiej stronie \(\displaystyle{ 0\in \mathbb{R}}\).
Z punktu (2) widać, że żaba musi w trakcie swojej podróży w pewnym momencie przeskoczyć nad \(\displaystyle{ 0\in \mathbb{R}}\). Z punktu (1) wiemy jednak, że żaba wykonuje skoki długości \(\displaystyle{ \leq 2\cdot M}\). Oznacza to, że w pewnym momencie żaba znajdzie się w przedziale \(\displaystyle{ [-M,M]}\). Oczywiście to trzeba formalnie zapisać i wyeliminować tę całą żabę, ale pokazuje to, że dla pewnego \(\displaystyle{ k=0,1,...,n}\) zachodzi
\(\displaystyle{ s_k\in [-M, M]}\) lub równoważnie \(\displaystyle{ |s_k|\leq M}\)
Jeżeli \(\displaystyle{ k\neq 0}\), to mamy tezę. Jeśli \(\displaystyle{ k=0}\), to
\(\displaystyle{ |s_n| = |-s_0|\leq M}\)
i też mamy tezę.
Podejrzewam też, że na OM-ie za tak napisane rozwiązanie dostałbym pewnie \(\displaystyle{ 5}\) punktów na \(\displaystyle{ 6}\) (gorzej, gdybym dostał \(\displaystyle{ 2}\), ale może by się zlitowali). Wzorcowe rozwiązanie mi się nie podoba. Zaoszczędzę swój czas i go nie przeczytam .
Dziękuję Wam bardzo. Uważam, że to podejście jest dużo bardziej intuicyjne od wzorcówki, właśnie na coś takiego liczyłem, zakładając ten wątek. Niestety nie mogę wstawić „pomógł".
