LXVII (67) OM - I etap

[Pinionrzek]

Jeszcze nie można, gdyż termin wysłania tej serii się nie skończył.

[wielkireturner]

Już można! Piszcie, czy 3 dało się zrobić krótko i zwięźle.

[Pinionrzek]

Z tego co słyszałem, to się dało. Niestety moje rozwiązanie jest długie i złożone. Ale w sumie to było jedyne zadanie, które rozkminiałem dłużej niż 5 minut i samo w sobie wydaje się być intrygujące. Pozostałe problemy wyraźnie odbiegają poziomem od zwykłych zadań z OM. Powodem tego stanu rzeczy może być to, że podobno ubiegłoroczne zadania były zbyt trudne i w olimpiadzie wystartowała rekordowo mała liczba osób, więc w tym roku KGOM postanowił zachęcić szersze grono uczestników do startu w olimpiadzie. Myślę jednak, że mimo prostoty tych trzech zadań, to poza 4., które mi się wybitnie nie podoba, były one zgrabne i ładne. Wieczorem, jeśli będę miał czas, postaram się wrzucić jakieś szkice.

[bakala12]

Nie wiem, co to za poglądy, że te zadania były proste i łatwiejsze niż w zeszłym roku. Ja uważam inaczej i mi ta seria się nie podobała. Moim zdaniem pierwsze 2 zadania były bardzo proste, to prawda, ale trzecie jest jednym z najdziwniejszych zadań na jakie trafiłem i zrobiłem je w końcu po sporej rozkminie, ale rozwiązanie w którym sprawdzam ileś tam przypadków jest po prostu obrzydliwe i odrzucające No a zadanie 4 w sumie nie było takie złe, ale też (przynajmniej ja) rozważałem przypadki (choć tutaj było ich 2, góra 3 chyba).

No więc moje wrażenie ogólne jest słabe, mimo że zrobiłem wszystkie zadania z tej serii, to niezbyt mi się podobały.

Również zobowiązuję się do wrzucenia szkiców swoich rozwiązań, ale nie miałem czasu jakoś wklepać tego jeszcze Ale tak skrótowo:

hinty:    

1. Indukcja po \(\displaystyle{ n}\), całkiem szybkie zadanie, no i nawiązuje do znanej hipotezy Collatza, więc jak ktoś znał tą hipotezę, to odpowiedź do zadania miał za darmo (gdyby się nie dało otrzymać jedynki, to hipoteza Collatza okazywałaby się nieprawdziwa). To zadanie można również zgrabnnie rozwiązać metodą niezmienników ( i oba rozwiązania korzystają z tego jak w stałej liczbie kroków zmniejszyć napisaną liczbę).
2. Geo na 2 podobieństwa... Liczyłem na coś ambitniejszego
3. Hejt na to zadanie Proste sformułowanie problemu, ale rozwiązanie żmudne (przynajmniej moje). Ciekaw jestem czy ktoś to zadanie zrobił zgrabnie i krótko, bo chętnie bym zobaczył takie rozwiązanie. No i napiszę po raz kolejny, że nie podobało mi się to zadanie
4. Nierówność geometryczna, w sumie nie taka strasznie trudna, ale przynajmniej ja musiałem się babrać z konfiguracją która dawała przypadki. Z tego co pamiętam jeden był niemal oczywisty, a drugi poddawał się przeliczeniu na pałę. Więc ogólnie w moim rozwiązaniu piękna i czarów nie ma

Ogólnie to nie ukrywając pierwsze 2 zadania były dużo łatwiejsze niż zwykle, natomiast 3 było żmudnym pałowaniem. No a zadanie 4 nie było magiczną geometrią, ale dało się je zrobić w dość prosty sposób. I nie mam pojęcia jak można sensownie określić poziom tych zadań, bo dwa pierwsze są bardzo łatwe, a dwa kolejne trochę jak koń pod górę

[aneta909811]

Jaki był w ubiegłym roku próg do II etapu w okręgu łódzkim?

[Pinionrzek]

Chyba 31, łódzki miał najwyższe progi.

[aneta909811]

Dziękuję.

[Wiesiek7]

Czy to 1 uznają, jeżeli się robiło bez indukcji, jedynie wyjasniająć, że otrzyma się w kazdym kroku liczbę mniejszą? Jak teraz czytam o hipotezie Collatza to się załamałem
Robiłem indukcję i wczoraj się zorientowałem, że jest błędna Nigdy więcej wysyłania zadań ostatniego dnia
Jaki był próg dla Warszawy rok temu?

[AndrzejK]

Zadanie 3. pochodzi z "Putnam Competition" z 2003 roku.

