LXIV (64) OM - I etap

[HuBson]

współczuję wszystkim który redagowali rozwiązanie do 8

[Errichto]

E tam, tylko 3427 znaków.

[bakala12]

U mnie:
5. NO cóż dość łatwe
6. Menelaosem było najszybciej, ale tw. sinusów też szło
7. No jak na stereo to straszny banał, że ja na to wpadłem
8. Nie pykło. Z tego co widzę to trzeba zająć się grafami
Ogólnie druga seria moim zdaniem na dość standardowym poziomie, choć geometria go nie zawyżała

[chomikchomik]

widzę, że nie tylko ja nie zrobiłem 8. a już się tak puszyłem, że zrobię wszystko. było chyba najtrudniejsze, ale nie wiem, bo też nie robiłem żadnej grafowej kombi. może ktoś polecić jakieś zadanka w stylu grafy, itp.?

[Ponewor]

Moje: 5 na miliard sposobów zrobić można, a ja chciałem upodobnić do niebieskiego Pawłowskiego. 6 sinusy jak już się pojawiało. 7 zwyczajnie. 8 to jak komisja zrozumie co miałem na myśli to się zdziwię.

Zadanie 5.:    

Na dobry początek weźmy \(\displaystyle{ m=1}\) i \(\displaystyle{ n=1}\). Wtedy \(\displaystyle{ |20^{m}-9^{n}|=|20-9|=11}\). Załóżmy teraz, że istnieją takie całkowite dodatnie \(\displaystyle{ m}\) i \(\displaystyle{ n}\), że \(\displaystyle{ |20^{m}-9^{n}|=k<11}\). Oczywiście \(\displaystyle{ k \in \mathbf{Z}}\) i \(\displaystyle{ k}\) nieujemne. Zachodzą oczywiste kongruencje: \(\displaystyle{ 20 \equiv 0 \pmod{2} \Rightarrow 20^{m} \equiv 0 \pmod{2}}\), \(\displaystyle{ 9 \equiv 1 \pmod{2} \Rightarrow 9^{n} \equiv 1 \pmod{2}}\), \(\displaystyle{ 20^{m}-9^{n} \equiv -1 \equiv 1 \pmod{2} \Rightarrow |20^{m}-9^{n}| \equiv 1 \pmod{2}}\). Zatem \(\displaystyle{ k}\) może być równe \(\displaystyle{ 1, \ 3, \ 5, \ 7, \ 9}\). Rozważmy teraz inne kongruencje:
\(\displaystyle{ \\ 20 \equiv 2 \pmod{3} \Rightarrow 20^{m} \equiv 1 \pmod{3} \vee 20^{m} \equiv 2 \pmod{3}}\), \(\displaystyle{ 9 \equiv 0 \pmod{3} \Rightarrow 9^{n} \equiv 0 \pmod{3}}\), \(\displaystyle{ 20^{m}-9^{n} \equiv 1 \pmod{3} \vee 20^{m}-9^{n} \equiv 2 \pmod{3} \Rightarrow \\ \Rightarrow |20^{m}-9^{n}| \equiv 1 \pmod{3} \vee |20^{m}-9^{n}| \equiv 2 \pmod{3}}\).
Stąd \(\displaystyle{ k}\) nie może być równe \(\displaystyle{ 3}\), ani \(\displaystyle{ 9}\). Dalej mamy: \(\displaystyle{ 20 \equiv 0 \pmod{4} \Rightarrow 20^{m} \equiv 0 \pmod{4}}\), \(\displaystyle{ 9 \equiv 1 \pmod{4} \Rightarrow 9^{n} \equiv 1 \pmod{4}}\), \(\displaystyle{ 20^{m}-9^{n} \equiv -1 \equiv 3 \pmod{4} \Rightarrow |20^{m}-9^{n}| \equiv -1 \equiv 3 \pmod{4}}\). Stąd \(\displaystyle{ k}\) nie może być równe \(\displaystyle{ 1}\), ani \(\displaystyle{ 5}\). Zostaje nam tylko \(\displaystyle{ k=7}\). Kolejne miłe i kochane kongruencje:
\(\displaystyle{ 20 \equiv 0 \pmod{5} \Rightarrow 20^{m} \equiv 0 \pmod{5}}\), \(\displaystyle{ 9 \equiv -1 \pmod{5} \Rightarrow 9^{n} \equiv 1 \pmod{5} \vee 9^{n} \equiv -1 \pmod{5}}\), \(\displaystyle{ 20^{m}-9^{n} \equiv 1 \pmod{5} \vee 20^{m}-9^{n} \equiv -1 \pmod{5} \Rightarrow \\ \Rightarrow |20^{m}-9^{n}| \equiv 1 \pmod{5} \vee |20^{m}-9^{n}| \equiv -1 \pmod{5}}\).
Wobec tego \(\displaystyle{ k \neq 7}\). Otrzymaliśmy sprzeczność z założeniem, że istnieją takie całkowite dodatnie \(\displaystyle{ m}\) i \(\displaystyle{ n}\), że \(\displaystyle{ |20^{m}-9^{n}| < 11}\). Zatem wyrażenie \(\displaystyle{ |20^{m}-9^{n}|}\) najmniejszą wartość przy całkowitych dodatnich \(\displaystyle{ m}\) i \(\displaystyle{ n}\) osiąga dla \(\displaystyle{ m=1}\) i \(\displaystyle{ n=1}\) i wynosi ona \(\displaystyle{ 11}\).

