[LXI OM] I etap

[Swistak]

to IMHO rozwiązanie zadań 1, 2 i 3 razem jest łatwiejsze niż rozwiązanie najłatwiejszego zadania sprzed roku, jednak myślę, że próg nie powinien przekroczyć 40 punktów. Inne zadania nie są już takie proste jak I seria.

IMO tak Ci się tylko wydaje, bo w zeszłym roku byłeś dużo słabszy a tak samo było wiele prościutkich zadanek np. 3,4,5

Akurat ile razy to mówiłem, to zawsze dodawałem "Wiem, że teraz jestem lepszy, ale mimo tego nadal tak twierdzę.", tylko akurat tu zapomniałem . A ty nadal nie umiesz przyjąć do wiadomości, że 5 zadanie było jednym z najtrudniejszych zadań rok temu xD. Rozwiązanie zadania 3 było w zasadzie dość złożone, a 4 też nie było takie oczywiste. Moim zdaniem gdybym miał typować najłatwiejsze zadania sprzed roku, to to zdecydowanie byłyby zadania 9 i 10. Dla mnie łączna trudność zadań 1, 2 i 3, to trudność zadania 1, a to bez najmniejszych wątplipości jest łatwiejsze niż wszystkie ubiegłoroczne zadania ;P.

[patry93]

Swistak - inaczej postrzegasz trudność zadań. Dowodem na to może być Twoje stwierdzenie, że 3. było łatwe.

[Dumel]

A ty nadal nie umiesz przyjąć do wiadomości, że 5 zadanie było jednym z najtrudniejszych zadań rok temu xD.

dla mnie było najłatwiejsze, nawet łatwiejsze od dwóch pozostałych które wymieniłem (coś na poziomie tegorocznego zad. 4.) a punktów za nie było mało, bo pewnie mało komu się chciało to ładnie opisać i sporo osób strzelało blefa w końcówce (że nie można dołożyć żadnego zbioru). a żeby nikt mi nie wkręcał że się przechwalam napisze że 10. robione całkowicie bez trygonometrii było IMO jednym z trudniejszych zadań (wiem wiem śmiech na sali )

[jerzozwierz]

Każdy inaczej postrzega trudność zadań. Na przykład ja, zadanie nr 4, dla niektórych "dość łatwe", uważam za naprawdę trudne, jedno z trudniejszych jakie kiedykolwiek zrobiłem. Po pierwsze, dlatego, że na pomysł nie jest wpaść łatwo. Po drugie, od pomysłu do zrealizowania jest dłuższa droga niż w typowym zadaniu olimpijskim. Swoją drogą po zrobieniu takiego zadania satysfakcja jest znacznie, znacznie większa
PS. jeszcze co do zeszłorocznego 3, to uważam rozwiązanie (przynajmniej moje) za dość złożone, ale stosunkowo proste z jednego powodu - wystarczało wypisać wszystkie możliwe kąty
co do 5 - wystarczyło sobie wyobrazić stosy i udowodnić że zmieniając podstawę nic się nie zmieni, ogólnie dość łatwe xd

[xiikzodz]

Jak ktoś słusznie zauwazył w 3 mogą być redukcje za zapis. Jedną z metod poprawnego zapisu prezentowanego tu kilkakrotnie pomysłu jest naturalne przyporządkowanie każdemu ciągowi liczby w systemie dziesiętnym i zauważenie, że wykonanie opisanej tu wielokrotnie operacji zamiany cyfr zmniejsza tę liczbę. Liczby naturalne są ograniczone z dołu, więc można wykonać jedynie skończenie wiele zmniejszeń, zaś końcowa liczba musi być już posortowana, bo inaczej dałoby się ją zmniejszyć. Znaczy się argument z półniezmiennikiem, w gruncie rzeczy dowód poprawności sortowania bąbelkowego.

inne podejście:    

A samo zadanie powiada oczywiście, że grupa *), w której każdy element ma rząd 2 jest przemienna, z czym nie mają kłopotu studenci na pierwszych ćwiczeniach z algebry - wniosek z tego taki, że samo przyswojenie pojęcia grupy starcza, by to zadanie stało się mechaniczne.

W związku z powyższym można to zadanie inaczej rozwiązać, zupełnie bez przestawiania. Wiedząc, że klasy abstrakcji tych ciągów tworzą grupę wystarczy zauważyć, że istnieje epimorfizm tej grupy na produkt 10-ciu kopii grupy cyklicznej 2-elementowej, którego jądro jest trywialne, czyli izomorfizm. Z kolei grupę cykliczną 10-elementową można zobaczyć jako zbiór wszystkich wektorów postaci \(\displaystyle{ (\varepsilon_1,...,\varepsilon_{10})}\) dla \(\displaystyle{ \varepsilon_i=\pm 1}\) z mnożeniem po współrzędnych. Na koniec koniec zauważamy, że \(\displaystyle{ (\varepsilon_1,...,\varepsilon_{10})=(\varepsilon_1,1,...,1)\cdot(1,\varepsilon_2,1,...,1)\cdot...\cdot(1,,...,1,\varepsilon_{10})}\). To rozwiązanie korzysta z definicji grupy i z twierdzenia o izomorfizmie, do którego nie potrzebne jest żadne "przestawianie".