[bakala12]

Czy to 1 uznają, jeżeli się robiło bez indukcji, jedynie wyjasniająć, że otrzyma się w kazdym kroku liczbę mniejszą? Jak teraz czytam o hipotezie Collatza to się załamałem

Jeżeli odpowiednio to uzasadniłeś, to zostanie to uznane, bo to alternatywny sposób i w pełni poprawny.

Może zacznę wrzucać swoje rozwiązanie, ale na razie nie wszystko na raz

1.:    

Pokażemy, że niezależnie od tego jaka liczba była napisana na tablicy, po skończenie wielu operacjach opisanych w zadaniu, na tablicy można otrzymać jedynkę.
Dowód będzie indukcyjny ze względu na \(\displaystyle{ n}\).
Dla \(\displaystyle{ n=1}\) nie ma czego dowodzić. Podobnie dla \(\displaystyle{ n=2}\) po jednej operacji na tablicy pojawi się jedynka.
Załóżmy teraz, że teza zadania jest prawdziwa dla dowolnego \(\displaystyle{ n<n_{0}}\) przy czym \(\displaystyle{ n_{0} \ge 2}\).
Pokażemy, że początkowe stwierdzenie jest słuszne również dla \(\displaystyle{ n_{0}}\). Możliwe są dwa przypadki:
1. \(\displaystyle{ n_{0}}\) jest liczbą parzystą.
Wówczas w pierwszym kroku na tablicy otrzymujemy liczbę \(\displaystyle{ \frac{n_{0}}{2}}\), która jest naturalna i mniejsza od \(\displaystyle{ n_{0}}\), co na mocy założenia indukcyjnego oznacza, że po skończenie wielu krokach z liczby \(\displaystyle{ n_{0}}\) można otrzymać na tablicy jedynkę.
2. \(\displaystyle{ n_{0}}\) jest liczbą nieparzystą. Wówczas mamy wybór i na tablicy możemy napisać jedną z liczb \(\displaystyle{ 3n_{0}-1, 3n_{0}+1}\). Zauważamy łatwo, że są to dwi kolejne liczby parzyste, a więc jedna z nich musi być podzielna przez \(\displaystyle{ 4}\). Oznaczmy ją przez \(\displaystyle{ k}\). Wówczas po kolejnych dwóch operacjach na tablicy będzie znajdować się liczba \(\displaystyle{ \frac{k}{4}}\).
Mamy jednak \(\displaystyle{ \frac{k}{4} \le \frac{3n_{0}+1}{4} < \frac{4n_{0}}{4}}\) (druga nierówność jest ostra ponieważ \(\displaystyle{ n_{0} \ge 2}\)). A więc na tablicy otrzymaliśmy liczbę mniejszą od \(\displaystyle{ n_{0}}\), a więc na mocy założenia indukcyjnego po skończenie wielu operacjach możemy otrzymać na tablicy jedynkę.
Kończy to dowód kroku indukcyjnego, więc na mocy zasady indukcji matematycznej uzyskujemy prawdziwość naszego stwierdzenia dla dowolnej liczby całkowitej dodatniej.
Odpowiedź: Niezależnie od liczby początkowo napisanej na tablicy, wykonując skończenie wiele operacji opisanych w zadaniu można otrzymać na tablicy jedynkę.
Uwaga: W powyższym dowodzie pokazano nawet jak należy pomniejszać liczbę napisaną na tablicy w stałej ilości kroków, a więc zadanie można rozwiązać również ładnie za pomocą metody niezmienników

2.:    

Mamy następujące zależności:
\(\displaystyle{ AB^{2}=AC \cdot BC \Rightarrow \frac{AB}{AC}=\frac{BC}{AB} \Rightarrow \frac{AB}{BD}=\frac{BC}{AB} \Rightarrow \Delta ABC \sim \Delta ABD}\)
Zatem mamy równości:
\(\displaystyle{ \angle BAD = \angle BCA \\
\angle BAC = \angle BDA}\)
Wobec tego mamy:
\(\displaystyle{ \Delta ACE \equiv \Delta ABD}\)
A zatem \(\displaystyle{ \angle BAD = \angle CEA}\)

[Andrzej Andrzej]

W ubiegłym roku startowałem po raz pierwszy w OMie - z pierwszej serii zrobiłem tylko jedno zadanie. Wydaje mi się, że tegoroczne zadanka były znacznie łatwiejsze. Mimo wszystko dobrze się bawiłem, rozwiązując te zadania. Teraz tylko rozwalić drugą serię . Myślicie, że poziom bardzo wpłynie na próg do II etapu?

[Michalinho]

