Ciekawa granica
- mol_ksiazkowy
- Użytkownik
- Posty: 11473
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3157 razy
- Pomógł: 748 razy
Ciekawa granica
Niech \(\displaystyle{ f(n)}\) będzie największą nieparzystą liczbą która dzieli \(\displaystyle{ n}\). Udowodnić, że ciąg \(\displaystyle{ \frac{ \frac{f(1)}{1}+...+ \frac{f(n)}{n}}{n} }\) jest zbieżny i obliczyć jego granicę
-
- Użytkownik
- Posty: 164
- Rejestracja: 27 paź 2015, o 23:44
- Płeć: Mężczyzna
- Podziękował: 17 razy
- Pomógł: 30 razy
Re: Ciekawa granica
Dla \(\displaystyle{ n}\) nieparzystych \(\displaystyle{ f(n)=n}\), bo liczba n dzieli samą siebie. Dla parzystych \(\displaystyle{ f(n)=f\left(\frac{n}{2}\right)}\).
\(\displaystyle{ S(n) = \frac{\frac{f(1)}{1} + ... + \frac{f(n)}{n}}{n} = \frac{\frac{f(1)}{1}+\frac{f(3)}{3}+\frac{f(5)}{5}+...\frac{f(2)}{2}+\frac{f(4)}{4}+\frac{f(6)}{6}...+\frac{f(n)}{n}}{n} = \frac{1+1+1...+\frac{1}{2}\left(\frac{f(1)}{1}+\frac{f(2)}{2}+\frac{f(3)}{3}...\frac{f(n/2)}{n/2}\right)}{n}}\)
\(\displaystyle{ S(n)=\frac{1}{2}+\frac{1}{4}S\left(\frac{n}{2}\right)
}\)
Jeśli szereg jest zbieżny to \(\displaystyle{ \lim_{n\to \infty}\left(S\left(n\right)-S\left(\frac{n}{2}\right)\right)=0}\), czyli \(\displaystyle{ S\left(n\right) \to S\left(\frac{n}{2}\right)}\)
\(\displaystyle{ \frac{3}{4}S(n) \to \frac{1}{2}}\)
\(\displaystyle{ S(n) \to \frac{1}{2}\cdot\frac{4}{3}=\frac{2}{3}}\).
A szereg jest zbieżny ponieważ jest dodatni oraz dla każdego naturalnego dodatniego m, \(\displaystyle{ \frac{f(m)}{m}\le 1}\), więc \(\displaystyle{ S(n)\le 1}\).
\(\displaystyle{ S(n) = \frac{\frac{f(1)}{1} + ... + \frac{f(n)}{n}}{n} = \frac{\frac{f(1)}{1}+\frac{f(3)}{3}+\frac{f(5)}{5}+...\frac{f(2)}{2}+\frac{f(4)}{4}+\frac{f(6)}{6}...+\frac{f(n)}{n}}{n} = \frac{1+1+1...+\frac{1}{2}\left(\frac{f(1)}{1}+\frac{f(2)}{2}+\frac{f(3)}{3}...\frac{f(n/2)}{n/2}\right)}{n}}\)
\(\displaystyle{ S(n)=\frac{1}{2}+\frac{1}{4}S\left(\frac{n}{2}\right)
}\)
Jeśli szereg jest zbieżny to \(\displaystyle{ \lim_{n\to \infty}\left(S\left(n\right)-S\left(\frac{n}{2}\right)\right)=0}\), czyli \(\displaystyle{ S\left(n\right) \to S\left(\frac{n}{2}\right)}\)
\(\displaystyle{ \frac{3}{4}S(n) \to \frac{1}{2}}\)
\(\displaystyle{ S(n) \to \frac{1}{2}\cdot\frac{4}{3}=\frac{2}{3}}\).
A szereg jest zbieżny ponieważ jest dodatni oraz dla każdego naturalnego dodatniego m, \(\displaystyle{ \frac{f(m)}{m}\le 1}\), więc \(\displaystyle{ S(n)\le 1}\).
- Dasio11
- Moderator
- Posty: 10235
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2365 razy
Re: Ciekawa granica
To niepoprawne wnioskowanie, bo nie każdy ciąg o wyrazach w przedziale \(\displaystyle{ (0, 1]}\) jest zbieżny.
-
- Użytkownik
- Posty: 164
- Rejestracja: 27 paź 2015, o 23:44
- Płeć: Mężczyzna
- Podziękował: 17 razy
- Pomógł: 30 razy
Re: Ciekawa granica
Zgadza się. Zapomniałem napisać, że jest też monotoniczny.
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Ciekawa granica
Zastanówmy się, ile jest w przedziale \(\displaystyle{ \left(\frac{n}{2^{k}}, \frac{n}{2^{k-1}}\right]}\) – gdzie \(\displaystyle{ 1\le k\le \left\lfloor \log_{2}n\right\rfloor+1}\) – liczb całkowitych dodatnich nieparzystych. Wychodzi (oszacowania z dwóch stron) nie mniej niż
\(\displaystyle{ \frac{1}{2}\left(\frac{n}{2^{k-1}}-\frac{n}{2^{k}}-1\right)}\) i nie więcej niż \(\displaystyle{ \frac{1}{2}\left(\frac{n}{2^{k-1}}-\frac{n}{2^{k}}+1\right)}\) (specjalnie unikam, póki można, cech, żeby uprościć rozumowanie i zapis).
A gdy jakaś liczba nieparzysta \(\displaystyle{ r}\) wpada do przedziału \(\displaystyle{ \left(\frac{n}{2^{k}}, \frac{n}{2^{k-1}}\right]}\), to pojawi się jako wartość \(\displaystyle{ f(j), \ j\le n}\) dokładnie \(\displaystyle{ k}\) razy: \(\displaystyle{ f(r)=f(2r)=\ldots=f\left(2^{k-1}r\right)=r}\). No i oczywiście \(\displaystyle{ \frac{f\left(2^{i}r\right)}{2^{i}r}=\frac{1}{2^{i}}}\) dla nieparzystego \(\displaystyle{ r}\) i naturalnego \(\displaystyle{ i}\).
Zatem mamy oszacowanie
\(\displaystyle{ \frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}\frac{1}{2}\left(\frac{n}{2^{k-1}}-\frac{n}{2^{k}}-1\right)\sum_{i=0}^{k-1}\frac{1}{2^{i}}\le \frac{\frac{f(1)}{1}+\frac{f(2)}{2}+\ldots+\frac{f(n)}{n}}{n}\le \frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}\frac{1}{2}\left(\frac{n}{2^{k-1}}-\frac{n}{2^{k}}+1\right)\sum_{i=0}^{k-1}\frac{1}{2^{i}}}\)
Po cierpliwym zsumowaniu i elementarnych oszacowaniach (ignorujesz częstokroć moje – i nie tylko moje – rozwiązania, więc nie będę ich cyzelował), dostajemy wynik na mocy twierdzenia o trzech ciągach. By zobaczyć, że to zadziała, wystarczy spojrzeć, iż
\(\displaystyle{ \lim_{n\to \infty}\frac{1}{n}\sum_{k=1}^{\lfloor log_{2}n\rfloor+1}\sum_{i=0}^{k-1}\frac{1}{2^{i}}=0}\)
bo to wyrażenie pod granicą to jest różnica naszej majoranty i minoranty. No a to się trywialnie szacuje z dołu przez zero (suma dodatnich składników) i z góry przez \(\displaystyle{ \frac{2}{n}\left(\lfloor\log_{2}n\rfloor+1\right)}\), wszak \(\displaystyle{ \sum_{j=0}^{\infty}\frac{1}{2^{j}}=2}\)
\(\displaystyle{ \frac{1}{2}\left(\frac{n}{2^{k-1}}-\frac{n}{2^{k}}-1\right)}\) i nie więcej niż \(\displaystyle{ \frac{1}{2}\left(\frac{n}{2^{k-1}}-\frac{n}{2^{k}}+1\right)}\) (specjalnie unikam, póki można, cech, żeby uprościć rozumowanie i zapis).
A gdy jakaś liczba nieparzysta \(\displaystyle{ r}\) wpada do przedziału \(\displaystyle{ \left(\frac{n}{2^{k}}, \frac{n}{2^{k-1}}\right]}\), to pojawi się jako wartość \(\displaystyle{ f(j), \ j\le n}\) dokładnie \(\displaystyle{ k}\) razy: \(\displaystyle{ f(r)=f(2r)=\ldots=f\left(2^{k-1}r\right)=r}\). No i oczywiście \(\displaystyle{ \frac{f\left(2^{i}r\right)}{2^{i}r}=\frac{1}{2^{i}}}\) dla nieparzystego \(\displaystyle{ r}\) i naturalnego \(\displaystyle{ i}\).
Zatem mamy oszacowanie
\(\displaystyle{ \frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}\frac{1}{2}\left(\frac{n}{2^{k-1}}-\frac{n}{2^{k}}-1\right)\sum_{i=0}^{k-1}\frac{1}{2^{i}}\le \frac{\frac{f(1)}{1}+\frac{f(2)}{2}+\ldots+\frac{f(n)}{n}}{n}\le \frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}\frac{1}{2}\left(\frac{n}{2^{k-1}}-\frac{n}{2^{k}}+1\right)\sum_{i=0}^{k-1}\frac{1}{2^{i}}}\)
Po cierpliwym zsumowaniu i elementarnych oszacowaniach (ignorujesz częstokroć moje – i nie tylko moje – rozwiązania, więc nie będę ich cyzelował), dostajemy wynik na mocy twierdzenia o trzech ciągach. By zobaczyć, że to zadziała, wystarczy spojrzeć, iż
\(\displaystyle{ \lim_{n\to \infty}\frac{1}{n}\sum_{k=1}^{\lfloor log_{2}n\rfloor+1}\sum_{i=0}^{k-1}\frac{1}{2^{i}}=0}\)
bo to wyrażenie pod granicą to jest różnica naszej majoranty i minoranty. No a to się trywialnie szacuje z dołu przez zero (suma dodatnich składników) i z góry przez \(\displaystyle{ \frac{2}{n}\left(\lfloor\log_{2}n\rfloor+1\right)}\), wszak \(\displaystyle{ \sum_{j=0}^{\infty}\frac{1}{2^{j}}=2}\)
-
- Użytkownik
- Posty: 164
- Rejestracja: 27 paź 2015, o 23:44
- Płeć: Mężczyzna
- Podziękował: 17 razy
- Pomógł: 30 razy
Re: Ciekawa granica
A ja nie. Ja nie ignoruję Twoich rozwiązań.
Interesuje mnie, jak na to wpadłeś? Ja nad tym siedziałem dniami i nocami. Napisałem algorytm, wg którego granica to \(\displaystyle{ \frac{2}{3} }\), nie potrafiłem dalej. Mógłbym Ciebie poprosić o wyjaśnienie co tam się dzieje z tymi logarytmami? Byłbym bardzi wdzięczny.
A tak przy okazji, to zastanawia mnie czasami, skąd pan mol_ksiazkowy bierze te zadania.
-
- Użytkownik
- Posty: 22233
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3759 razy
-
- Użytkownik
- Posty: 164
- Rejestracja: 27 paź 2015, o 23:44
- Płeć: Mężczyzna
- Podziękował: 17 razy
- Pomógł: 30 razy
Re: Ciekawa granica
Pan mol_ksiazkowy zapodaje bardzo interesujące problemy matematyczne. Na niektóre nikt nie potrafi znaleźć rozwiązań. Mnie się nie podoba, jak pan się wyraża wobec innych użytkowników.
18000 postów to najwidoczniej za mało, żeby się nauczyć szacunku. Nie wiem, co się dzieje w pana głowie, ale ja z politowaniem i smutkiem obserwuję forum, które uwielbiem, kiedy pan bezmyślnie odpycha innych użytkowników i się z nich śmieje.
Matematyka jest dziedziną trudną, wymagającą, skomplikowaną i piękną. Ja zawsze będę tylko uczniem. Każdy matematyk będzie zawsze tylko uczniem.
Matematyka jest piękna, a my (my wszyscy), mamy szczęście, że mamy szansę się tym pięknem podzielić.
Może pan też się tym chciałby podzielić.
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Ciekawa granica
OK, miło mi, że nie ignorujesz (zapewniłeś mi półuśmiech, a to więcej niż mam, szczerze dzięki). Postaram się rzucić na to trochę światła.
Pierwsza myśl jest taka, że funkcja \(\displaystyle{ }\) działa tak, że ignoruje potęgi dwójki, przez jakie dzieli się liczba, na przykład \(\displaystyle{ f(7)=f(14), \ f(5)=f(40)}\) etc. Takie sumy zwykle łatwiej się liczy, jak się jakoś pogrupuje (bo szacowanie każdego wyrazu z osobna nie ma specjalnie sensu, zważywszy na to, iż wyrazy nie mają żadnej sensownej asymptotyki, tj. dla dowolnie dużych \(\displaystyle{ n}\) znajdziemy tak duże, jak i małe wartości funkcji, bo np. \(\displaystyle{ f(2k+1)=2k+1, \ k\in \NN}\), a także \(\displaystyle{ f\left(2^{r}\right)=1, \ r\in \NN}\) – i wartości \(\displaystyle{ \frac{f(n)}{n}}\) sobie będą skakać od \(\displaystyle{ \frac{1}{n}}\) do jedynki). Na początku chciałem to zrobić tak, żeby pogrupować według liczb nieparzystych nieprzekraczających \(\displaystyle{ n}\). Jak weźmiemy liczbę nieparzystą \(\displaystyle{ 2k-1, \ k\in \NN}\), to będzie
\(\displaystyle{ f(2k-1)=f(2\cdot(2k-1))=\ldots=f\left(2^{r}(2k-1)\right)}\) gdy \(\displaystyle{ 2^{r}(2k-1)\le n}\), co sprowadza się do \(\displaystyle{ r\le \log_{2}\left(\frac{n}{2k-1}\right)}\), a z uwagi na całkowitość \(\displaystyle{ r}\) – do \(\displaystyle{ r\le \left\lfloor\log_{2}\left(\frac{n}{2k-1}\right)\right\rfloor}\)
No i tak dla każdej liczby nieparzystej \(\displaystyle{ 2k-1\le n}\), co prowadzi do podwójnej sumy
\(\displaystyle{ \frac{1}{n}\sum_{k=1}^{\left\lfloor \frac{n+1}{2}\right\rfloor}\sum_{i=0}^{\left\lfloor \log_{2}\left(\frac{n}{2k-1}\right)\right\rfloor}\frac{1}{2^{i}}}\),
ponieważ jeśli \(\displaystyle{ n=2^{r}(2k-1)}\), to \(\displaystyle{ \frac{f(n)}{n}=\frac{2k-1}{2^{r}(2k-1)}=\frac{1}{2^{r}}}\).
Wprawdzie wewnętrzną sumę łatwo zwinąć ze wzoru na sumę początkowych wyrazów ciągu geometrycznego, jednak dalej zostają te podłogi i zaczynają się schody.
Dobra, to nie pykło, bo dalej nie potrafiłem sobie poradzić z tymi częściami całkowitymi, więc odłożyłem problemat na jeden dzień, żeby w robocie się nad tym swobodnie zastanowić, gdy klientów nie ma. Niby w robocie mnie nie olśniło, ale następnego dnia rano pomyślałem od drugiej strony:
zamiast grupować wedle największej liczby nieparzystej w takie sznurki typu \(\displaystyle{ \frac{f(2k-1)}{2k-1}+\frac{f(2\cdot(2k-1)}{2\cdot(2k-1)}+\ldots+\frac{f\left(2^{r}\cdot(2k-1)\right)}{2^{r}\cdot(2k-1)}}\), pogrupujmy w ten sposób, żeby do jednej grupki powpadały sumy typu
\(\displaystyle{ 1+\frac{1}{2}+\ldots+\frac{1}{2^{r}}}\) równej długości. A to działa tak: dla liczby nieparzystej \(\displaystyle{ m}\) z przedziału
\(\displaystyle{ \left(\frac{n}{2}, n\right]}\) dostaniemy sumę złożoną z samej jedynki, czyli \(\displaystyle{ \frac{f(m)}{m}}\), a to dlatego, że już \(\displaystyle{ 2m>n}\). Dla każdej liczby nieparzystej z przedziału \(\displaystyle{ \left(\frac{n}{4}, \frac{n}{2}\right]}\) dostaniemy sumę postaci \(\displaystyle{ 1+\frac{1}{2}}\), bo \(\displaystyle{ m\le n, \ 2m\le n}\), lecz już \(\displaystyle{ 4m>n}\). I łatwo to dalej uogólnić w ten sposób, że dla liczby nieparzystej z przedziału \(\displaystyle{ \left(\frac{n}{2^{k}}, \ \frac{n}{2^{k-1}}\right]}\) dostaniemy sumę \(\displaystyle{ \frac{f(m)}{m}+\frac{f(2m)}{2m}+\ldots+\frac{f\left(2^{k-1}m\right)}{2^{k-1}m}=1+\frac{1}{2}+\ldots+\frac{1}{2^{k-1}}}\).
Pozostaje zliczyć liczby nieparzyste w przedziale \(\displaystyle{ \left(\frac{n}{2^{k}}, \ \frac{n}{2^{k-1}}\right]}\). Jak masz odcinek \(\displaystyle{ (a,b], \ a,b>0}\), to znajduje się w nim \(\displaystyle{ \lfloor b\rfloor-\lceil a\rceil+1}\) liczb całkowitych:
\(\displaystyle{ \lceil a\rceil+0, \ \lceil a\rceil +1, \ldots, \lceil a\rceil +(\lfloor b\rfloor-\lceil a\rceil)=\lfloor b\rfloor}\)
Wśród powyższych liczb najwięcej nieparzystych będzie, gdy zarówno \(\displaystyle{ \lceil a\rceil}\), jak i \(\displaystyle{ \lfloor b\rfloor}\) będą nieparzyste, a najmniej nieparzystych – gdy tak \(\displaystyle{ \lceil a\rceil}\), jak i \(\displaystyle{ \lfloor b\rfloor}\) będą parzyste.
Otrzymamy w tych sytuacjach odpowiednio \(\displaystyle{ \frac{1}{2}\left(\lfloor b\rfloor -\lceil a\rceil\right)+1}\) i \(\displaystyle{ \frac{1}{2}\left(\lfloor b\rfloor -\lceil a\rceil\right)}\) liczb nieparzystych.
No to teraz wstawiamy tam te \(\displaystyle{ \frac{n}{2^{k}}, \ \frac{n}{2^{k-1}}}\) i mamy co najmniej
\(\displaystyle{ \frac{1}{2}\left(\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lceil \frac{n}{2^{k}}\right\rceil\right)}\)
zaś co najwyżej
\(\displaystyle{ \frac{1}{2}\left(\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lceil \frac{n}{2^{k}}\right\rceil\right)+1}\)
liczb nieparzystych w przedziale \(\displaystyle{ \left(\frac{n}{2^{k}}, \frac{n}{2^{k-1}}\right]}\)
No i ponieważ \(\displaystyle{ \lfloor x\rfloor \le x, \ lceil x\rceil \ge x}\), więc
\(\displaystyle{ \frac{1}{2}\left(\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lceil \frac{n}{2^{k}}\right\rceil\right)+1\le \frac{n}{2^{k-1}}-\frac{n}{2^{k}}+1}\), a ponieważ
\(\displaystyle{ \lfloor x\rfloor >x-1, \ \lceil x\rceil<x+1 }\), więc
\(\displaystyle{ \frac{1}{2}\left(\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lceil \frac{n}{2^{k}}\right\rceil\right)>\frac{1}{2}\left( \frac{n}{2^{k-1}}-1-\left( \frac{n}{2^{k}}+1\right)\right)\\=\frac{1}{2}\left( \frac{n}{2^{k-1}}- \frac{n}{2^{k}}\right)-1}\)
Oczywiście poza tym jest \(\displaystyle{ \frac{n}{2^{k-1}}-\frac{n}{2^{k}}=\frac{n}{2^{k}}}\).
Z tamtymi poprzednimi oszacowaniami mogłem trochę przesadzić, ale teraz już jest dobrze, idei to nie zmienia.
Czyli mamy
\(\displaystyle{ \frac{1}{n}\sum_{j=1}^{n}\frac{f(j)}{j}=\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}
@\left\{m\in \NN: 2\nmid m \wedge \frac{n}{2^{k}}<m\le \frac{n}{2^{k-1}}\right\}\cdot \sum_{i=0}^{k-1}\frac{1}{2^{i}}}\)
oraz
\(\displaystyle{ \frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}\left( \frac{n}{2^{k+1}}-1\right) \sum_{i=1}^{k-1}\frac{1}{2^{i}}\\<\frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}@\left\{m\in \NN: 2\nmid m \wedge \frac{n}{2^{k}}<m\le \frac{n}{2^{k-1}}\right\}\cdot \sum_{i=1}^{k-1}\frac{1}{2^{i}}\\\le \frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}\left(\frac{n}{2^{k+1}}+1\right)\cdot \sum_{i=0}^{k-1}\frac{1}{2^{i}} }\)
i pozostaje zsumować początkowe wyrazy ciągów geometrycznych oraz obliczyć trywialne granice.
Przy czym \(\displaystyle{ @}\) oznacza moc zbioru, niestety hasz mi nie wchodzi (to się jakoś omijało w LaTeX-u, ale już nie pamiętam, jak).
Wynik wynosi, jak napisałeś, \(\displaystyle{ \frac{2}{3}}\).
), czasopism matematycznych (jak Delta czy Crux Mathematicorum), sprawozdań z olimpiad i PDF-ów. Niemniej jednak super byłoby, gdyby mol_ksiazkowy podawał częściej źródła, bo jak problem jest z poziomu IMO czy IMC, to wiadomo, że taki ja nie mam co się za nie brać z powodów genetycznych, a tak można oszczędzić czas.
Dodano po 2 minutach 33 sekundach:
Wiesz, co się liczy? SZACUNEK LUDZI ULICY!!!
Pierwsza myśl jest taka, że funkcja \(\displaystyle{ }\) działa tak, że ignoruje potęgi dwójki, przez jakie dzieli się liczba, na przykład \(\displaystyle{ f(7)=f(14), \ f(5)=f(40)}\) etc. Takie sumy zwykle łatwiej się liczy, jak się jakoś pogrupuje (bo szacowanie każdego wyrazu z osobna nie ma specjalnie sensu, zważywszy na to, iż wyrazy nie mają żadnej sensownej asymptotyki, tj. dla dowolnie dużych \(\displaystyle{ n}\) znajdziemy tak duże, jak i małe wartości funkcji, bo np. \(\displaystyle{ f(2k+1)=2k+1, \ k\in \NN}\), a także \(\displaystyle{ f\left(2^{r}\right)=1, \ r\in \NN}\) – i wartości \(\displaystyle{ \frac{f(n)}{n}}\) sobie będą skakać od \(\displaystyle{ \frac{1}{n}}\) do jedynki). Na początku chciałem to zrobić tak, żeby pogrupować według liczb nieparzystych nieprzekraczających \(\displaystyle{ n}\). Jak weźmiemy liczbę nieparzystą \(\displaystyle{ 2k-1, \ k\in \NN}\), to będzie
\(\displaystyle{ f(2k-1)=f(2\cdot(2k-1))=\ldots=f\left(2^{r}(2k-1)\right)}\) gdy \(\displaystyle{ 2^{r}(2k-1)\le n}\), co sprowadza się do \(\displaystyle{ r\le \log_{2}\left(\frac{n}{2k-1}\right)}\), a z uwagi na całkowitość \(\displaystyle{ r}\) – do \(\displaystyle{ r\le \left\lfloor\log_{2}\left(\frac{n}{2k-1}\right)\right\rfloor}\)
No i tak dla każdej liczby nieparzystej \(\displaystyle{ 2k-1\le n}\), co prowadzi do podwójnej sumy
\(\displaystyle{ \frac{1}{n}\sum_{k=1}^{\left\lfloor \frac{n+1}{2}\right\rfloor}\sum_{i=0}^{\left\lfloor \log_{2}\left(\frac{n}{2k-1}\right)\right\rfloor}\frac{1}{2^{i}}}\),
ponieważ jeśli \(\displaystyle{ n=2^{r}(2k-1)}\), to \(\displaystyle{ \frac{f(n)}{n}=\frac{2k-1}{2^{r}(2k-1)}=\frac{1}{2^{r}}}\).
Wprawdzie wewnętrzną sumę łatwo zwinąć ze wzoru na sumę początkowych wyrazów ciągu geometrycznego, jednak dalej zostają te podłogi i zaczynają się schody.
Dobra, to nie pykło, bo dalej nie potrafiłem sobie poradzić z tymi częściami całkowitymi, więc odłożyłem problemat na jeden dzień, żeby w robocie się nad tym swobodnie zastanowić, gdy klientów nie ma. Niby w robocie mnie nie olśniło, ale następnego dnia rano pomyślałem od drugiej strony:
zamiast grupować wedle największej liczby nieparzystej w takie sznurki typu \(\displaystyle{ \frac{f(2k-1)}{2k-1}+\frac{f(2\cdot(2k-1)}{2\cdot(2k-1)}+\ldots+\frac{f\left(2^{r}\cdot(2k-1)\right)}{2^{r}\cdot(2k-1)}}\), pogrupujmy w ten sposób, żeby do jednej grupki powpadały sumy typu
\(\displaystyle{ 1+\frac{1}{2}+\ldots+\frac{1}{2^{r}}}\) równej długości. A to działa tak: dla liczby nieparzystej \(\displaystyle{ m}\) z przedziału
\(\displaystyle{ \left(\frac{n}{2}, n\right]}\) dostaniemy sumę złożoną z samej jedynki, czyli \(\displaystyle{ \frac{f(m)}{m}}\), a to dlatego, że już \(\displaystyle{ 2m>n}\). Dla każdej liczby nieparzystej z przedziału \(\displaystyle{ \left(\frac{n}{4}, \frac{n}{2}\right]}\) dostaniemy sumę postaci \(\displaystyle{ 1+\frac{1}{2}}\), bo \(\displaystyle{ m\le n, \ 2m\le n}\), lecz już \(\displaystyle{ 4m>n}\). I łatwo to dalej uogólnić w ten sposób, że dla liczby nieparzystej z przedziału \(\displaystyle{ \left(\frac{n}{2^{k}}, \ \frac{n}{2^{k-1}}\right]}\) dostaniemy sumę \(\displaystyle{ \frac{f(m)}{m}+\frac{f(2m)}{2m}+\ldots+\frac{f\left(2^{k-1}m\right)}{2^{k-1}m}=1+\frac{1}{2}+\ldots+\frac{1}{2^{k-1}}}\).
Pozostaje zliczyć liczby nieparzyste w przedziale \(\displaystyle{ \left(\frac{n}{2^{k}}, \ \frac{n}{2^{k-1}}\right]}\). Jak masz odcinek \(\displaystyle{ (a,b], \ a,b>0}\), to znajduje się w nim \(\displaystyle{ \lfloor b\rfloor-\lceil a\rceil+1}\) liczb całkowitych:
\(\displaystyle{ \lceil a\rceil+0, \ \lceil a\rceil +1, \ldots, \lceil a\rceil +(\lfloor b\rfloor-\lceil a\rceil)=\lfloor b\rfloor}\)
Wśród powyższych liczb najwięcej nieparzystych będzie, gdy zarówno \(\displaystyle{ \lceil a\rceil}\), jak i \(\displaystyle{ \lfloor b\rfloor}\) będą nieparzyste, a najmniej nieparzystych – gdy tak \(\displaystyle{ \lceil a\rceil}\), jak i \(\displaystyle{ \lfloor b\rfloor}\) będą parzyste.
Otrzymamy w tych sytuacjach odpowiednio \(\displaystyle{ \frac{1}{2}\left(\lfloor b\rfloor -\lceil a\rceil\right)+1}\) i \(\displaystyle{ \frac{1}{2}\left(\lfloor b\rfloor -\lceil a\rceil\right)}\) liczb nieparzystych.
No to teraz wstawiamy tam te \(\displaystyle{ \frac{n}{2^{k}}, \ \frac{n}{2^{k-1}}}\) i mamy co najmniej
\(\displaystyle{ \frac{1}{2}\left(\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lceil \frac{n}{2^{k}}\right\rceil\right)}\)
zaś co najwyżej
\(\displaystyle{ \frac{1}{2}\left(\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lceil \frac{n}{2^{k}}\right\rceil\right)+1}\)
liczb nieparzystych w przedziale \(\displaystyle{ \left(\frac{n}{2^{k}}, \frac{n}{2^{k-1}}\right]}\)
No i ponieważ \(\displaystyle{ \lfloor x\rfloor \le x, \ lceil x\rceil \ge x}\), więc
\(\displaystyle{ \frac{1}{2}\left(\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lceil \frac{n}{2^{k}}\right\rceil\right)+1\le \frac{n}{2^{k-1}}-\frac{n}{2^{k}}+1}\), a ponieważ
\(\displaystyle{ \lfloor x\rfloor >x-1, \ \lceil x\rceil<x+1 }\), więc
\(\displaystyle{ \frac{1}{2}\left(\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lceil \frac{n}{2^{k}}\right\rceil\right)>\frac{1}{2}\left( \frac{n}{2^{k-1}}-1-\left( \frac{n}{2^{k}}+1\right)\right)\\=\frac{1}{2}\left( \frac{n}{2^{k-1}}- \frac{n}{2^{k}}\right)-1}\)
Oczywiście poza tym jest \(\displaystyle{ \frac{n}{2^{k-1}}-\frac{n}{2^{k}}=\frac{n}{2^{k}}}\).
Z tamtymi poprzednimi oszacowaniami mogłem trochę przesadzić, ale teraz już jest dobrze, idei to nie zmienia.
Czyli mamy
\(\displaystyle{ \frac{1}{n}\sum_{j=1}^{n}\frac{f(j)}{j}=\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}
@\left\{m\in \NN: 2\nmid m \wedge \frac{n}{2^{k}}<m\le \frac{n}{2^{k-1}}\right\}\cdot \sum_{i=0}^{k-1}\frac{1}{2^{i}}}\)
oraz
\(\displaystyle{ \frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}\left( \frac{n}{2^{k+1}}-1\right) \sum_{i=1}^{k-1}\frac{1}{2^{i}}\\<\frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}@\left\{m\in \NN: 2\nmid m \wedge \frac{n}{2^{k}}<m\le \frac{n}{2^{k-1}}\right\}\cdot \sum_{i=1}^{k-1}\frac{1}{2^{i}}\\\le \frac{1}{n}\sum_{k=1}^{\lfloor \log_{2}n\rfloor+1}\left(\frac{n}{2^{k+1}}+1\right)\cdot \sum_{i=0}^{k-1}\frac{1}{2^{i}} }\)
i pozostaje zsumować początkowe wyrazy ciągów geometrycznych oraz obliczyć trywialne granice.
Przy czym \(\displaystyle{ @}\) oznacza moc zbioru, niestety hasz mi nie wchodzi (to się jakoś omijało w LaTeX-u, ale już nie pamiętam, jak).
Wynik wynosi, jak napisałeś, \(\displaystyle{ \frac{2}{3}}\).
Można się domyślić. Z książek z zadaniami (ja mam na przykład „Wędrówki po krainie nierówności" Kourliandtchika, „Elementary ineqaulities" Mitrinovića itd. – takie rzeczy to w antykwariatach, na portalach typu alledrogo itd. bo rzadko są wznawiane – i ze studiów np. trudne zbiorki do analizy Kaczor, Nowak), starych konkursów (tutaj masz gigantyczną bazę:pkrwczn pisze:A tak przy okazji, to zastanawia mnie czasami, skąd pan mol_ksiazkowy bierze te zadania.
Kod: Zaznacz cały
https://www.imomath.com/index.php?options=2&lmm=0
Dodano po 2 minutach 33 sekundach:
Wiesz, co się liczy? SZACUNEK LUDZI ULICY!!!
Kod: Zaznacz cały
https://www.youtube.com/watch?v=612ObQ5iZ-4
-
- Użytkownik
- Posty: 22233
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3759 razy
Re: Ciekawa granica
Nie odczytałeś kontekstu...pkrwczn pisze: ↑12 sie 2020, o 15:43Pan mol_ksiazkowy zapodaje bardzo interesujące problemy matematyczne. Na niektóre nikt nie potrafi znaleźć rozwiązań. Mnie się nie podoba, jak pan się wyraża wobec innych użytkowników.
18000 postów to najwidoczniej za mało, żeby się nauczyć szacunku. Nie wiem, co się dzieje w pana głowie, ale ja z politowaniem i smutkiem obserwuję forum, które uwielbiem, kiedy pan bezmyślnie odpycha innych użytkowników i się z nich śmieje.
Matematyka jest dziedziną trudną, wymagającą, skomplikowaną i piękną. Ja zawsze będę tylko uczniem. Każdy matematyk będzie zawsze tylko uczniem.
Matematyka jest piękna, a my (my wszyscy), mamy szczęście, że mamy szansę się tym pięknem podzielić.
Może pan też się tym chciałby podzielić.
Gdy przygotowywaliśmy z kolegą nasz zbiór ciekawych zadań (a było to w czasach przedinternetowych), to postępowaliśmy tak samo: lataliśmy od czasopisma do czasopisma, od książki do książki, żeby wybrać te najciekawsze smaczki. Dziś do tych źródeł dochodzą liczne fora, więc jest pewnie łatwiej.
Tekstu o braku szacunku nie będę komentował, bo to OT
-
- Administrator
- Posty: 34342
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
- mol_ksiazkowy
- Użytkownik
- Posty: 11473
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3157 razy
- Pomógł: 748 razy
Re: Ciekawa granica
Ross Honsberger - From Erdős to Kiev Problems of Olympiad CaliberNiemniej jednak super byłoby, gdyby mol_ksiazkowy podawał częściej źródła