*) Niby grupoid, ale element odwrotny gwarantuje rząd 2, zaś element neutralny sobie dodajemy w formie ciągu pustego.

[Wuja Exul]

Zgodzę się z Waszą opinią, że zadania 1-3 były łatwe. Jest to celowe działanie KZ, mające zwiększyć spadającą ostatnimi czasy liczbę uczestników. Działa to na zasadzie "zrobiłem 3 zadania, może zrobię kolejne 6".

Wstrzymałbym się z komentarzami typu "łatwiejsze niż najłatwiejsze zadanie z zeszłego roku" czy "nie powinny znaleźć się na OM". Komuś może zrobić się przykro, jeśli cieszył się z trzech zrobionych zadań, a tu piszą, że były wyjątkowo łatwe. Poza tym moim zdaniem OM potrzebuje również paru 'szkolnych' zadań, przynajmniej na I stopniu.

Ktoś pisał "dobry blef nie jest zły", ale uwaga - członkowie Komitetów Okręgowych również czytają to forum i być może uczuliłeś ich na tego typu ściemę. A przynajmniej mnie - dzięki!
Jeśli dostałeś 6 punktów za źle rozwiązane zadanie, to gratulacje. Być może Twoje ściemy prowadziły po małych modyfikacjach do dobrego rozwiązania, tylko po prostu tego nie widziałeś. Albo należysz do okręgu [autocenzura].

Powodzenia wszystkim w rozwiązywaniu zadań z kolejnych serii.

[danioto]

Prostując szerzącą się plotkę o blefie, to chcę zaznaczyć, że to był żart. Dość ironiczny (nawet auto) i może z pozoru na taki nie wyglądający, ale tylko żart. Oczywiście wiem, że dałem niezłą ściemę, lecz "Polak mądry po szkodzie", a moja reakcja była uwarunkowana głęboką niechęcią do wszelkiego typu wypowiedzi "ordynarny blef"...
A co do moich "blefów" ubiegłorocznych, to jeden z uczestników chciał (przynajmniej w mojej opinii) pokazać swoją i swojego rozwiązania wyższość nade mną, więc mi wkręcał blefa o blefie, a ja młody, głupi byłem i uwierzyłem. Aż tu nagle się okazuje 6 punktów. Jestem całkiem świadomy, gdzie takowe blefy u mnie występują, a gdzie nie. A co do zadań, to chyba nie tylko mi przydałoby się trochę wobec nich pokory...

[karolina668]

a ja jako dziewczyna, z załozenia podobno o umysle mniej "matematycznym" niż umysł męski, czego dowodzi chociażby stosunek chłopców do dziewcząt w kalsach mat-fiz, jak również ilość dziewczyn na OMie, to zrobiłam zad. 1,2 i 4 i jestem z tego faktu bardzo zadowolona. Zadanie 3 natomiast, było, jest i zapewne pozostanie dla mnie niepojęte w swej istocie..
W każdym razie jak przeczytalam ze "zadanie 3 jako jedyne zajęło mi więcej niż 5 min" (wypowidź utrzymana w tonie nie bez przechwalania się!) to musze stwierdzić, że komentarze o "banalności" i "oczywistościach" działają bardzo demotywująco. Rozumiem, że na tym forum są pewnie sami geniusze, ale miejscie litość dla zwykłych śmiertelników...
A trudność czy łatwość konkretnego zadania czy czegokolwiek innego jest względna - bo jest to po prostu subiektywna ocena konkretnej osoby....

Pozdrowienia dla szanownych Panow

[Qń]

Jak ktoś słusznie zauwazył w 3 mogą być redukcje za zapis.

Oprócz proponowanego przez Ciebie uściślenia, może być jeszcze na przykład taki argument, że każda permutacja jest złożeniem inwersji, zatem jeśli możemy na danym ciągu dokonywać inwersji, to możemy też otrzymać jego dowolną permutację.

Q.

[paladin]

Jak ktoś słusznie zauwazył w 3 mogą być redukcje za zapis. Jedną z metod poprawnego zapisu prezentowanego tu kilkakrotnie pomysłu jest naturalne przyporządkowanie każdemu ciągowi liczby w systemie dziesiętnym i zauważenie, że wykonanie opisanej tu wielokrotnie operacji zamiany cyfr zmniejsza tę liczbę. Liczby naturalne są ograniczone z dołu, więc można wykonać jedynie skończenie wiele zmniejszeń, zaś końcowa liczba musi być już posortowana, bo inaczej dałoby się ją zmniejszyć. Znaczy się argument z półniezmiennikiem, w gruncie rzeczy dowód poprawności sortowania bąbelkowego.

inne podejście:    

A samo zadanie powiada oczywiście, że grupa *), w której każdy element ma rząd 2 jest przemienna, z czym nie mają kłopotu studenci na pierwszych ćwiczeniach z algebry - wniosek z tego taki, że samo przyswojenie pojęcia grupy starcza, by to zadanie stało się mechaniczne.