Zadanie 6.:    

\(\displaystyle{ \newrgbcolor{zzttqq}{0.6 0.2 0}
\newrgbcolor{ffqqtt}{1 0 0.2}
\newrgbcolor{ttfftt}{0.2 1 0.2}
\newrgbcolor{qqwuqq}{0 0.392156862745098 0}\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=o,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-5.643230452674915,-3.716059670781891)(10.236769547325116,4.383940329218105)
\pspolygon[linecolor=zzttqq,fillcolor=white,fillstyle=solid,opacity=0.1](-3.680967078189314,-2.941244855967079)(5.049032921810705,-2.971244855967079)(-0.830967078189308,2.878755144032921)
\psline[linecolor=ffqqtt](-2.660522809956742,-0.85739024505004)(1.358870313464176,-2.958563884804377)
\psline[linecolor=ttfftt](1.650154309547645,0.410292538886467)(1.358870313464176,-2.958563884804377)
\psline[linecolor=ffqqtt](-0.830967078189308,2.878755144032921)(-2.660522809956742,-0.85739024505004)
\psline[linecolor=ffqqtt](5.049032921810705,-2.971244855967079)(1.358870313464176,-2.958563884804377)
\psline[linecolor=ttfftt](1.650154309547645,0.410292538886467)(-0.830967078189308,2.878755144032921)
\psline[linecolor=ttfftt](1.358870313464176,-2.958563884804377)(-3.680967078189314,-2.941244855967079)
\psline(-2.660522809956742,-0.85739024505004)(-3.680967078189314,-2.941244855967079)
\psline(1.650154309547645,0.410292538886467)(5.049032921810705,-2.971244855967079)
\psline(-0.830967078189308,2.878755144032921)(1.358870313464176,-2.958563884804377)
\psline(-2.660522809956742,-0.85739024505004)(1.650154309547645,0.410292538886467)
\psline(-2.237259898994833,0.006957173124803)(2.070437057367352,-0.007845909199465)
\pscustom[linecolor=qqwuqq,fillcolor=qqwuqq,fillstyle=solid,opacity=0.1]{\parametricplot{3.138156240999806}{3.427609201144603}{1.400000000000003*cos(t)+0.249577694657634|1.400000000000003*sin(t)+-0.00158866053036}\lineto(0.249577694657634,-0.00158866053036)\closepath}
\begin{scriptsize}
\psdots[dotstyle=*,linecolor=blue](-3.680967078189314,-2.941244855967079)
\rput[bl](-4.003230452674912,-3.196059670781891){\blue{$A$}}
\psdots[dotstyle=*,linecolor=blue](5.049032921810705,-2.971244855967079)
\rput[bl](5.136769547325105,-2.856059670781892){\blue{$B$}}
\psdots[dotstyle=*,linecolor=blue](-0.830967078189308,2.878755144032921)
\rput[bl](-0.743230452674906,3.003940329218106){\blue{$C$}}
\psdots[dotstyle=*,linecolor=blue](-2.660522809956742,-0.85739024505004)
\rput[bl](-3.02323045267491,-0.956059670781892){\blue{$Q$}}
\psdots[dotstyle=*,linecolor=blue](1.650154309547645,0.410292538886467)
\rput[bl](1.736769547325099,0.523940329218107){\blue{$P$}}
\psdots[dotstyle=*,linecolor=blue](1.358870313464176,-2.958563884804377)
\rput[bl](1.436769547325098,-2.836059670781892){\blue{$R$}}
\psdots[dotstyle=*,linecolor=blue](0.249577694657634,-0.00158866053036)
\rput[bl](0.076769547325096,-0.416059670781893){\blue{$D$}}
\psdots[dotstyle=*,linecolor=blue](-2.237259898994833,0.006957173124803)
\rput[bl](-2.58323045267491,-0.016059670781893){\blue{$S$}}
\psdots[dotstyle=*,linecolor=blue](2.070437057367352,-0.007845909199465)
\rput[bl](2.1567695473251,0.103940329218107){\blue{$T$}}
\rput[bl](-0.843230452674906,-0.236059670781893){\black{$\theta$}}
\end{scriptsize}
\end{pspicture*}}\)
Na rysunku kolorem zielonym ozaczono odcinki o długości \(\displaystyle{ x}\), zaś kolorem czerwonym odcinku o długości \(\displaystyle{ y}\). Długość odcinka \(\displaystyle{ BP}\) oznaczmy jako \(\displaystyle{ f}\), zaś \(\displaystyle{ AQ}\) jako \(\displaystyle{ g}\). Z równości odpowiednich boków wynika, że czworokąt \(\displaystyle{ PCQR}\) jest deltoidem. Zatem kąt między jego przekątnymi jest prosty, oraz odcinki \(\displaystyle{ CD}\) i \(\displaystyle{ DR}\) są równej długości \(\displaystyle{ k}\). Nazwijmy punkt przecięcia przekątnych tego deltoidu \(\displaystyle{ D}\). Załóżmy, że prosta \(\displaystyle{ PQ}\) nie jest równoległa do prostej \(\displaystyle{ AB}\). Poprowadźmy przez punkt \(\displaystyle{ D}\) prostą równoległą do prostej \(\displaystyle{ AB}\). Niech \(\displaystyle{ S}\) będzie punktem przecięcia tej prostej z odcinkiem \(\displaystyle{ AC}\), zaś \(\displaystyle{ T}\) z odcinkiem \(\displaystyle{ BC}\). Prosta \(\displaystyle{ PQ}\) dzieli trójkąt \(\displaystyle{ ABC}\) na trójkąt \(\displaystyle{ PQC}\) i czworokąt \(\displaystyle{ ABPQ}\), przy czym jeden z punktów \(\displaystyle{ S}\) i \(\displaystyle{ T}\) należy do trójkąta \(\displaystyle{ PQC}\), zaś drugi do czworokąta \(\displaystyle{ ABPQ}\). Załóżmy bez straty ogólności, że punkt \(\displaystyle{ S}\) należy do tego trójkąta, zaś \(\displaystyle{ T}\) do czworokąta (dla sytuacji odwrotnej analogiczne rozumowanie). Zatem punkt \(\displaystyle{ S}\) leży na odcinku \(\displaystyle{ CQ}\), a \(\displaystyle{ T}\) na odcinku \(\displaystyle{ BP}\). Miarę kątów wierzchołkowych \(\displaystyle{ PDT}\) i \(\displaystyle{ QDS}\) oznaczmy jako \(\displaystyle{ \theta}\). Niech \(\displaystyle{ |PT|=m}\) i \(\displaystyle{ |QS|=n}\). Z podobieństwa trójkątów \(\displaystyle{ TCD}\) i \(\displaystyle{ BCR}\) mamy:

