X OMG

[Ukasz wojtek]

Finał już jutro, więc jakie zadania obstawiacie?

[enedil]

Finał już jutro, więc jakie zadania obstawiacie?

Mimo, że w tym roku nie biorę udziału...
1. Teoria liczb - raczej łatwa
2. dosyć trudna plani
3. Kombinatoryka
4. Jakaś nierówność
5. Zadanie na Twierdzenie OMG'a.

[Swistak]

Tymczasowy link do zadanek:

Kod: Zaznacz cały

https://www.dropbox.com/s/9bay5wx9kyt6f

... 7.jpg?dl=0
Nie ma to jak łatwe zadania na OMG. Drugie zajęło mi więcej czasu niż dowolne zadanie z finału OM, a się nie przyzwyczaiłem do tego, że zadania z OMG zajmują mi więcej niż minutę xD. Pewnie da się jakoś łatwiej niż ja robiłem, ale moje rozw. jest powalone xd. Piątego też jeszcze nie mam, choć nie siedziałem nad nim jeszcze tak długo jak nad 2.

Szkic 2:    

Indukcyjnie po \(\displaystyle{ k}\) dowodzimy, że tym samym kolorem są pomalowane wszystkie liczby podzielne przez \(\displaystyle{ 2}\) nie większe niż \(\displaystyle{ 2^k + 2}\) oraz takie podzielne przez \(\displaystyle{ 4}\) nie większe niż \(\displaystyle{ 2^{k+1}}\). Jak przechodzimy do większego \(\displaystyle{ k}\) i bierzemy liczbę \(\displaystyle{ n}\) podzielne przez \(\displaystyle{ 4}\) nie większą niż \(\displaystyle{ 2^{k+2}}\), to jak jest postaci \(\displaystyle{ 8m+4}\) to je mam, bo \(\displaystyle{ 8m+4=2(4m+2)}\), a \(\displaystyle{ 2 + (4m + 2) = 4m + 4}\) jest podzielne przez \(\displaystyle{ 4}\) i jest nie większe niż \(\displaystyle{ 2^{k+1}}\), a jak jest postaci \(\displaystyle{ 8m}\), to \(\displaystyle{ 8m=4 \cdot 2m}\), zatem to mam, bo \(\displaystyle{ 4 + 2m \le 2^k +4}\), a takie wszystkie parzyste liczby też już mam . Jak \(\displaystyle{ n =2m \le 2^{k+1} + 2}\), to \(\displaystyle{ n = 2 + (2m-2)}\), i to mam, bo mam \(\displaystyle{ 2(2m-2) = 4m-4}\), bo jest podzielne przez \(\displaystyle{ 4}\) i jest \(\displaystyle{ \le 2^{k+2}}\). Zatem teza indukcyjna dowiedziona XD. Jak mam wszystkie parzyste, to oczywiście mam wszystkie.
Tak na boku, to warto zadbać o bazę, bo oczywiście \(\displaystyle{ 2}\) i \(\displaystyle{ 4}\) są z całej gry wyłączone, zatem ręcznie do jakichś \(\displaystyle{ 16}\) można sobie porozpisywać, aby było bezpiecznie (nie mam ochoty w szczegółową analizę bazy się babrać w tej chwili)

[kuba99]

Jak poszło? Wg mnie 1 banalne ale sposób zapisu na 6 pkt już niekoniecznie 2 brak pomysłu 3. Fajne, Ale jak będzie wyglądać wzorcowa? 4 Dobre jak na finał 5 bryła jak zwykle istnieje ale jak ja znaleźć? Ogólnie najtrudniejsze zadania finałowe od paru lat. Próg na laureata nie powinien być duży.

[gus]

Wg mnie 1 banalne ale sposób zapisu na 6 pkt już niekoniecznie

Ukryta treść:    

1. Liczba parzysta\(\displaystyle{ =2+}\) liczba parzysta(złożona)
2. Liczba nieparzysta\(\displaystyle{ =3+}\) liczba parzysta(złożona)

[marcin7Cd]

Jest "ładniejsze" rozwiązanie drugiego

Ukryta treść:    

