LXII Olimpiada Matematyczna II etap.

[kaszubki]

Kuczeee :/
W tym roku mi nie poszło. Zwaliłem na maxa. Zrobiłem tylko szóste, ale nie dowodziłem tego lematu... Może 2 punkty wpadną.
Jeszcze do piątego miałem fajnego blefa, wyszedł mi

Ukryta treść:    

ciąg rekurencyjny: \(\displaystyle{ f(n)=f(n-1)+2f(n-2)}\), gdzie \(\displaystyle{ f(0)=1}\) i \(\displaystyle{ f(1)=1}\). Mój dowód był nawet przekonywający...
Nawet wyprowadziłem wzór jawny: \(\displaystyle{ f(n) = \frac{1}{3} \cdot ((-1)^{n} + 2^{n+1})}\)

[KPR]

2 na wektorach:

Ukryta treść:    

Wiemy, że \(\displaystyle{ \vec{BP}=\vec{BD}+\vec{DQ}+\vec{QP}}\). Zatem \(\displaystyle{ 2\vec{DQ}+\vec{QP}=\vec{DQ}+\vec{BP}-\vec{BD}}\), zatem \(\displaystyle{ \vec{DM}=\frac{\vec{DQ}+\vec{BP}-\vec{BD}}{2}}\). Analogicznie \(\displaystyle{ \vec{BM}=\frac{\vec{DQ}+\vec{BP}+\vec{BD}}{2}}\). Z warunków zadania mamy \(\displaystyle{ \vec{DM}\circ\vec{BM}=0}\) (\(\displaystyle{ \circ}\) oznacza iloczyn skalarny). Mamy zatem \(\displaystyle{ \frac{\vec{DQ}+\vec{BP}-\vec{BD}}{2}\circ\frac{\vec{DQ}+\vec{BP}-\vec{BD}}{2}=0}\), czyli \(\displaystyle{ (\vec{DQ}+\vec{BP})^2-\vec{BD}^2=0}\), czyli \(\displaystyle{ (\vec{DQ}+\vec{BP})^2=\vec{BD}^2=(\vec{BD}+\vec{AD})^2}\). Jak to rozpiszemy i skrócimy kwadraty (bo odpowiednie wektory są równej długości) to mamy \(\displaystyle{ \vec{AB}\circ\vec{AD}=\vec{BP}\circ\vec{QD}}\), czyli \(\displaystyle{ \cos \angle BAD=-\cos \angle BCD}\)

[Panda]

Heh, ja tylko 5 i jakiś banalny początek 6, choć potem już tylko ponoć indukcja. Jak 4 robiliście? Zadanie wydaje się mieć multum rozwiązań, ja najpierw prosty lemat, i potem bezmyślne pałowanie analizą możliwości:

Ukryta treść:    

Lemat 1 (to nie ten wspomniany wyżej, ale ten z wzorcówki - dowód inny to pokażę) - w każdym dobrym [dobry znaczy zgodny z warunkami zadania] ciągu przynajmniej jedna liczba występuje tylko raz.

Dowód:
Załóżmy nie wprost, dla każdej liczby istnieje inna należąca do ciągu jej równa. Zwróćmy uwagę na dowolną taką parę, Między nimi są elementy, więc są tam też pary. Zwróćmy teraz uwagę na dowolną z nich. Różnica odległości między nimi maleje, a widzimy, że można przeprowadzić analogiczne rozumowanie, zatem można to robić nieskończenie wiele razy, co jest sprzeczne z tym, że odległość maleje - nie może maleć w nieskończoność.

Lemat 2 - jeśli żaden element nie powtarza się dwukrotnie w ciągu (w sensie nie ma trójek a=b=c), to jego długość jest mniejsza bądź równa \(\displaystyle{ 2n-1}\), gdzie n to moc zbioru wartości z ciągu.

Dowód: Oczywisty. Mamy maksymalnie \(\displaystyle{ n-1}\) par, zatem maksymalnie \(\displaystyle{ 2n-1}\) elementów. Faktycznie, jest to możliwe (dowód w firmówce).

Lemat 3 - Jeśli jakiś element powtarza się więcej niż 2 razy w dobrym ciągu, to taki ciąg nie jest dłuższy od najdłuższego ciągu w którym nie ma takich elementów.

Lemat 3a - Lemat 3 zachodzi dla dokładnie jednego takiego elementu.