\(\displaystyle{ \frac{x+m}{f+x}=\frac{k}{2k} \Leftrightarrow f=x+2m \quad (1)}\)
oraz:

\(\displaystyle{ \frac{|DT|}{y}=\frac{k}{2k} \Leftrightarrow |DT|=\frac{y}{2} \quad (2)}\)
Z podobieństwa trójkątów \(\displaystyle{ SCD}\) i \(\displaystyle{ ACR}\) mamy:

\(\displaystyle{ \frac{y-n}{g+y}=\frac{k}{2k} \Leftrightarrow g=y-2n \quad (3)}\)
oraz:

\(\displaystyle{ \frac{|DS|}{x}=\frac{k}{2k} \Leftrightarrow |DT|=\frac{x}{2} \quad (4)}\)
Z równań (1) i (3):

\(\displaystyle{ f+g=x+y+2(m-n) \quad (5)}\)
Z twierdzenia sinusów dla trójkąta \(\displaystyle{ PDT}\) mamy:

\(\displaystyle{ \frac{m}{\sin \theta}=\frac{|DT|}{\sin \angle DPT}=\frac{\frac{y}{2}}{\sin (180^{\circ}-\angle DPC)}=\frac{y}{2\sin \angle DPC} \Leftrightarrow m = \frac{y\sin \theta }{2\sin \angle DPC} \quad (6)}\)
Z trójkąta prostokątnego \(\displaystyle{ DPC}\): \(\displaystyle{ \sin \angle DPC = \frac{k}{x}}\), więc \(\displaystyle{ m=\frac{xy \sin \theta}{2k}}\). Z twierdzenia sinusów dla trójkąta \(\displaystyle{ QDS}\) mamy:

\(\displaystyle{ \frac{n}{\sin \theta}=\frac{|DS|}{\sin \angle DQS}=\frac{\frac{x}{2}}{\sin DQC}=\frac{x}{2\sin \angle DQC} \Leftrightarrow n = \frac{x\sin \theta }{2\sin \angle DQC} \quad (7)}\)
Z trójkąta prostokątnego \(\displaystyle{ DQC}\): \(\displaystyle{ \sin \angle DQC = \frac{k}{y}}\), więc \(\displaystyle{ n=\frac{xy \sin \theta}{2k}}\). Zatem \(\displaystyle{ m=n}\) co wraz z równaniem (5) daje nam \(\displaystyle{ f+g=x+y}\), a tu po dodaniu stronami \(\displaystyle{ x+y}\) otrzymujemy tezę. Przypadek gdy równoległe wrzucę później.

Zadanie 7.:    

Naprawdę myśleliście, że umiem stereo?

Zadanie 8.:    

Na początek rozważmy sytuację, gdy istnieje choć jeden wiersz lub kolumna nie zawierająca wyróżnionego pola. Wyróżnione pole nazwijmy narożnym, gdy nie jest jedynym wyróżnionym polem w swoim wierszu i kolumnie. Pozostałe wyróżnione pola nazwijmy nienarożnymi. Usuńmy z planszy wszystkie wiersze i kolumny zawierające jedno pole wyróżnione. Oczywiście w ten sposób pewne pola narożne mogą stać się polami nienarożnymi. Wtedy powtarzamy procedurę usuwania wierszy i kolumn, aż na planszy nie pozostanie żadne nienarożne pole. Pokażmy, że na planszy zostały pewne wyróżnione - narożne pola. Załóżmy, że usunęliśmy wszystkie wyróżnione pola. Z każdym usuniętym polem możemy skojarzyć choć jeden usunięty wiersz, albo jedną usuniętą kolumnę w której się znajdował. Ostatnie usunięte wyróżnione pole było jedynym wyróżnionym polem w swym wierszu i w swej kolumnie, więc z nim kojarzymy dwa usunięte wiersze i kolumny. Wobec tego liczba usuniętych wierszy i kolumn jest większa równa \(\displaystyle{ 2n}\), tymczasem liczba wierszy i kolumn możliwych do usunięcia to liczba wierszy i kolumn na całej planszy (\(\displaystyle{ 2n}\)) minus liczba wierszy i kolumn nie zawierających wyróżnionych pól. Czyli z jednej strony liczba wierszy i kolumn \(\displaystyle{ x}\), spełnia nierówność: \(\displaystyle{ x \geq 2n}\), zaś z drugiej: \(\displaystyle{ x \leq 2n-1}\). Tu otrzymujemy sprzeczność z założeniem, że opisane usuwanie wierszy i kolumn prowadzi do usunięcia wszystkich wyróżnionych pól. Na planszy zostały pewne narożne pola (oczywiście w liczbie większej równej \(\displaystyle{ 4}\)). Z każdego narożnego pola możemy się przemieścić do innego znajdującego się w tym samym wierszu lub kolumnie i tak dalej, przy czym jeśli ostatni ruch był po jednym wierszu to kolejny powinien zostać wykonany po jednej kolumnie i na odwrót. Ponieważ liczba narożnych pól jest skończona, zaczniemy poruszać się w koło. Może się zdarzyć, że dopiero od pewnego pola trafimy na cykl, wtedy oczywiście odrzucamy pola początkowe. I ów cykl wystarczy zamalować na zielono. Ponieważ z każdego pola przemieszczamy się do drugiego pola w tym samym wierszu lub kolumnie, w każdym wierszu i kolumnie z polem należącym do cyklu jest parzysta liczba zamalowanych pól. W pozostałych wierszach i kolumnach jest zero zamalowanych pól, czyli także liczba parzysta. Co w wypadku gdy nie istnieją wiersze i kolumny bez zamalowanych pól? Wtedy liczba wierszy i kolumn do usunięcia to \(\displaystyle{ 2n}\). Postępujemy analogicznie jak w poprzednim przypadku - usuwamy odpowiednie wiersze i kolumny. Jeśli znajdziemy cykl, to malujemy jak poprzednio. Jeśli nie znajdziemy cyklu - usuniemy wszystkie wiersze i kolumny, to \(\displaystyle{ x=2n}\), a tę wartość uzyskamy gdy z każdym wyróżnionym polem (prócz ostatniego) skojarzyć będziemy mogli tylko jeden wiersz lub kolumnę. Tak będzie gdy każde wyróżnione pole (prócz jednego) nie będzie jedynym w swym wierszu lub kolumnie. Czyli poruszając się po tych polach raz po wierszu, raz po kolumnie uzyskamy "łańcuch". Ponieważ w każdym wierszu i w każdej kolumnie musi być ponad jedno wyróżnione pole, w każdym wierszu i kolumnie muszą być dwa wyróżnione pola (prócz jednego wiersza i jednej kolumny) - by ich suma dopełniala się do \(\displaystyle{ 2n-1}\). Malowanie zaczniemy od jedynego wyróżnionego pola, które jest samotne w swym wierszu lub kolumnie - o tym polu już wspominano wyżej bez żadnych wyjaśnień. Od niego zaczynamy malowanie co drugiego wyróżnionego pola w łańcuchu. Wówczas w każdym wierszu i każdej kolumnie mamy pomalowane jedno z dwóch wyróżnionych pól (lub z jednego pola w owym jedynym wierszu i kolumnie). Czyli niewątpliwie w każdym wierszu i w każdej kolumnie mamy nieparzystą liczbę pomalowanych pól.