No to ja też wrzucę swoje rozwiązania. \(\displaystyle{ 4}\) poszło bez rozpatrywania przypadków . Jeśli ktoś ma ładne, trikowe rozwiązanie \(\displaystyle{ 3}\)-go albo jakieś względnie krótkie bez rozpatrywania wielu przypadków, ale z wykorzystaniem jakichś fajnych własności to niech wrzuci

1:    

Naszym zadaniem jest znalezienie złożenia przekształceń:
\(\displaystyle{ p(n)=\frac{n}{2}, q(n)=3n+1, r(n)=3n-1}\), tak aby otrzymać liczbę \(\displaystyle{ 1}\).
Opiszmy funkcję:
\(\displaystyle{ f(n)= \begin{cases} p(n), \text{ dla } 2|n \\ p(p(q(n)))=\frac{3n+1}{4}, \text{ dla } n\equiv 1\text{ mod 4}, \\ p(p(r(n)))=\frac{3n-1}{4}, \text{ dla } n\equiv 3\text{ mod 4}\end{cases}}\).
Dla \(\displaystyle{ n=1}\) od razu otrzymujemy \(\displaystyle{ 1}\).
Niech \(\displaystyle{ n\neq 1}\)
Zauważmy, że w ten sposób \(\displaystyle{ f(n)}\) będzie naturalne i ponadto łatwo sprawdzić, że \(\displaystyle{ f(n)<n}\).
Oznaczając poprzez \(\displaystyle{ f^{k}(n)}\) k-tą iterację \(\displaystyle{ f}\), otrzymujemy więc:
\(\displaystyle{ n>f(n)>f^2(n)>f^3(n)>\ldots\ge 1}\),
a więc po dostatecznej liczbie kroków otrzymamy \(\displaystyle{ 1}\).

2:    

Mamy 3 założenia:
1) \(\displaystyle{ BD=AC}\),
2) \(\displaystyle{ AD=AE}\),
3) \(\displaystyle{ AB^2=AC\cdot BC}\)
Z 1), 3) wynika \(\displaystyle{ AB^2=BD\cdot BC}\), a więc okrąg opisany na \(\displaystyle{ ACD}\) jest styczny do \(\displaystyle{ AB}\) w \(\displaystyle{ A}\). Z twierdzenia o kącie dopisanym \(\displaystyle{ \angle BAD=\angle ACD}\). Ponadto:
\(\displaystyle{ \angle ADB=180^\circ-\angle ADC=\angle ACD+\angle DAC=\angle BAC}\), co w połączeniu z 1) i 2) daje przystawanie trójkątów \(\displaystyle{ CAE}\) i \(\displaystyle{ BDA}\) a więc równość \(\displaystyle{ \angle BAD=\angle CEA}\).

4:    

Oznaczymy sobie prostą równoległą do prostej \(\displaystyle{ k}\) przechodzącą przez punkt \(\displaystyle{ X}\) jako \(\displaystyle{ r^X_k}\).
\(\displaystyle{ r^P_{AB}\cap BC=M, r^P_{BC}\cap AB=L}\)
\(\displaystyle{ r^P_{AB}\cap ADC=Q, r^P_{BC}\cap ADC=R}\) (łamana \(\displaystyle{ ADC}\))
\(\displaystyle{ r^Q_{BC}\cap AB=K, r^R_{AB}\cap BC=N, r^Q_{BC}\cap r^R_{AB}=S}\)
Proste równoległe do boków \(\displaystyle{ AB, BC}\) poprowadzone z \(\displaystyle{ Q}\) wyznaczyły nam wielokąt o wierzchołku \(\displaystyle{ A}\) o polu \(\displaystyle{ x}\), a z \(\displaystyle{ R}\) wielokąt o wierzchołku \(\displaystyle{ C}\) o polu \(\displaystyle{ z}\). \(\displaystyle{ P_{PQRS}-d=y}\). Zauważmy, że prawdziwa jest równość (banalna do udowodnienia, gdy widzimy prostokąt):
\(\displaystyle{ (a-x)(c-z)=b(d+y)\Rightarrow ac=bd+by+x(c-z)+az> bd}\)

[TomciO]

3cie chyba prosto:

Ukryta treść:    

