[Rozgrzewka OM][MIX] Łańcuszek olimpijski

[kp1311]

Ukryta treść:    

Jeśli \(\displaystyle{ u,v,t}\) są pierwiastkami pierwszego wielomianu to, na podstawie wzorów vieta i odpowiednich przekształceń możemy dojść do tego że \(\displaystyle{ \frac{u+v}{2}, \frac{u+t}{2}, \frac{v+t}{2}}\) są pierwiastkami drugiego wielomianu.

Chcąc wbić po gwoździu w każdy z kilkudziesięciu słupów rozstawionych w równych odstępach wzdłuż drogi najlepiej zacząć od pierwszego a skończyć na ostatnim. Ale jak zrobić to samo najgorzej, to znaczy tak aby przebyta droga była jak najdłuższa?

[justynian]

Zacząć od środkowego jeśli liczba jest nieparzysta i poruszać się najpierw do jednego skrajnego potem do jednego za początkowym i tak do wyczerpania, jeśli ilość słupków jest parzysta to wybrać jeden z 2 środkowych i znów do skrajnego tylko że do tego który jest bardziej oddalony a dalej tak jak poprzednio.

dla: \(\displaystyle{ n=2k+1}\) \(\displaystyle{ \Leftrightarrow s= [\frac{n}{2}]n}\)
dla: \(\displaystyle{ n=2k}\) \(\displaystyle{ s= \frac{n^2-2}{2}}\)

Zadanko: \(\displaystyle{ \alpha + \beta +\gamma= \pi}\) ; \(\displaystyle{ \alpha , \beta ,\gamma \in R_+}\)
\(\displaystyle{ cos^2 \frac{ \alpha }{2}+cos^2 \frac{ \beta }{2}+cos^2 \frac{\gamma}{2} \ge 2}\)

[kp1311]

Nie uważasz że podałeś jedynie hipotezę bez uzasadnienia jej?

[justynian]

Cóż zapewne moje ładne rysunki które mogę przefaksowć nie wystarczą , a niestety w chwili obecnej innego nie mam.

[Elvis]

justynian, nie brakuje w twoim zadaniu jakiegoś założenia (zapewne nieujemności)? Tak jak jest chyba nie działa.

[justynian]

tak zapomniałem dodać że \(\displaystyle{ \alpha , \beta ,\gamma \in R_+}\), poprawiam także w poście.

[Wasilewski]

Ukryta treść:    

Wystarczy trochę poprzekształcać lewą stronę:
\(\displaystyle{ cos^{2}(\frac{\alpha}{2}) + cos^{2}(\frac{\beta}{2}) + cos^{2}(\frac{\gamma}{2}) = \frac{3}{2} + \frac{1}{2}(cos(\alpha) + cos(\beta) + cos(\gamma)) = \frac{3}{2} + \frac{1}{2}(2cos(\frac{\alpha + \beta}{2})cos(\frac{\alpha-\beta}{2}) - 2cos^{2}(\frac{\alpha+\beta}{2}) + 1) = 2 + cos(\frac{\alpha+\beta}{2})(cos(\frac{\alpha-\beta}{2}) - cos(\frac{\alpha+\beta}{2})) = 2 + 2cos(\frac{\alpha+\beta}{2})sin(\alpha)sin(\beta)\ge 2}\).

Niech nowym zadaniem będzie uczciwe uzasadnienie odpowiedzi do zadania kp1311.
Jak się nie uda w skończonym czasie, to dam coś innego.

[kp1311]

Zadanie zablokowało łańcuszek, myślę że mógłbyś wrzucić coś innego.

[Wasilewski]

Ok, niech więc będzie takie coś:
Znaleźć wszystkie funkcje \(\displaystyle{ f: \mathbb{R}_{+} \cup \{0\} \rightarrow \mathbb{R}_{+}\cup \{0\}}\) ciągłe w zerze oraz spełniające nierówność:
\(\displaystyle{ f\left(\frac{x+y}{x+y+1}\right) \ge f(x) + f(y)}\).