[chomikchomik]

siódme to był chyba, obok 5, największy banał drugiej serii-- 6 lis 2012, o 20:19 --trzeba było zbudować drugi trójkąt na płaszczyźnie ABD przystający do trójkąta ABO, gdzie O jest środkiem okręgu opisanego na trójkącie ABC. zliczyć kąty i skorzystać z twierdzenia o rzucie prostokątnym prostej na płaszczyznę. a przynajmniej ja tak zrobiłem może ktoś podać rozwiązanie 6 menelaosem? bo ja robiłem z tw. sinusów

[Errichto]

@Ponewor, ja zrozumiałem to i komisja zrozumie. No chyba że nie widzę blefa, ale raczej tak nie jest.
Widzicie? Da się bez grafów.

@chomikchomik, niebieskie książeczki Olimpiady Informatycznej
a siódme nie było banałem... dopiero kilka dni temu zauważyłem, że ten punkt styczności to środek okręgu opisanego.

[ElEski]

Mam pytanko;
Czy ktoś z Was wie jak ładnie skonstruować dużo nierównobocznych trójkątów, w których będzie mogło być spełnione to, co w 6?

[Errichto]

@ElEski - Bierzesz jakieś równo oddalone A,R,P,C (jest takich możliwości całkiem sporo). Przydałoby się, żeby tworzyły tak jakby część wielokąta wypukłego. Na prostej AC zaznaczasz taki punkt, by był równo oddalony od R i C (chyba można dzięki tej wypukłości). Na prostej PC zaznaczasz punkt oddalony od R o tyle samo co pierwszy zaznaczony od R i C.
Ale ręki ani innych ważnych części ciała za to uciąć nie dam.