Sprawdzam, że dla liczb mniejszych od 8 działa. Załóżmy indukcyjnie, że dla liczb mniejszych od \(\displaystyle{ 4k}\), gdzie \(\displaystyle{ k \ge 2}\) wszystkie są pokolorowane tym samym kolorem. Dla przejrzystości oznaczę, że jeśli \(\displaystyle{ a \leftrightarrow b}\) to te liczby mają ten sam kolor. Zależność z zadania to \(\displaystyle{ ab \leftrightarrow a+b}\). Rozważmy przypadki:
1) \(\displaystyle{ 4 \cdot k \leftrightarrow 4+k}\), a \(\displaystyle{ 4k=k+3k \ge k+6>k+4}\),więc założenia indukcyjnego jest pokolorowane tym samym kolorem, co reszta
2)
\(\displaystyle{ 4k+1=2k+(2k+1) \leftrightarrow 2k(2k+1)=k(4k+2) \leftrightarrow 5k+2=4k+(k+2) \leftrightarrow 4k(k+2)=2k(2k+4) \leftrightarrow 4k+4=4(k+1) \leftrightarrow k+5}\)
,a \(\displaystyle{ 4k+1=k+3k+1 \ge k+6+1>k+5}\)
3)
\(\displaystyle{ 4k+2=2(2k+1) \leftrightarrow 2k+3}\), a \(\displaystyle{ 4k+2=2k+2k+2 \ge 2k+4+2>2k+3}\)
4)
\(\displaystyle{ 4k+3=(2k+2)+(2k+1) \leftrightarrow (2k+2)(2k+1)=(k+1)(4k+2) \leftrightarrow 5k+3=2k+(3k+3) \leftrightarrow 2k(3k+3)=6k(k+1)=3k(2k+2) \leftrightarrow 5k+2=4k+(k+2) \leftrightarrow 4k(k+2)=2k(2k+4) \leftrightarrow 4k+4=4(k+1) \leftrightarrow k+5}\)
,a \(\displaystyle{ 4k+3=k+3k+3 \ge k+6+3>k+5}\)
To udowadnia, że każda liczba mniejsza od \(\displaystyle{ 4k+4}\) jest pokolorowana tym samym kolorem, co kończy dowód

[Swistak]

Huh, no być może jak się prześledzi te wszystkie rachunki, to rzeczywiście wyjdzie, ale z tym 4k+1 i 4k+3 to jakaś masakra zupełna. Otóż okazuje się, że istnieje rozwiązanie w jednej linijce:

Krótkie 2:    

\(\displaystyle{ n \leftrightarrow 2n-4 \leftrightarrow 4n-12 \leftrightarrow n+1}\)

;___;

Istotnie takiemu rozwiązaniu nie da się odmówić poprawności, jednak idealnie do niego moim zdaniem pasuje określenie "randomowe". Nie istnieje ciąg myślowy, który byłby w stanie naprowadzić na akurat takie rozwiązanie. Gdy ja rozwiązywałem to zadanie, to starałem się używać swojego mózgu, co najwyraźniej było błędem. Najpierw chciałem to wykazywać indukcyjnie "grupami", ale zauważyłem, że mi się sypie dla liczb pierwszych, to je wywaliłem z tezy indukcyjnej, ale wtedy założenie indukcyjne było zbyt słabe, aby wykazać tezę. Potem starałem się explicite wskazać ścieżkę między dwoma dowolnie wskazanymi liczbami. Miałem zabawny dowód, że każda liczba jest połączona z pewną potęgą dwójki, jednak nie byłem w stanie wykazać, że potęgi dwójki są połączone ze sobą. Wróciłem do tezy indukcyjnej, wykoksiłem ją i jakoś się udało, nawet używając względnie mało obliczeń. Istotnie byłem rozczarowany, gdy mój kolega pokazał mi to rozwiązanie, które tutaj napisałem. Ten ciąg połączeń rzeczywiście nie jest bardzo długi i da się do niego dojść drogą eksperymentów, ale mi się jakoś to nie udało. Czy mam się z tego powodu czuć gorszy ?
Zadanie piąte bardzo podobnie - ponownie nie widzę żadnej motywacji, która mogła stać za dojściem do rozwiązania. Trzeba je w zasadzie od razu "zgadnąć w całości", no i na koniec chwilę się zastanowić, czemu taki wielościan istnieje. Tutaj, w przeciwieństwie do 2., samemu w ogóle nie podołałem i rozwiązałem dopiero po istotnej podpowiedzi timona.
Całkowicie poważnie mówię, że dla mnie 2. i 5. były istotnie trudniejsze niż dowolne zadanie z finału licealnej olimpiady. Sęk w tym, że trudność w licealnych zadaniach, jakkolwiek niska by ona nie była, kryła się w umiejętności przeprowadzania logicznych ciągów rozumowań (jak to w matematyce często bywa ), a tutaj w zgadywaniu... Wiadomo, że w matematyce niewątpliwie czasami potrzeba też dobre intuicje albo tzw. pomysły z czapy i nie do wszystkiego prowadzi idealnie umotywowana dedukcja, ale tutaj było to widoczne wybitnie silnie.

