[LXI OM] I etap

[Kibu]

tez na to liczę:) swoją drogą wszystkie pocty juz są o tej porze zamkniete wiec moze ktos sie pokusi o umieszczenie rozwiazan

Niewszystkie. Samej zdarzało mi się o 22 z minutami być na poczcie całodobowej z rozwiązaniami zadań... Właściwie to większość serii przez 3 lata na niej wysłałam:).

[lukasz_650]

I też nie zgadzam się z tym, że wszystkie poczty są już zamknięte, bo w każdym większym mieście poczta główna jest całodobowa - i być może ktoś nawet jeszcze wyśle rozwiązania, bo dla przykładu rok temu rozwiązania zadań z Olimpiady Fizycznej wysyłałem o 22:30 ^^

EDIT. Wygląda na to, że ktoś ma podobne doświadczenia i że się trochę spóźniłem z tym postem

[jerzozwierz]

No tak... mi nauczyciel powiedział żeby dać do niego, a szkoła wyśle. Jak zapomni to.... nie ręczę za siebie A jako że rozwiązania pisałem na komputerze, powinienem wrzucić najwcześniej jak się da.

[xanowron]

No tak... mi nauczyciel powiedział żeby dać do niego, a szkoła wyśle. Jak zapomni to.... nie ręczę za siebie A jako że rozwiązania pisałem na komputerze, powinienem wrzucić najwcześniej jak się da.

Trzeba było nie słuchać tylko samemu wysłać
Nie warto tak ryzykować dla tych 4-5 zł

[nikasek11]

I co z rozwiązaniami?

[etyre]

Naprawdę się wkurzyłem przez to, że strona nie działała w nocy. Nie wiem, czy to przez najazd olimpijczyków, ale mimo to, byłem i wkurzony, i zawiedziony.

Teraz wybieram się do szkoły (całe szczęście nie mam pierwszych lekcji, mogłem się przynajmniej wyspać ;P), więc mogę rozwiązania podać na szybko.

Wg mnie, najłatwiejsze było 2, w ciągu 2 minut można było wszystko rozpisać (włącznie z rysunkiem).

Wyglądało tak:

Ukryta treść:    

Wcześniej wkleiłem wysłane rozwiązanie, ale uznałem, że nie wygląda OK, więc, jak też u niemal wszystkich, na kącie środkowym i wpisanym

W 3 znalazłem algorytm sortowania 2 dowolnych elementów, przez kilkukrotne segmentowanie.

Ukryta treść:    

Nie będę się rozpisywał teraz ale po kolei ciągi wyglądały tak:\(\displaystyle{ (a,b), (b,b,a,b), (b,b,a,b,a,a)
(b,a)}\)Oczywiści było trochę opisu w słowach, ale ten algorytm jest rdzeniem.

Pierwsze podobnie do innych, 4 trochę inaczej i chyba nie na max

OK, na razie tyle, w reszcie jest za dużo pisania w TeX-u . Czekam na rozwiązania innych.

[jerzozwierz]

Więc:
Zadanie pierwsze:

Ukryta treść:    

Oczywiście jak któraś ze zmiennych jest równa 1, to teza oczywista. Zakładamy dalej, że żadna nie jest równa 1. Dzielimy obie strony równania przez \(\displaystyle{ (x-1)(y-1)}\) i podstawiamy \(\displaystyle{ p=x ^{2008}+x ^{2007}+...+x+1}\) oraz \(\displaystyle{ q=y^{2008}+y ^{2007}+...+y+1}\). Równanie wygląda teraz tak: \(\displaystyle{ q(x^{2009}+p)=p(y^{2009}+q)}\). Redukujemy pq, dzielimy obie strony równania przez \(\displaystyle{ (xy)^{2009}}\) i rozwijając z powrotem \(\displaystyle{ p}\) i \(\displaystyle{ q}\) dostajemy \(\displaystyle{ \frac{x ^{2008}+x ^{2007}+...+x+1}{x^{2009}}= \frac{y^{2008}+y ^{2007}+...+y+1}{y^{2009}}}\). Teraz sobie podstawiam \(\displaystyle{ \frac{1}{x}=a}\) i \(\displaystyle{ \frac{1}{y}=b}\). Dostaję oczywiście \(\displaystyle{ a^{2009}+a ^{2008}+...+a=b^{2009}+b ^{2008}+...+b}\). Uwzględniając różnowartościowość w przedziale \(\displaystyle{ (0,+ \infty )}\) funkcji \(\displaystyle{ f(t)=t^{2009}+t ^{2008}+...+t}\) dostaję \(\displaystyle{ a=b \Leftrightarrow x=y}\) i właściwie po zadaniu.