Niech \(\displaystyle{ f(x) = Ax^2 + Bx + C}\) oraz \(\displaystyle{ g(x) = ax^2 + bx + c}\). Ponieważ zamiana \(\displaystyle{ f}\) lub \(\displaystyle{ g}\) na funkcje przeciwną nie zmienia założeń ani tezy, możemy przyjąć, że \(\displaystyle{ A, a > 0}\). Co więcej, \(\displaystyle{ \lim_{x \to \infty} \frac{f(x)}{g(x)} = \frac{A}{a}}\), a skoro dla dużych \(\displaystyle{ x}\) oba trójmiany są dodatnie, to oczywiście \(\displaystyle{ A \geq a}\). Rozpatrzmy najpierw przypadek, w którym funkcja \(\displaystyle{ f}\) posiada dwa różne pierwiastki rzeczywiste \(\displaystyle{ x_1, x_2}\). Ponieważ \(\displaystyle{ 0 = |f(x_i)| \geq |g(x_i)|}\) mamy \(\displaystyle{ g(x_1)=g(x_2)=0}\). Wówczas
\(\displaystyle{ \left | \frac{\Delta_f}{4A} \right |=\left | f \left ( \frac{-B}{2A} \right ) \right |=\left | f\left ( \frac{x_1+x_2}{2} \right ) \right | \geq \left | g\left ( \frac{x_1+x_2}{2} \right ) \right | = \left | g \left ( \frac{-b}{2a} \right ) \right | = \left | \frac{\Delta_g}{4a} \right |.}\)

A skoro \(\displaystyle{ A \geq a}\), to w tym przypadku teza jest ewidentna.

Załóżmy zatem, że funkcja \(\displaystyle{ f}\) posiada co najwyżej jeden pierwiastek, czyli w że w szczególności jest cały czas nieujemna. Dla dowolnego \(\displaystyle{ x}\) prawdziwe są więc obie nierówności \(\displaystyle{ f(x) - g(x) \geq 0}\) oraz \(\displaystyle{ f(x) + g(x) \geq 0}\). W szczególności oba trójmiany \(\displaystyle{ (A-a)x^2 + (B-b)x + (C-c)}\) oraz \(\displaystyle{ (A+a)x^2 + (B+b)x + (C+c)}\) są ciągle nieujemne. Ich delty są więc niedodatnie. Otrzymujemy zależności
\(\displaystyle{ (B-b)^2 - 4(A-a)(C-c) \leq 0}\) oraz \(\displaystyle{ (B+b)^2 - 4(A+a)(C+c) \leq 0}\),
które przepisujemy jako
\(\displaystyle{ \Delta_f + \Delta_g - (2Bb - 4Ac - 4aC) \leq 0}\) oraz \(\displaystyle{ \Delta_f + \Delta_g + (2Bb - 4Ac - 4aC) \leq 0}\).
Zauważmy, że gdyby było \(\displaystyle{ \Delta_f + \Delta_g > 0}\) to w oczywisty sposób nie mogłyby zachodzić jednocześnie obie powyższe nierówności. A zatem \(\displaystyle{ | \Delta_f| = - \Delta_f \geq \Delta_g = |\Delta_g|}\) i dowód jest zakończony,

[Pinionrzek]

1.

Ukryta treść:    

Pokażę, że po skończenie wielu krokach można otrzymać na tablicy jedynkę. Zaprezentuję algorytm, który pozwoli nam dojść do takiej sytuacji.
Pierwszym ważnym spostrzeżeniem jest to, że wykonując operacje podane w treści zadania, zawsze otrzymamy dodatnią liczbę całkowitą. Jeżeli teraz liczba na tablicy jest parzysta, to dzieląc ją przez \(\displaystyle{ 2}\) oczywiście zmniejszamy tę liczbę. Jeśli jednak na tablicy znajduje się \(\displaystyle{ k \equiv 1 \pmod{2}}\), to musimy ją zamienić na \(\displaystyle{ 3k+1}\) lub \(\displaystyle{ 3k-1}\). Są to dwie liczby parzyste różniące się o \(\displaystyle{ 2}\), zatem jedna z nich musi się dzielić przez \(\displaystyle{ 4}\). Wybieramy więc tę liczbę, dzielącą się przez \(\displaystyle{ 4}\), a następnie postępując wedle założeń zadania dzielimy ją dwa razy przez \(\displaystyle{ 2}\), otrzymując pewną liczbę \(\displaystyle{ l \in \mathbb{Z}_{+}}\). Pokażę teraz, że dla dowolnie wybranego \(\displaystyle{ k \in \mathbb{Z}_{+}}\) będzie zachodziło \(\displaystyle{ l \le k}\). Jest to równoważne \(\displaystyle{ (1)}\)\(\displaystyle{ \frac{3k+1}{4} \le k \iff 3k+1 \le 4k}\), co jest oczywiste, a równość zachodzi jedynie, gdy \(\displaystyle{ k=1}\).Skoro pokazaliśmy, że dana nierówność zachodzi dla \(\displaystyle{ 3k+1}\), to tym bardziej zachodzi ona dla \(\displaystyle{ 3k-1}\).
Wykazałem zatem, że zarówno dla dowolnego \(\displaystyle{ k>1}\), wykonując podane operacje, jesteśmy w stanie otrzymać liczbę mniejszą od \(\displaystyle{ k}\). Widzimy więc, że na mocy pierwszego spostrzeżenia oraz \(\displaystyle{ (1)}\), otrzymujemy, że po skończonej liczbie operacji otrzymamy w końcu jedynkę.