[Swistak]

Ej no, przecież to zadanie ze słupkami wcale nie jest trudne xp. Oznaczmy liczbę słupków przez n. Załóżmy, że jest ona parzysta. Wtedy twierdzę, że optymalną strategią jest startowanie ze słupka o numerze n, pójście do któregokolwiek słupka o numerze z przedziału \(\displaystyle{ [n+2; 2n]}\), potem do któregokolwiek słupka o numerze z przedziału \(\displaystyle{ [1; n-1]}\), potem znowu do któregokolwiek słupka o numerze z przedziału \(\displaystyle{ [n+2; 2n]}\) itd. kończąc na słupku n+1. Policzmy przebytą drogę licząc dla każdego odcinka między dwoma słupkami ile razy został on przebyty. Załóżmy, że po jego lewej stronie jest \(\displaystyle{ l}\) słupków, a po prawej \(\displaystyle{ p}\) przy czym \(\displaystyle{ l<p}\). Zauważmy, że dla każdego z \(\displaystyle{ l}\) słupków po lewej kiedyś do niego doszliśmy idąc od słupka z prawej połówki, a potem zawróciliśmy idąc do słupka z prawej strony. Zatem ten odcinek przeszliśmy \(\displaystyle{ 2l}\) razy i więcej nie mogliśmy. Analogicznie rozumowanie można przeprowadzić dla każdego innego odcinka poza środkowym. Na chwilę dodajmy do naszej ścieżki jeszcze jeden odcinek, między dwoma środkowymi słupkami. Wtedy nasze rozumowanie można powtórzyć także dla środkowego odcinka, a więc łącznie (razem z tym odcinkiem) przebyliśmy \(\displaystyle{ 2+4+6+...+(n-2)+n+(n-2)+...+6+4+2=\frac{n^{2}}{2}}\) Odejmując jeden dodany odcinek otrzymujemy odpowiedź \(\displaystyle{ \frac{n^{2}-2}{2}}\). Trzeba jeszcze udowodnić, że nie da się więcej. Otóż więcej dałoby się tylko wtedy, gdyby każdy odcinek został przebyty \(\displaystyle{ 2 \cdot max(l_{i}, p_{i})}\), gdzie te liczby oznaczają ile słupków jest na lewo i prawo od i-tego odcinka, jednak zauważmy, że wykonujemy \(\displaystyle{ n-1}\) przejść między słupkami, więc środkowy odcinek możemy przejść co najwyżej n-1 razy.
Można to także inaczej sformułować: Chodząc z lewej do prawej połówki naszą drogę kończąc na słupku o numerze \(\displaystyle{ n+s}\) łącznie przebyjemy \(\displaystyle{ \frac{n^{2}}{2} -s}\), bo po prostu dla s odcinków między słupkami od \(\displaystyle{ n}\) do \(\displaystyle{ n+s}\) istnieje słupek po prawej stronie (dokładnie ten o numerze n+s), z którego nie wrócimy do lewej połówki, a więc przejdziemy je \(\displaystyle{ 2 \cdot (l_{i}, p_{i})-1}\) razy.
c.b.d.u.
Jeżeli n jest nieparzyste, to przeprowadzając analogiczne rozumowanie otrzymujemy odpowiedź \(\displaystyle{ \frac{n^{2}-3}{2}}\)
Nowe zadanie już jest .

[Dumel]

Ok, niech więc będzie takie coś:
Znaleźć wszystkie funkcje \(\displaystyle{ f: \mathbb{R}_{+} \cup \{0\} \rightarrow \mathbb{R}_{+}\cup \{0\}}\) ciągłe w zerze oraz spełniające nierówność:
\(\displaystyle{ f\left(\frac{x+y}{x+y+1}\right) \ge f(x) + f(y)}\).