[chomikchomik]

ja dopiero wczoraj zobaczyłem, że w 6 chodzi o trójkąt. robiłem na czworościanie. myślicie, że mi uznają, czy ciachną trochę punktów? i co to za "niebieskie książeczki informatyczne"? bo z tego co wiem, na oi jest sporo kombinatoryki. ale w sumie to nie wiem.

[Errichto]

ja dopiero wczoraj zobaczyłem, że w 6 chodzi o trójkąt

Jesteś moim mistrzem.
Ew. pisz reklamację, jeśli zrobiłeś ogólniejszy przypadek (chociaż chyba tak nie jest).


jeśli chodzi o grafy, to chyba warto się z informatycznych książek uczyć. Takie w miarę proste rzeczy można na

Kod: Zaznacz cały

http://informatyka.wroc.pl/

znaleźć. Przecież nie trzeba na implementację (kody) patrzeć.

[cyberciq]

Nie chce mi się powyżej czytać czy ktoś tak robił, ale do 8 jeszcze szkic szybki:

Ukryta treść:    

Jeśli dla pewnego \(\displaystyle{ n}\) istnieje na planszy takie ustawienie wyróżnionych pól, że nie da się pokolorować aby zachodziła teza to dla \(\displaystyle{ n-1}\) także takie ustawienie istnieje, dalej dla \(\displaystyle{ n=1,2}\) nie istnieje takie ustawienie,żeby pokolorowanie było takie,że teza nie zachodzi, dalej z prawa kontrapozycji wynikała teza czy jakoś tak

[timon92]

Mam pytanko;
Czy ktoś z Was wie jak ładnie skonstruować dużo nierównobocznych trójkątów, w których będzie mogło być spełnione to, co w 6?

w każdym trójkącie w którym \(\displaystyle{ AC+BC=2AB}\) znajdziesz takie punkty jakie są w zadaniu

może ktoś podać rozwiązanie 6 menelaosem?

jak u Ponewora pokazujemy, że \(\displaystyle{ CR, PQ, ST}\) tną się w jednym punkcie, teraz zapisujemy Menelaosa dla trójkąta \(\displaystyle{ AST}\) i prostej \(\displaystyle{ PQ}\) i wychodzi że \(\displaystyle{ PT=SQ}\), a to jest równoważne tezie

[porfirion]

cyberciq, mógłbyś rozwinąć swoje rozumowanie? Pomysł jest bardzo ciekawy, ale jak to udowodniłeś?

[Swistak]

8 zadanie jest prześwietne : D. Choć w tym roku chyba naprawdę mieli bardzo mały wybór zadań, to jak standardowe/nieoryginalne są 3, 4, 5 woła o pomstę do nieba : |. A przede wszystkim 4. Zadanie, które widziałem jakieś 10 razy może się pojawić na kółku szkolnym, a nie na olimpiadzie xdd. I do tego popatrzcie na zadanie 5 z finału LI OM. Pomimo tego, że samo zadanie 8 jest naprawdę piękne, to 51-3-5 sprawia, że jego obecność na I etapie jest dość kompromitująca.