Rozpatrzmy taki ciąg, w którym tylko jedna liczba się powtarza ponad 2 razy - niech to będzie jedynka. Ponadto przyjmijmy, że jest on najdłuższy możliwy.
Oznaczmy jako \(\displaystyle{ s}\) liczbę jedynek, zaś jako \(\displaystyle{ t_{},t_{2},...,t_{s-1}}\) wszystkie podciągi między kolejnymi jedynkami (rzecz jasna w zadaniu zdefiniowałem inaczej - w ogóle tak tam też paprałem, że ojeju, stąd te 3-4h mi to zajęło - muszę popracować nad tym). Jako t_{s) zaś oznaczmy sumę ciągów przed pierwszą jedynką i za ostatnią. Z treści wynika, że zbiory zawierające elementy z każdego z podciągów są rozłączne. Zatem, jeśli \(\displaystyle{ r_{i}}\) oznaczymy ilość różnych elementów w ciągu \(\displaystyle{ t_{i}}\) (dla \(\displaystyle{ 0 < i < n}\)), to - ponieważ w ciągu tym nie ma równych trójek (z założenia 3a) - jego długość wynosi \(\displaystyle{ 2r_{i}-1}\). Zaś dla ciągu \(\displaystyle{ t_{s}}\) mamy maksymalnie \(\displaystyle{ 2r_{s}}\) elementów, co wynika Dirichleta i braku trójek. Sumując więc długości wszystkich podciągów oraz ilość jedynek, otrzymujemy, że dany ciąg ma długość mniejszą bądź równą \(\displaystyle{ 2r+1}\), gdzie r to ilość różnych liczb nie licząc tej, która się powtarza ponad 2 razy - zatem jeśli n to ilość różnych liczb w ciągu, to jego długość jest mniejsza bądź równa \(\displaystyle{ 2n-1}\), co dowodzi lematowi.

Lemat 3b - Jeśli dobry ciąg zawiera więcej powtarzających się ponad raz elementów, to jego długość nie jest większa od dowolnego innego ciągu o tej samej ilości różnych elementów, ale zawierającego jeden powtarzający się przynajmniej 2 razy element.

Dowód: Pierwsza, dość oczywista rzecz to to, że żadne trójki i większe (pary teeż) się nie "przecinają" - taki ciąg byłby niedobry. Załóżmy najpierw, że inne trójki znajdują się między jedynkami. Podzielmy więc tak jak w lemacie ciąg na podciągi. Każdy albo jest taki jak w lemacie 2, albo taki jak omówiony w 3a, albo taki jak omawiany teraz. W dwóch pierwszych przypadkach sprawa została dowiedziona, w pozostałym możemy przenieść uwagę na taki ciąg, czyli postępować jak w dowodzie lematu 1. Nie możemy jednak nieskończenie tego robić, więc w końcu natrafimy na podciąg taki, jak w lemacie 2 (czyli nie ma trójki takich samych elementów) albo w 3a (czyli jest tylko jeden element powtarzający się wielokrotnie). Zatem dla ciągu, do którego należy teza zajdzie, dla wyższego rzędem też itd. Nie mam już siły bo długo to opisuję, ale wiecie o co chodzi :p Takie nieskończone schodzenie z zawracaniem...

Jeszcze do rozważenia opcja, że inny powtarzający się element jest poza jedynkami, czyli de facto sąsiaduje z ciągiem zawierającym jedynki. Widzimy jednak, że możemy sprytnie i zachowując tezę przekształcić taki ciąg w ciąg omówiony wyżej, jednak o mniejszej liczbie elementów (jeśli to 2 się powtarza dodatkowo, to zmieniamy 2 na 1), otrzymując ciąg lepszy, co przeczy założeniu.

No, tym sposobem spałowałem po wszystkich możliwościach. Na pewno są błędy w zapisie, wprowadziłem ok. 10 oznaczeń, ale to i tak mało i ciągle to samo pisałem.

No cóż, teraz widzę, że na OMa gotowy nie byłem - zatem do zobaczenia za rok na finale (ci co będą mogli) ^^

@Mejczus: Na OMG chyba unikają równań deltorodnych, za łatwo by mieli ci, co potrafią, a nie taka jest idea, przynajmniej OMa, a z OMG chyba podobnie - przynajmniej rok temu tak było.

@KPR: \(\displaystyle{ n \ge 3}\) bodajże, treści wiesz gdzie.

Czółko.

[KPR]

To że \(\displaystyle{ n \ge 3}\) nic nie oznacza, bo teza zadania działa dla wszystkich, to i wzór powinien.-- 19 lut 2011, o 20:55 --Ja z kolei trzecie robiłem tak, że udowodniłem, że na początku i końcu jest to samo, a potem, że jak podzielimy se ten ciąg elementami równymi temu pierwszemu, to każdy element jest maksymalnie w jednej części. Później sumujemy założenie indukcyjne dla każdej części i wychodzi.

[adamm]

O co w końcu chodziło z tą nierównością? Ktoś na forum pisał, że ją zrobił to chyba w którymś okręgu była na zawodach.