hmm dziwnie proste i ciągłość niepotrzebna, chyba ze robie jakis blad.
dla \(\displaystyle{ x_y = \frac{-y+ \sqrt{y^2+4y}}{2}}\) mamy
\(\displaystyle{ \frac{x+y}{x+y+1}=x}\) wiec wstawiając \(\displaystyle{ (x,y)=(x_y,y)}\) dostajemy \(\displaystyle{ 0 \ge f(y)}\) wiec \(\displaystyle{ f(y)=0}\) dla dowolnego \(\displaystyle{ y}\)

[Wasilewski]

Ok, odpowiedź dobra, rozwiązanie też na takie wygląda.

[Dumel]

następne zadanko:
dla danych liczb naturalnych \(\displaystyle{ m<n}\) do tablicy \(\displaystyle{ n \times n}\) wpisujemy liczby \(\displaystyle{ 1,2,...,n^2}\). w każdym wierszu kolorujemy na sinofioletowo \(\displaystyle{ m}\) największych liczb. podobnie w każdej kolumnie \(\displaystyle{ m}\) największych liczb kolorujemy kolorem krwistoczerwonym. wyznaczyć największą i najmniejszą możliwą liczbę liczb pomalowanych obydwoma kolorami.

[tkrass]

odpowiedź:    

największa liczba: \(\displaystyle{ mn}\)
najmniejsza liczba: \(\displaystyle{ m}\)

dowodzik:    

że więcej niż \(\displaystyle{ mn}\) nie może być jest dość oczywistym, bo na każdy kolor pomalowanych jest dokładnie \(\displaystyle{ mn}\) liczb. że mniej niż \(\displaystyle{ m}\) nie może być to też w miarę jasne. sposób pomalowania tablicy tak, żeby uzyskać największą liczbę:
bierzemy sobie dowolną permutację ciągu \(\displaystyle{ mn}\) największych liczb wpisanych w tablicę. pierwszą wpisujemy w jakieś pole \(\displaystyle{ (x,y)}\). \(\displaystyle{ m-1}\) następnych wpisujemy kolejno w pola \(\displaystyle{ (x+1,y)}\), \(\displaystyle{ (x+2,y)}\), ..., \(\displaystyle{ (x+m-1,y)}\). kolejną liczbę wpisujemy w pole \(\displaystyle{ (x+1,y+1)}\) i znowu \(\displaystyle{ m-1}\) następnych wpisujemy "za nią" w poziomie. oczywiście jeżeli na przykład \(\displaystyle{ x+1>n}\), to liczbę wpisujemy w pole \(\displaystyle{ x+1 (modn)}\).
innymi słowy: robimy takie schodki modulo n na tablicy. tym sposobem wszystkie liczby należące do schodków są zakolorowane podwójnie, a jest ich\(\displaystyle{ mn}\).
sposób pomalowania tablicy tak, żeby uzyskać najmniejszą liczbę:
to już łatwiejsza sprawa, wpisujemy po prostu w jedną kolumnę liczby od \(\displaystyle{ n^2-n+1}\) do \(\displaystyle{ n^2}\). wtedy w tej kolumnie znajdzie się m liczb dwukolorowych, w pozostałych oczywiście żadnej.

Ponieważ to moje pierwsze rozwiązanie od bardzo bardzo dawna, proszę o sprawdzenie czy nie napisałem jakichś głupstw.

Jeśli jest ok, to nowe:
Wykazać, że każdą naturalną liczbę złożoną można przedstawić w postaci sumy czterech liczb naturalnych \(\displaystyle{ a}\), \(\displaystyle{ b}\), \(\displaystyle{ c}\), \(\displaystyle{ d}\), takich że \(\displaystyle{ ab=cd}\).

[limes123]

Druga czesc dowodu raczej nie jest poprawna. Zobacz sobie dla n=3, m=2. Raczej na m^2 bym stawial, ale nie myslalem jeszcze.