W związku z powyższym można to zadanie inaczej rozwiązać, zupełnie bez przestawiania. Wiedząc, że klasy abstrakcji tych ciągów tworzą grupę wystarczy zauważyć, że istnieje epimorfizm tej grupy na produkt 10-ciu kopii grupy cyklicznej 2-elementowej, którego jądro jest trywialne, czyli izomorfizm. Z kolei grupę cykliczną 10-elementową można zobaczyć jako zbiór wszystkich wektorów postaci \(\displaystyle{ (\varepsilon_1,...,\varepsilon_{10})}\) dla \(\displaystyle{ \varepsilon_i=\pm 1}\) z mnożeniem po współrzędnych. Na koniec koniec zauważamy, że \(\displaystyle{ (\varepsilon_1,...,\varepsilon_{10})=(\varepsilon_1,1,...,1)\cdot(1,\varepsilon_2,1,...,1)\cdot...\cdot(1,,...,1,\varepsilon_{10})}\). To rozwiązanie korzysta z definicji grupy i z twierdzenia o izomorfizmie, do którego nie potrzebne jest żadne "przestawianie".

*) Niby grupoid, ale element odwrotny gwarantuje rząd 2, zaś element neutralny sobie dodajemy w formie ciągu pustego.

Szczerze mówiąc, nie widzę w tym zadaniu działania grupy, a już zupełnie nie widzę, w jakim kontekście pojawia się liczba 10. Możesz przybliżyć swoje rozwiązanie od początku?

Co do półniezmiennika - można też liczyć tak zwane inwersje, czyli pary elementów takich, że większy stoi przed mniejszym. Odpowiednie przestawienie zmniejsza liczbę inwersji o 1, kiedyś zatem dojdziemy do zera, czyli do ciągu niemalejącego.
Ale, jak już jesteśmy przy sortowaniu bąbelkowym, chyba bardziej przekonuje argumentacja "najpierw najlżejszy na początek, potem drugi najlżejszy etc." Od tego sortowanie wzięło swoją nazwę

[xiikzodz]

Szczerze mówiąc, nie widzę w tym zadaniu działania grupy, a już zupełnie nie widzę, w jakim kontekście pojawia się liczba 10.

Zamiast 10 wstaw sobie liczbę n różnych elementów danego ciągu i użyj n-tkowego systemu pozycyjnego i alternatywnym rozwiązaniu też zamień sobie 10 na n. O działaniu grupy w tej alternatywnej propozycji rozwiązania nie ma mowy.

[paladin]

Eee, mnie uczono, że grupa powinna mieć jakieś działanie

[xiikzodz]

Tu działaniem grupowym, czego nie należy mylić z działaniem grupy, bo tylko gramatycznie wygląda to na to samo, jest sklejanie ciągów (a dokładniej ich klas równoważności). Na przykład:

\(\displaystyle{ abc\cdot pq=abcpq}\)

[paladin]

Oj, odróżniam jedno od drugiego, spokojnie. Faktycznie, świetny pomysł, aczkolwiek można go uciąć już po stwierdzeniu "grupa ma rząd 2, więc jest przemienna, czyli ciąg możemy permutować jak chcemy..." Oraz nie unikniemy argumentowania, że działanie na klasach abstrakcji jest dobrze zdefiniowane.
Ale kiedy już się to zobaczy, przestaje się myśleć o tym zadaniu jako o "dziwnym triku" i zaczyna się widzieć stojącą za nim matematykę. Gratulacje zatem

[edit] Miało być "grupa ma wszystkie elementy o rzędzie 2". Bardzo skrót myślowy

[xiikzodz]

To znaczy uciąć można powiadając, "w grupie każdy element ma rząd 2, wobec tego grupa jest przemienna" zauważywszy wcześniej, że rzeczywiście chodzi o grupę. Przy czy w takim rozwiązaniu w domyśle korzystamy z tego, że w grupie przemiennej można sobie przestawiać (generatory), co zasadniczo sprowadza się do tego samego. Za to to alternatywne rozwiązanie używa innych technik.

Przy okazji poprawka rozwiązania (alternatywnego) z grupami:

Ukryta treść:    

Wiedząc, że klasy abstrakcji tych ciągów tworzą grupę (po dodaniu ciągu pustego) wystarczy zauważyć, że istnieje epimorfizm tej grupy na produkt n kopii grupy cyklicznej 2-elementowej, którego jądro jest trywialne, czyli izomorfizm. Z kolei produkt n grup cyklicznych 2-elementowych można zobaczyć jako zbiór wszystkich wektorów postaci \(\displaystyle{ (\varepsilon_1,...,\varepsilon_n)}\) dla \(\displaystyle{ \varepsilon_i=\pm 1}\) z mnożeniem po współrzędnych. Na koniec zauważamy, że \(\displaystyle{ (\varepsilon_1,...,\varepsilon_n)=(\varepsilon_1,1,...,1)\cdot(1,\varepsilon_2,1,...,1)\cdot...\cdot(1,,...,1,\varepsilon_n)}\).