Spoko, spoko, nierówność już leci:
\(\displaystyle{ a_{1},a_{2},...,a_{n} \in \mathbb{R}^+}\), \(\displaystyle{ n \in \mathbb{N}^+}\)
\(\displaystyle{ \frac{1}{a_{1}}+\frac{2}{a_{1}+a_{2}}+\frac{3}{a_{1}+a_{2}+a_{3}}+...+\frac{n}{a_{1}+a_{2}+...+a_{n}}< 2\left(\frac{1}{a_{1}}+\frac{1}{a_{2}}+...+\frac{1}{a_{n}}\right)}\)

[KPR]

Nie o tę nierówność chodzi.

[Jerzy_q]

2 na wektorach: ...

Too easy. Niepotrzebnie marnowałem czas szukając jakichś zależności które dałyby \(\displaystyle{ \mathbb{R}}\), jeszcze koniec końców wzory pomyliłem. Trudno, zniszczę ich za rok.

[Panda]

Jak to się nie zgadza...121, 212 <- dłuższego nie ukręcisz, bo albo 1212, albo sąsiedztwo.

[adamm]

Nie o tę nierówność chodzi.

To były dwie?

Ukryta treść:    

No dobra żartowałem, ale niektórzy się tak spinają, że nie mogłem się powstrzymać.

[KPR]

Panda, napisałem to, jak jeszcze było źle.

[johnny]

dla n=2 teza nie dziala bo skoro masz 3 wyrazy w ciagu, to nie mozesz wykreslic wszystkich oprocz czterech...

[Swistak]

Moja SUBIEKTYWNA ocena:
1. Matura
2. Dość trudne, możliwe, że będę dwójkować całej masie osób, która nie zadbała o to, że jakiś punkt ma leżeć po którejś stronie prostej. Na szczęście ja o to zadbałem na zawodach, ale to nie było takie hop-siup, zajęło mi to istotną część czasu. Uważam, że brak tego, co ja miałem lub tego, co było we wzorcówce to dość istotna luka.
3. Wrzucić do maszynki i mamy rozwiązanie - nieskończenie szablonowe
4. Ja się pół godziny patrzyłem jak głupi w te punkty G i H i nie miałem pojęcia jakie ciekawe one mają własności ... Ale na szczęście w końcu padło.
5. Zadanie całkiem spoko, ale niesamowicie głupie w opisie (ja miałem takie rozw. które było jeszcze dużo bardziej opisowe, rozpisałem się na 2 strony A4, co zajęło mi z godzinę, ale i tak wydaje mi się, że nie zrobiłem tego wystarczająco ściśle). Poza tym było tu nieskończenie wiele możliwości puszczenia blefa.
6. Dla mnie to już wyższy poziom hardkoru, nie ogarniam złożeń wielomianów, ale w końcu po długich bólach i mękach udało mi się to zrobić, ale długo po wyjściu z sali sam nie wiedziałem, czy to co napisałem jest dobrze, czy źle ;p. Ale w końcu wyszło na to, że raczej ok. I tu też było nieskończenie wiele możliwości puszczenia blefa.

Podsumowując były moim zdaniem 4 zadania (1, 3, 4, 5) w zasięgu większości przy czym w jednym będzie pewnie sporo blefów, a dość możliwe, że wydwójkują sporej liczbie osób zad. 2. Próg szacuję na 19 pkt.


A propo wzoru na liczbę tych ciągów, to już to poprawiłem, ale widzę, że toczą się ciągle dyskusje:

Ukryta treść:    

\(\displaystyle{ {2n-2 \choose n-1}(n-1)!}\)

[SaxoN]

Oj Swistak, przesadzasz z tym czwartym - nawet mnie udało się to zrobić w n<10 minut (oczywiście poza zawodami - jestem już za stary żeby startować), a nie jestem nieskończenie mocny w geometrii, o czym nie raz już się przekonałem A szóste może nie było trywialne, ale zawodnikowi takiemu jak Ty nie powinno było sprawić takich trudności ^^

[Swistak]

Tylko, że taki zawodnik jak ja był przekonany, że \(\displaystyle{ P(Q(x))=Q(P(x))}\) nie implikuje tego, że \(\displaystyle{ P(Q(S(x)))=Q(P(S(x)))}\), gdzie S jest jakiśtam wielomianem i zdał sobie sprawę, że to istotnie zachodzi, pół godziny temu .
A co do 4, to może nie napisałem tego wyraźnie, ale jednak to było prościutkie zadanie, trochę żal, że tyle nad tym siedziałem.

[SaxoN]

Pierwszego twojego zdania nawet nie spróbuję zrozumieć, drugie jest już w miarę po polsku. W ogóle wzorcówka do tego czwartego to jakiś smutny żart, przecież istnieje do tego parolinijkowe rozwiązanie na łukach (odpowiednie półproste dzieliły na połowę odpowiednie łuki)