2.

Ukryta treść:    

Warunek \(\displaystyle{ AB^2=BC\cdot AC=BC\cdot BD}\) implikuje na mocy potęgi punktu to, że okrąg opisany na \(\displaystyle{ \Delta ADC$ jest styczny do $AB}\). Ponadto stosunki te pokazują także, że \(\displaystyle{ \Delta ABC \sim \Delta ABD}\). Z tego podobieństwa mamy również \(\displaystyle{ \frac{AC}{AB}= \frac{AD}{DB}= \frac{AE}{AC} \iff CA^2=AB\cdot AE}\). Z tego wynika, że okrąg opisany na \(\displaystyle{ \Delta EBC}\) jest styczny do \(\displaystyle{ AC}\). Niech \(\displaystyle{ F}\) będzie drugim punktem przecięcia \(\displaystyle{ CE}\) z okręgiem opisanym na \(\displaystyle{ \Delta ADC}\). Stosując teraz dwukrotnie twierdzenie o kącie między styczną a cięciwą dostajemy \(\displaystyle{ \angle FAE = \angle ECA= \angle EBC}\). Ponadto \(\displaystyle{ \angle ADB=180^\circ-\angle CDA= 180^\circ- \angle AFC= \angle AFE}\). Równość między drugim a trzecim przejściem wynika z tego, że oba te kąty są oparte na jednym łuku. Ponadto na mocy obu tych równości mamy, że \(\displaystyle{ \Delta AFE \sim \Delta ADB}\), więc \(\displaystyle{ \angle BAD = \angle CEA}\).

3.

Ukryta treść:    

Mam w sumie podobne rozwiązanie do TomciA, z tym że ja to zadanie rozwiązałem tak, że najpierw wyeliminowałem jakieś prostsze przypadki, gdy \(\displaystyle{ \Delta_f \ge 0}\) i tę ostatnią część rozumowania poprzednika zastosowałem do konkretnego przypadku \(\displaystyle{ \Delta_f<0, \Delta_g>0}\). Widzę teraz, że moje rozwiązanie da się trochę skrócić i wykonałem trochę niepotrzebnej roboty, ale zarys ogólnie jest podobny. W każdym razie uważam, że to zadanie jako jedyne wymaga większej pomysłowości i to mi się w nim podoba.

4.

Ukryta treść:    

Nie no, to zadania nie wymaga jakiejkolwiek pomysłowości, jest po prostu tępym zastosowaniem wzoru na pole trapezu i prostokąta, gdzie praktycznie od początku widać, że większość rzeczy się tam skraca. Brak jakiegokolwiek tricku w tym zadaniu mnie naprawdę rozsierdził.

[jutrvy]

A ja pierwsze zrobiłem zupełnie inaczej.

Ukryta treść:    

Załóżmy nie wprost, że zbiór tych liczb naturalnych, dla których nie można otrzymać jedynki jest niepusty. Z zasady minimum ma on element najmniejszy, oznaczmy go przez \(\displaystyle{ k}\). Oczywiście \(\displaystyle{ k\ge 2}\). Jeśli \(\displaystyle{ 2}\) dzieli \(\displaystyle{ k}\), to wtedy mamy, że \(\displaystyle{ \frac{k}{2}}\) też się nie sprowadzi do jedynki - sprzeczność z minimalnością \(\displaystyle{ k}\).

Jeżeli \(\displaystyle{ k}\) jest nieparzysta, to reszta z dzielenia \(\displaystyle{ k}\) przez \(\displaystyle{ 4}\) wynosi \(\displaystyle{ 1}\) lub \(\displaystyle{ 3}\). Jeśli ta reszta to jeden, to wtedy zmazujemy \(\displaystyle{ k}\) i piszemy \(\displaystyle{ 3k+1}\), co przez cztery już się dzieli. Zauważamy, że \(\displaystyle{ \frac{3k+1}{4}}\) jest liczbą mniejszą od \(\displaystyle{ k}\) - znów sprzeczność z minimalnością \(\displaystyle{ k}\). I analogicznie dla reszty równej trzy...