[matma_matma]

Nie istnieje ciąg myślowy, który byłby w stanie naprowadzić na akurat takie rozwiązanie. Gdy ja rozwiązywałem to zadanie, to starałem się używać swojego mózgu

Drogi Świstaku to, że Twój mózg, którego starałeś się używać nie wygenerował ciągu myślowego doprowadzającego Cię do tego rozwiązania nie znaczy, że takowy ciąg nie istnieje, co próbujesz udowodnić z powodu bólu ****, że nie wpadłeś na to eleganckie rozwiązanie.

A oto dowód czyli ciąg myślowy, który mnie doprowadził do tego rozwiązania:

Na wstępie można wywnioskować, że pięknie by bylo gdybyśmy znaleźli ścieżkę między dwoma dowolnymi liczbami. Wychodząc od liczby \(\displaystyle{ n}\) musimy ją przedstawić jako sumę dwóch liczb albo iloczyn dwóch liczb. Od razu widać, że opcja iloczynu odpada jeśli \(\displaystyle{ n}\) jest pierwsza, więc przedstawmy ją w postaci sumy jednak nie jako \(\displaystyle{ n=x+y}\) tylko jako \(\displaystyle{ n=(n-x)+x}\) żeby liczba którą otrzymamy zawierała w sobie \(\displaystyle{ n}\) w "czystej" postaci. Tą liczbą jest \(\displaystyle{ x(n-x)}\). Jako, nie chce się zagłębiać w dzielniki \(\displaystyle{ x}\) ani \(\displaystyle{ n-x}\) (dopóki nie będe musiał) to przedstawiam ją w postaci sumy w "analogiczny" sposób, czyli jako \(\displaystyle{ [x(n-x)-y]+y}\) otrzymując jako kolejną na ścieżce liczbę \(\displaystyle{ xyn- yx^{2}- y^{2}}\). Łatwo zauważyć, że jeśli \(\displaystyle{ y=x}\) to pięknie nam \(\displaystyle{ x^{2}}\) wychodzi przed nawias i kolejną liczbą którą otrzymujemy na ścieżce jest \(\displaystyle{ n+ x^{2}-x-1}\) czyli jesteśmy w domu, bo dla \(\displaystyle{ x=2}\) jest to \(\displaystyle{ n+1}\) czyli jest ścieżka od dowolnej \(\displaystyle{ n}\) do \(\displaystyle{ n+1}\) czyli wszystkie są jednego koloru

[Sylwek]

Brawo! Świetnie przedstawione rozumowanie, matma_matma.

[Swistak]

Sorry xD. Mi raczej nie chodziło o ból **** (tym bardziej, że moje rozwiązanie też mnie satysfakcjonuje w miarę) tylko trochę hejt na styl zadania, ale widzę, że jednak zbyt pochopnie to wszystko oceniłem i się myliłem . Tym bardziej byłem utwierdzony o "randomowości" tego rozwiązania, bo jak spytałem kolegi, jak do niego doszedł to właśnie wyglądało to jak zlepek kilku randomowych myśli, które przypadkiem się złożyły w całość .

Rzeczywiście tak jak to przedstawiasz, to wygląda całkiem sensownie. Muszę przyznać, ze podoba mi sposób w jaki motywujesz swoje kolejne kroki, tzn. że startując z pierwszej iloczynem wiele nie zdziałamy i podobnie ciężko coś nim zdziałać mając \(\displaystyle{ x(n-x)}\). Choć dla pewnych konkretnych wartości \(\displaystyle{ x}\) być może coś by się dało, ewentualnie być może jakaś analiza reszt z dzielenia \(\displaystyle{ n}\) przez coś by coś dała, ale z takim stanem informacji ciężko coś a priori stwierdzić i rzeczywiście ponowne zastosowanie rozbicia na sumę brzmi sensowniej (co w zasadzie też podobnie zaargumentowałeś), a stamtąd już niedaleko.