Zadanie drugie:

Ukryta treść:    

tak jak etyre

Zadanie trzecie:

Ukryta treść:    

tak jak etyre, tylko dodam, że jak można zmieniać miejscami dwa wyrazy ciągu, to robimy tak: wybieramy element najmniejszy, i "przerzucamy" go na początek, za pomocą cyklu (k-1) zmian, zakładając że stoi na k-tej pozycji. Potem drugi najmniejszy, i tak dalej i tak dalej, aż posortujemy całość.

Zadanie czwarte:
Nad nim myślałem długo, ale w końcu wykminiłem dość ładne rozwiązanie.

Ukryta treść:    

Na początek dwie oczywiste oczywistości:
\(\displaystyle{ \frac{x+1}{x}=a \Leftrightarrow x= \frac{1}{a-1}}\) oraz \(\displaystyle{ \frac{2x-1}{x-1}=a \Leftrightarrow x= \frac{a-1}{a-2}}\). Dowód nie wprost, załóżmy, że pewne \(\displaystyle{ \frac{p}{q}}\) nie należy do zbioru A. Czyli: a nie należy do zbioru A, wtedy i tylko wtedy, gdy \(\displaystyle{ \frac{a-1}{a-2}}\) nie należy do A i liczba \(\displaystyle{ \frac{1}{a-1}}\) nie należy do zbioru A. Teraz taki myk: definiujemy zbiór B analogicznie do tego z zadania, tylko że korzeniem jest liczba \(\displaystyle{ \frac{p}{q}}\), a zamiast dwóch operacji na iksie daję \(\displaystyle{ \frac{1}{a-1}}\) i \(\displaystyle{ \frac{a-1}{a-2}}\).
Nietrudno zauważyć, że teza zadania sprowadza się do udowodnienia, że niezależnie od p i q, liczba 2 należy do zbioru B. No to jazda: najpierw, iterując jedną operację z drugą, dostaję \(\displaystyle{ a-2}\). Czyli, mając dowolnie duże \(\displaystyle{ \frac{p}{q}}\), mogę "zjechać" nim do przedziału \(\displaystyle{ (1,3>}\).
Idea mojego dowodu polega na tym, żeby pokazać, że mianownik będzie malał, co jest równoznaczne z tym, że w końcu osiągnie 1. Rozpatruję dwa przypadki: 1. \(\displaystyle{ 1< \frac{p}{q}<2}\) i 2. \(\displaystyle{ 2< \frac{p}{q}<3}\). W pierwszym przypadku używam operacji \(\displaystyle{ \frac{1}{a-1}}\), po podstawieniu za a \(\displaystyle{ \frac{p}{q}}\), dostaję że mianownik jest równy \(\displaystyle{ p-q}\), a wykazanie tego, że przy założeniu \(\displaystyle{ 1< \frac{p}{q}<2}\) mianownik jest mniejszy, jednocześnie nie ujemny, i jednocześnie większy od 1 jest przedszkolne. Analogicznie przypadek drugi, używam drugiej operacji, dostaję mianownik \(\displaystyle{ p-2q}\), i tak samo dowodzę jak w przypadku pierwszym. No to teraz końcówka dowodu: mając sobie to \(\displaystyle{ \frac{p}{q}}\), sprowadzam do przedziału \(\displaystyle{ (1,3>}\), zmniejszam mianownik, znowu sprowadzam do \(\displaystyle{ (1,3>}\), i tak dalej, i tak dalej, aż mianownik będzie równy 1. Nie jest wielkim odkryciem to, że w przedziale \(\displaystyle{ (1,3>}\) mamy tylko dwie liczby całkowite: 2 i 3, dwójka jest naszym celem, a \(\displaystyle{ \frac{3-1}{3-2}=2}\), co kończy dowód.

[Qń]

W ramach podtrzymywania sprawności umysłu , postanowiłem i ja zmierzyć się z I etapem (jak kiedyś). Oto szkice moich rozwiązań (miejscami się dublują z już zamieszczonymi, ale pisałem to parę dni temu i szkoda mi teraz nie zamieszczać ) :

Zadanie 1
Chyba niezbyt trudne. Drugi sposób rozwiązania mniej elementarny, ale za to z chyba niebrzydkim wykorzystaniem nierówności między średnimi.

Rozwiązanie:    

Łatwo zauważyć, że rozwiązaniami są \(\displaystyle{ (t,t),(t,1),(1,t)}\). Pokażemy, że innych rozwiązań nie ma. Załóżmy zatem, że \(\displaystyle{ x,y \neq 1}\). Wtedy równoważnie mamy:
\(\displaystyle{ \frac{x^{2010}-1}{x^{2009}-1} = \frac{y^{2010}-1}{y^{2009}-1}}\)

I sposób
Jeśli \(\displaystyle{ x\neq y}\), to bez utraty ogólności możemy założyć, że \(\displaystyle{ x>y}\). Mamy wówczas:
\(\displaystyle{ \frac{x^{2010}-1}{x^{2009}-1} = \frac{y^{2010}-1}{y^{2009}-1}
\Leftrightarrow \\ \\ \Leftrightarrow
\frac{x^{2009} + x^{2008} + \dots +1}{x^{2008} +x^{2007}+ \dots +1} = \frac{y^{2009} + y^{2008} + \dots +1}{y^{2008} +y^{2007}+ \dots +1}
\Leftrightarrow \\ \\ \Leftrightarrow
\frac{x^{2009}}{x^{2008} +x^{2007}+ \dots +1} + 1 = \frac{y^{2009}}{y^{2008} +y^{2007}+ \dots +1} +1
\Leftrightarrow \\ \\ \Leftrightarrow
\frac{x^{2009}}{x^{2008} +x^{2007}+ \dots +1} = \frac{y^{2009}}{y^{2008} +y^{2007}+ \dots +1}
\Leftrightarrow \\ \\ \Leftrightarrow
\frac{x^{2008} +x^{2007}+ \dots +1}{x^{2009}} = \frac{y^{2008} +y^{2007}+ \dots +1}{y^{2009}}
\Leftrightarrow \\ \\ \Leftrightarrow
\frac{1}{x}+\frac{1}{x^2} + \dots + \frac{1}{x^{2009}} =
\frac{1}{y}+\frac{1}{y^2} + \dots + \frac{1}{y^{2009}}}\)
Ale z uwagi na \(\displaystyle{ \frac{1}{x^k} < \frac{1}{y^k}}\) nigdy nie może zachodzić tu równość, co kończy dowód.

Sposób II
Pokażemy, że funkcja \(\displaystyle{ f(t)=\frac{t^{2010}-1}{t^{2009}-1}}\) jest rosnąca w zbiorze \(\displaystyle{ (0,1) \cup (1, \infty )}\), w szczególności będzie to znaczyło, że jest w nim różnowartościowa, a zatem rzeczona równość zachodzi wyłącznie dla \(\displaystyle{ x=y}\)

Oznaczmy \(\displaystyle{ 2009=n}\). Mamy:

\(\displaystyle{ f(t) = \frac{t^{n+1}-1}{t^{n}-1} \\
f'(t) = \frac{t^{2n}-(n+1)t^n + nt^{n-1}}{(t^n-1)^2}}\)

Z nierówności między średnimi arytmetyczną i geometryczną mamy:
\(\displaystyle{ \frac{t^{2n}+nt^{n-1}}{n+1} \geq \sqrt[n+1]{t^{2n} \cdot \left( t^{n-1}\right)^n} = \sqrt[n+1]{t^{n(n+1)}}=t^n}\)
skąd wynika, że \(\displaystyle{ f'(t) \geq 0}\), co oznacza, że funkcja \(\displaystyle{ f}\) jest rosnąca w każdym z przedziałów \(\displaystyle{ (0,1)}\) i \(\displaystyle{ (1,\infty )}\). Ale w jedynce nasza funkcja nie ucieka do nieskończoności, tylko ma granicę skończoną, więc łatwo stąd wywnioskować, że musi być rosnąca w całej dziedzinie, co kończy dowód.

Zadanie 2
Zdecydowanie najłatwiejsze zadanie z tej serii, nadawałoby się też na OMG.

Rozwiązanie:    

Oznaczmy \(\displaystyle{ \sphericalangle ACB = 2\alpha}\). Z równoramienności trójkąta \(\displaystyle{ ABC}\) wynika, że \(\displaystyle{ \sphericalangle CAB = 90^o -\alpha}\). Ale \(\displaystyle{ \sphericalangle CAB}\) i \(\displaystyle{ \sphericalangle DSB}\) są kątami odpowiednio wpisanym i środkowym, opartymi na tym samym łuku okręgu opisanego na trójkącie \(\displaystyle{ ADB}\). Stąd \(\displaystyle{ \sphericalangle DSB = 180^o- 2\alpha}\), a zatem \(\displaystyle{ \sphericalangle ACB + \sphericalangle DSB= 180^o}\), co oznacza, że na czworokącie \(\displaystyle{ SBCD}\) da się opisać okrąg, a stąd już wynika teza.

Zadanie 3
Też raczej proste, aczkolwiek strzelam, że za redakcję rozwiązań mogą wielu osobom mocno pociąć punkty.

Rozwiązanie:    

Zauważmy, że w każdym ciągu dowolne dwa elementy można zamienić miejscami, wykonując operacje:
\(\displaystyle{ ba \rightarrow aaba \rightarrow aababb = a(ab)(ab)b \rightarrow ab}\)
To oznacza, że każdy ciąg można przy użyciu dozwolonych operacji uporządkować w dowolny sposób, w szczególności też rosnąco.

Zadanie 4
Chyba jedyne trudne zadanie w tej serii. Słyszałem pogłoski, że istnieją (co najmniej) dwa sposoby jego rozwiązania, chętnie więc zobaczę istotnie różne rozwiązanie od poniższego, bo aż nie chce mi się wierzyć, że się da. A poniższą ideę można też zredagować inaczej, tzn. pokazać, że idąc od dowolnej liczby wymiernej (większej niż jeden) "do tyłu" - da się dojść do dwójki (ale to ta sama koncepcja).

Rozwiązanie:    

Umówmy się, że ułamek \(\displaystyle{ \frac{p}{q}}\) nazwiemy dobrym, jeżeli \(\displaystyle{ p,q \in \mathbb{Z}, \ p,q > 0, \ NWD(p,q)=1, \ \frac{p}{q}>1}\). Oczywistym jest, że każdą liczbę wymierną większą od jeden da się zapisać jako ułamek dobry, wystarczy więc wykazać, że każdy ułamek dobry należy do zbioru \(\displaystyle{ A}\).

Dowiedziemy tego indukcyjnie ze względu na licznik ułamka dobrego.

Podstawa indukcji
Oczywistym jest, że każdy ułamek dobry ma licznik nie mniejszy od dwóch oraz, że ułamek dobry o liczniku równym dwa jest tylko jeden - jest to \(\displaystyle{ \frac{2}{1}}\). Z założenia w zadaniu wynika, że należy on do zbioru \(\displaystyle{ A}\), nie ma więc tu czego dowodzić.

Krok indukcyjny
Ustalmy \(\displaystyle{ p>2}\). Załóżmy, że dla wszystkich \(\displaystyle{ p_1}\) takich, że \(\displaystyle{ p_1<p}\) każdy dobry ułamek postaci \(\displaystyle{ \frac{p_1}{q_1}}\) należy do \(\displaystyle{ A}\). Pokażemy, że każdy dobry ułamek postaci \(\displaystyle{ \frac{p}{q}}\) należy do \(\displaystyle{ A}\).

Weźmy więc dowolny dobry ułamek \(\displaystyle{ \frac{p}{q} \neq 2}\) i rozpatrzmy dwa przypadki: kiedy jest on mniejszy od dwóch i kiedy jest większy od dwóch.

1) Jeśli \(\displaystyle{ \frac{p}{q} < 2}\), to twierdzę, że ułamek \(\displaystyle{ \frac{q}{p-q}}\) jest dobry. Istotnie: licznik i mianownik są liczbami całkowitymi dodatnimi, ułamek jest nieskracalny (wynika to na przykład z algorytmu Euklidesa), oraz
\(\displaystyle{ \frac{q}{p-q}> 1 \Leftrightarrow q > p-q \Leftrightarrow 2q > p \Leftrightarrow \frac{p}{q}<2}\),
a ostatnia nierówność jest prawdziwa.
Co więcej, rzeczony ułamek ma licznik mniejszy niż \(\displaystyle{ p}\), a zatem z założenia indukcyjnego należy do \(\displaystyle{ A}\).
Ale w takim razie (z warunku \(\displaystyle{ x\in A \Rightarrow \frac{x+1}{x} \in A}\)) do \(\displaystyle{ A}\) należy też liczba:
\(\displaystyle{ \frac{\frac{q}{p-q}+1 }{\frac{q}{p-q}} = \frac{q + p -q}{q}=\frac{p}{q}}\)
czyli ta, o którą nam chodziło. W pierwszym wypadku mamy więc koniec kroku indukcyjnego.

2) Jeśli \(\displaystyle{ \frac{p}{q}>2}\), to twierdzę, że ułamek \(\displaystyle{ \frac{p-q}{p-2q}}\) jest dobry. Istotnie: licznik i mianownik są liczbami całkowitymi dodatnimi, ułamek jest nieskracalny (wynika to na przykład z algorytmu Euklidesa), oraz:
\(\displaystyle{ \frac{p-q}{p-2q}> 1 \Leftrightarrow p-q> p-2q \Leftrightarrow q>0}\),
a ostatnia nierówność jest prawdziwa.
Co więcej, rzeczony ułamek ma licznik mniejszy niż \(\displaystyle{ p}\), a zatem z założenia indukcyjnego należy do \(\displaystyle{ A}\).
Ale w takim razie (z warunku \(\displaystyle{ x\in A \Rightarrow \frac{2x-1}{x-1} \in A}\)) do \(\displaystyle{ A}\) należy też liczba:
\(\displaystyle{ \frac{2\cdot \frac{p-q}{p-2q}-1}{\frac{p-q}{p-2q}-1} = \frac{2p-2q - (p-2q)}{p-q - (p-2q)} = \frac{p}{q}}\)
czyli ta, o którą nam chodziło. W drugim wypadku także więc mamy koniec kroku indukcyjnego.

Kończy to dowód.

Cóż, wydaje mi się faktyczne umiejętności zostaną zweryfikowane w kolejnych seriach.

Q.

[Dumel]

tak jak Qń'a niestety starość już mnie dopadła, ale co nie co od siebie też dorzucę
1.

rozwiązanie:    

tak jak powyżej - pochodna

komentarz:    

tak jak zwykle to bywa z zad nr 1 - łatwe szybkie, raczej na zachętę dla początkujących

2.

rozwiązanie:    

wiadomo

komentarz:    

szkoda słów, zadanie łatwiejsze niż na kartkówce w I klasie

3.

rozwiązanie:    

ab->a abab a -> baba -> ba. nawiasem mówiąc ciewak jestem czy da się to zrobić inaczej (prościej na pewno nie) niż przez przestawianie sąsiednich liczb

komentarz:    

pewnie będę jedną z niewielu osób dla których było to najtrudniejsze zadanie I serii (jako jedyne zajęło mi więcej niż 5 minut). Ładne i proste, czyli standardowa pierwszoetapowa kombinatoryka

4.

rozwiązanie:    

idea ta sama co u wszystkich. zapis trochę inny- liczby wymiernej >1 nie przedstawiawiłem jako \(\displaystyle{ \frac{p}{q}}\) ale \(\displaystyle{ 1+ \frac{p}{q}}\). stąd wynika że jeśli para \(\displaystyle{ (p,q)}\) jest dobra to pary \(\displaystyle{ (p+q,p)}\) oraz \(\displaystyle{ (q,p+q)}\) też. banalna indukcja po \(\displaystyle{ max(p,q)}\) załatwia sprawę.

komentarz:    

jak wyżej- ładne i proste, ale mogło sprawić spore trudności zupełnie początkującym olimpijczykom. zaskoczyło mnie że dwójka to jedyna liczba z której "dojdziemy" do wszystkich liczb wymiernych >1

[Klorel]

ja zrobiłem konstrukcję liczb wymiernych za pomoca 'operacji' z zadania poprzez ułamki łańcuchowe, pokazując wcześniej, że każda liczba naturalna >1 nalezy do A.
Podobno jest to złe rozwiązania, cóż, mówi się trudno

reszta jak wszyscy ;]

[Rogal]

Wrzuć, ocenimy.

[Swistak]

Zadania 2-3: W ogóle szkoda gadać, nie wiem jakim cudem takie coś znalazło się na OM. Aż się prosi, aby wyjść na jakiegoś kozaka i poopowiadać jakieś ciekawe anegdotki, jakim to jest się fajnym, bo w jak krótkim czasie się zrobiło te zadania i z jakimi ciekawymi hostoryjkami xD.
Zadanie 1: Nic szczególnego, także proste, ale nie tak jak 2 i 3.
Zadanie 4: Jedyne ambitniejsze zadanie w tej serii. Jednym z moich pierwszych pomysłów na to zadanie było zajrzenie do książeczki "Miniatury Matematyczne 19", gdzie był dowód na to, że zaczynająć od ułamka \(\displaystyle{ \frac{1}{2}}\) i od ułamka \(\displaystyle{ \frac{a}{b}}\) tworząc ułamki \(\displaystyle{ \frac{a}{a+b} \ \ \frac{b}{a+b}}\) dojdziemy do wszystkich liczb wymiernych z przedziału \(\displaystyle{ (0; 1)}\) . Dowód przeprowadziłem analogicznie. Dziwi mnie, że bardzo dużo osób, zamiast po liczniku schodziło po mianowniku i wykorzystywało fakt, że wszystkie liczby całkowite należą do A i rozpatrywało 3 przypadki, kiedy \(\displaystyle{ \frac{p}{q}}\) należy do przedziałów \(\displaystyle{ (1; 2) \ \ (2; 3) \ \ (3; \infty)}\) (któryś z tych 2 ostatnich domknięty). Osobiście nie wiem jak można zrobić takie zadanie w krócej niż 5 minut . Nie jest pod żadnym względem schematyczne, a i pomysł nie jest taki banalny.

[Dawid00]

W zadaniu drugim ja zrobiłem to na rysunku.

Narysowałem trójkąt ABC. Zaznaczyłem na boku AB punkt D i stworzyłem nowy trójkąt BCD. Wyznaczyłem S i powstał mi czterobok. Zaznaczyłem ten czterobok i opisałem go w trójkącie i mi wyszło, że wszystkie te boki są opisane na trójkącie.

Raczej to źle zrobiłem, bo wszyscy mają inaczej (

[Django]

Pierwsze i trzecie mam mniej więcej jak Wy, (pomysły takie same), drugie zrobiłem podpierając się nieco trygonometrią, ale dowód wcale nie jest trudny (2x twierdzenie sinusów i krótki opis). Czwarte natomiast... ile za to dostanę punktów:

Ukryta treść:    

Podzieliłem dowód na 3 części. Najpierw udowodniłem, że w zbiorze nie ma liczby niewymiernej i nie ma liczby mniejszej od 1 (to są te dwie części, jestem ich pewien, że są dobrze). Natomiast trzecia część wygląda tak: założyłem nie wprost, że jest pewna (jedna) liczba wymierna większa od 1 i wymierna, która jednak w zbiorze A nie znajduje się. Doszedłem do sprzeczności, mianowicie, że powinna ta liczba nie dać się opisać żadnym ze wzorów danych w treści, a jednak się daje opisać. I tu napisałem, że to kończy dowód.

?

[Swistak]

...
No niestety dowód eksperymentalny na jednym przypadku w matematyce nie działa xD

Hahah Django nudziło Ci się z twierdzeniem sinusów xD? To było zadanie na wpisanie miar 2 kątów, a nie na 2 twierdzenia sinusów xD. Propo Twojego czwartego, to raczej czysty blef, bo nic nie wiesz, czy liczba, która po podstawieniu da Ci daną liczbę, należy do danego zbioru.