LXIV (64) OM - I etap

[opilo]

Jeśli nie rozpatrzyłem przypadku jak w wzorcówce w=2y, tylko podzieliłem bo się wydawało oczywiste, to zetną? a jeśli tak, to ile?

[marker1995]

pewnie 1 punkt Tobie urwą, chociaż zależy od humoru sprawdzającego

[silicium2002]

Jak dla mnie to masło maślane przecież skoro Jurek może wykonać dany ruch po jednej stronie 1007 kąta ( połowa danego 2012 kąta)
to oczywiste jest że na drugim 1007 kącie również da się wykonać symetryczny ruch.
Wydaje mi się że autorzy zadania nie zauważyli że rozwiązanie jest aż tak oczywiste i stąd ta
rażąco szczegółowa firmówka

Nie wydaje mi się, żeby to było oczywiste aż do pominięcia. Będą ciąć. Ja to napisałem

[HuBson]

no ale przecież skoro Michał miałby zrobić niedozwolony ruch to Jurek musiałby go w tym uprzedzić...

...ani wspólnych końców z wcześniej narysowanymi przekątnymi.

swoją drogą nie wiem jakie to ma znaczenie czy mają wspólne końce czy nie chyba napisali tak żeby zmylić

[opilo]

Nie mówiąc o tym że zad.3 z I serii było w teorii Sierpińskiego, t. II ...

[HuBson]

Nie wydaje mi się, żeby to było oczywiste aż do pominięcia. Będą ciąć. Ja to napisałem

a jak myślicie, ile mogą za to uciąć punktów jak ktoś ma skrócone rozwiązanie ?

[silicium2002]

Nie wydaje mi się, żeby to było oczywiste aż do pominięcia. Będą ciąć. Ja to napisałem

a jak myślicie, ile mogą za to uciąć punktów jak ktoś ma skrócone rozwiązanie ?

Myślę, że do pięciu

[porfirion]

Nikt się jeszcze nie pochwalił rozwiązaniami II serii? :p
5 bardzo proste i dość sztampowe.
6 ładnie szło z menelaosa, można też bardzo krótko uzasadnić z tw. sinusów.
7 - bardzo fajne zadanie - obrót \(\displaystyle{ C}\) względem AB do płaszczyzny \(\displaystyle{ ABD}\), tw. odwrotne do twierdzenia pomiędzy styczną i cięciwą, najmocniejsze tw. stereometrii, tw. o trzech prostych prostopadłych i pyka.
8 - warto było rozważyć graf dualny kolumny - wiersze, zobaczyć co się dzieje gdy jet w nim cykl i co kiedy go nie ma.

Bardzo fajne zadanka.

[HuBson]

ale zdecydowanie bardziej harde od I serii

pierwszego zadanie nie wrzucam bo nie warto
tak skrótowo

Zad 8:    

ja robiłem tak że jeśli w conajmniej jednej kolumnie lub wierszu nie było wyróżnionego pola to wykreślałem te kolumny i wiersze gdzie zanjdowało się maxymalnie jedno pole wyróżnione pole jeżeli się nie da wykreślić to znaczy że mamy "obwód" pól (wcześniej udowodniłem że nie da się wykreślić wszystkich kolumn i wierszy jeśli w conjamniej jednej kolumnie lub wierszu nie zanjduje się wyróżnione pole) no a jeśli w każdej kolumnie i w każdym wierszu jest conjamniej jedno wyróżnione pole i każdy ma conajmniej jednego sąsiada w wierszu lub kolumnie to zaczynamy malowanie od tego gdzie nie ma żadnego sąsiada w wierszu lub kolumnie (lub tutaj w zanczeniu tu albo tu) dalej malujemy najbliższego sąsiada jeżeli dojdziemy do sytuacji gdzie w wierszu lub kolumnie znajduję się parzysta liczba wyróżnionych pól to "odbijamy" na bok i nie malujemy przed ostatniego pola (tego co ma sąsiadów i w wierszu i w kolumnie)zawsze da sie odbić bo liczba wszystkich wyróżnionych pól jest \(\displaystyle{ 2n-1}\) czyli nieparzysta

fajnie by było jakby ktoś wrzucił 6 i 7
w 7 zauważyłem też tą możliwość odbicia punktu \(\displaystyle{ C}\)
na drugą płaszczyznę ale nie wiedziałem co dalej zrobić

[sympatyczny]

ZADANIE 5

\(\displaystyle{ min}\) { \(\displaystyle{ {\left| 20 ^{m} - 9 ^{n} \right| : m, n \in N}\)} \(\displaystyle{ = 11}\)

Dla \(\displaystyle{ m = n = 1}\)

\(\displaystyle{ \left|20 ^{m} - 9 ^{n} \right|}\) = \(\displaystyle{ \left|20 - 9 \right|}\) = \(\displaystyle{ 11}\)

Pokażemy, że jest to najmniejsza wartość. Ponieważ liczba \(\displaystyle{ 20 ^{m} - 9 ^{n}}\) nie może być podzielna przez \(\displaystyle{ 2,3}\) i \(\displaystyle{ 5}\) wystarczy udowodnić, że

\(\displaystyle{ 20 ^{m} - 9 ^{n} \neq \pm 1, \pm 7}\)

Zauważmy prawdziwość następujących kongruencji

\(\displaystyle{ 20 ^{m} \equiv (-1) ^{m}}\) \(\displaystyle{ mod}\) \(\displaystyle{ 3}\)

\(\displaystyle{ 9 ^{n} \equiv (-1) ^{n}}\) \(\displaystyle{ mod}\) \(\displaystyle{ 5}\)

\(\displaystyle{ 20 ^{m} \equiv (-1) ^{m}}\) \(\displaystyle{ mod}\) \(\displaystyle{ 7}\)

1. \(\displaystyle{ 9 ^{n} = 20 ^{m} + 1}\)

Z przystawania

\(\displaystyle{ 20 ^{m} \equiv (-1) ^{m}}\) \(\displaystyle{ mod}\) \(\displaystyle{ 3}\)

\(\displaystyle{ m}\) musi być liczbą nieparzystą. Wówczas \(\displaystyle{ 20 ^{m} \equiv - 1}\) \(\displaystyle{ mod}\) \(\displaystyle{ 7}\) a więc \(\displaystyle{ 9^{n}}\) musiałoby być podzielne przez \(\displaystyle{ 7}\), co jest niemożliwe.

2.\(\displaystyle{ 9 ^{n} = 20 ^{m} - 1}\)

Tym razem \(\displaystyle{ m}\) musi być liczbą parzystą. Wówczas \(\displaystyle{ 20^{m} \equiv 1}\) \(\displaystyle{ mod}\) \(\displaystyle{ 7}\) i otrzymujemy tę samą sprzeczność.

3.\(\displaystyle{ 9 ^{n} = 20 ^{m} + 7}\)

Wówczas

\(\displaystyle{ 9 ^{n} \equiv (-1) ^{n}}\) \(\displaystyle{ mod}\) \(\displaystyle{ 5}\)

i

\(\displaystyle{ 20 ^{m} + 7 \equiv 2}\) \(\displaystyle{ mod}\) \(\displaystyle{ 5}\)

co znowu jest niemożliwe.

4.\(\displaystyle{ 9 ^{n} = 20 ^{m} - 7}\)

Wtedy prawa strona równości \(\displaystyle{ 20 ^{m} - 7 \equiv 3}\) \(\displaystyle{ mod}\) \(\displaystyle{ 5}\) a lewa \(\displaystyle{ 9 ^{n} \equiv (-1) ^{n}}\) \(\displaystyle{ mod}\) \(\displaystyle{ 5}\). Sprzeczność dowodzi fałszywości ostatniej równości.

[ElEski]

5,6,8 były niezbyt wymagające, 7 trochę trudniejsze może.

6:
niech \(\displaystyle{ B}\) będzie punktem symetrycznym względem \(\displaystyle{ P}\) do \(\displaystyle{ C}\), \(\displaystyle{ E}\) będzie punktem symetrycznym względem \(\displaystyle{ Q}\) do \(\displaystyle{ C}\). Wówczas \(\displaystyle{ ERC}\) i \(\displaystyle{ DRC}\) są prostokątne, \(\displaystyle{ E,R,D}\) leżą na jednej prostej.
(niech \(\displaystyle{ D}\) leży pod \(\displaystyle{ AB}\), \(\displaystyle{ E}\) nad). Korzystając z twierdzenia Melenaosa dla trójkąta \(\displaystyle{ ABC}\) i punktów \(\displaystyle{ E,R,D}\) oraz z równości odcinków w treści zadania, otrzymujemy tezę.

7:
\(\displaystyle{ C}\) rzutujemy na \(\displaystyle{ ABD}\), powstaje parę trójkątów prostokątnych i z tw. Pitagorasa wychodzi -.-

8:
Lemat z zadania \(\displaystyle{ 5}\) finału \(\displaystyle{ LI OM}\) o szachownicy\(\displaystyle{ m}\)x\(\displaystyle{ n}\) i \(\displaystyle{ m+n}\) polach w niej wybranych (możecie sobie znaleźć dowód, mój był akurat indukcyjny, nie wiem, jaki jest na stronie)
Teraz możemy zacząć rozwiązywać zadanie;
Niech wiersze będą nazwane \(\displaystyle{ W_{1},...,W_{n}}\),
kolumny \(\displaystyle{ K_{1},.....,K_{n}}\).
niech zbiór wierszy to będzie \(\displaystyle{ W}\), kolumn to będzie \(\displaystyle{ K}\).
Rozważamy graf dwudzielny, w którym krawędzie idą tylko od \(\displaystyle{ W}\) do \(\displaystyle{ K}\) oraz krawędź \(\displaystyle{ W_{i}K_{j}}\) istnieje wtedy i tylko wtedy, gdy w \(\displaystyle{ i}\)-tym wierszu i \(\displaystyle{ j}\)-tej kolumnie jest wybrane pole.
\(\displaystyle{ 2}\) przypadki:
\(\displaystyle{ 1.)}\)-spójny: wtedy udowodnimy, że da się pokolorować tak, żeby było wszęzie nieparzyście wiele kolorowych
\(\displaystyle{ 2.)}\)-niespójny: wtedy udowodnimy, że da się pokolorować tak, żeby było wszędzie parzyście wiele kolorowych.

Aha.. jeszcze co to znaczy "pokolorować". Teza zadania jest równoważna temu, że w takim grafie można wybrać niezerową liczbę krawędzi, żeby każdy wierzchołek był stopnia tej samej parzystości, do tego będziemy dążyć. Powiemy, że jeśli krawędź istnieje w danej chwili, to jest zapalona, jesli nie- zgaszona.

1.) Na początku zapalone są wszystkie krawędzie. Jeśli każdy wierzchołek ma stopień nieparzysty, to git. Jeśli nie, to jest parzyście wiele wierzchołków stopnia parzystego. Bierzemy dowolne \(\displaystyle{ 2}\) i rozważamy ścieżkę między nimi bez cykli. Zmieniamy stan każdej krawędzi na tej ścieżce; zmieniła się parzystość wierzchołka początkowego i końcowego i nic więcej, więc liczba wierzchołków stopnia nieparzystego jest większa o \(\displaystyle{ 2}\). Kontynuując takie postępowanie zrobimy każdy wierzchołek nieparzystego stopnia (oczywiście na koniec zostanie podświetlonych więcej niż \(\displaystyle{ 0}\) krawędzi)

2.) Istnieje zatem s spójnych składowych.
niech \(\displaystyle{ r_{1},...,r_{s}}\) będą liczbami wierzchołków każdej z nich.
Istnieje \(\displaystyle{ k}\), że \(\displaystyle{ r_{k}}\) ma k lub więcej krawędzi, a dla niego działa nasz lemat więc ten przypadek też rozwiązaliśmy

[Mszak]

6 bardzo ładnie i prosto szło z środków ciężkości.

[przemos01]

5 bardzo proste: tu widziałem długie rozwiązanie a wystarczy wykazać z mod 10 że to wyrażenie przystaje do -1 v 1 mod10, czyli jeżeli jest mniejsze od 11 to jest równe 1 lub 9. 9 wywalamy od razu z mod 9 i zostaje udowodnić że wyrażenie nie jest równe 1.
6 nie zrobiłem, a siedziałem dosyć długo. Na Menelaosa nie wpadłem, a szkoda... -.-
7 W mojej opinii tylko 4 było prostsze od niego. Najpierw rzutujemy środek sfery na płaszczyzne ABD, łatwo zauważyć że rzut będzie dokładnie w punkcie styczności sfery z tą płaszczyzną. Prowadzimy z tego punktu(powiedzmy X) odcinki do A i B i z najmocniejszego twierdzenia stereometrii wychodzi że trójkąty ABO(gdzie O to śr. okręgu opisanego na ABC) i ABX są przystające. No i teraz kąt OAB=\(\displaystyle{ 90-\alpha}\), bo kąt AOB=2*ACB=\(\displaystyle{ 2\alpha}\). No a w takim razie kąt DAX=\(\displaystyle{ \alpha + 90-\alpha=90}\) zate, DAX jest prosty i z twierdzenia o trzech prostych mamy że w takim razie DAS jest prosty czyli AD prostopadłe do AS

8. Zabrakło mi sprytnego wykończenia, o ile wykminiłem, jak większość najprawdopodobniej, że dowolna permutacja wierszy i kolumn jest przekształceniem "równoważnym", uszeregowałem rosnąco wiersze i kolumny względem ilości wyróżnionych pól, oddzieliłem ostatni wiersz i ostatnią kolumnę, w której były co najwyżej 2 pola, ale dalej już nic konkretnego nie wymyśliłem. To znaczy typowe pałowanie: dowodziłem dla jakiś szczególnych przypadków, został mi na prawdę ostatni przypadek(gdy planszę n-1xn-1 można pokolorować na nieparzysto, ale nie da się na parzysto, gdy są dokładnie 2 pola w ostatnim wierszu+kolumnie, odpowiednio: 1 w wierszu i 1 w kolumnie, a kolejne plansze: n-2xn-2, n-3xn-3 w skutek permutacji nigdy nie będzie się dało żadnej z nich pokolorować na parzysto... ) ale już nie wymyśliłem... Ale na serio się namęczyłem

3 seria wydaje mi się przyjemniejsza niż chociażby w zeszłym roku więc powinno być spoko

[K-mil]

Zad 6
Oznaczamy przez \(\displaystyle{ M}\) środek boku \(\displaystyle{ AC}\) a przez \(\displaystyle{ N}\) środek boku \(\displaystyle{ BC}\). Prosto dowodzimy że proste \(\displaystyle{ CR}\), \(\displaystyle{ MN}\) i \(\displaystyle{ QP}\) przecinają się w jednym punkcie ( nie trzeba do tego Menelaosa itp ). No i teraz stosujemy tw sinusów i dochodzimy do tego że \(\displaystyle{ MQ=PN}\), a stąd już łatwo wynika teza

[Errichto]

5. jakoś prosto
6. tw. sinusów
7. (jak przemos niemalże)
\(\displaystyle{ Q}\) to punkt styczności sfery z płaszczyzną \(\displaystyle{ ABC}\)
\(\displaystyle{ \angle BQA = 2 \angle BCA \\ \angle BAQ = \frac{180- \angle BQA}{2}}\) bo to równoramienny
z najmocniejszego tw. stereometrii \(\displaystyle{ \angle BAK = \angle BAQ}\) gdzie \(\displaystyle{ K}\) jest punktem styczności tej sfery z płaszczyzną \(\displaystyle{ ABD}\).
do tego mamy \(\displaystyle{ \angle KAD = \angle BAD + \angle BAK}\)
a po podstawieniu otrzymamy, że \(\displaystyle{ \angle KAD}\) jest prosty. Mamy 3 trójkąty prostokątne SKA, SKD, KAD. Oznaczamy długości \(\displaystyle{ SK}\), \(\displaystyle{ AK}\), \(\displaystyle{ DK}\) jako \(\displaystyle{ r}\), \(\displaystyle{ a}\), \(\displaystyle{ d}\), piszemy co wiemy z Pitagorasa i mamy tezę z tw. odwrotnego do Pitagorasa.
8. Kolumny i wersy to wierzchołki grafu. Krawędź mamy, gdy w przecięciu łączonego wersu i kolumny jest wyróżnione pole. Jeśli jest cykl, to odpowiadające temu cyklowi malowanie spełnia warunek z parzystością wszystkiego. Jeśli nie ma, to mamy drzewo (bo o 1 mniej krawędzi niż wierzchołków). Idziemy od liści, chcemy nieparzystego stopnia dla każdego wierzchołka. Usuwamy krawędzie prowadzące do ojców lub je zostawiamy zależnie od parzystości tegoż liścia. I po takim rozważeniu listka, przechodzimy do reszty drzewa czyli zredukowanego o 1. Po jakimś czasie zostaną 2 wierzchołki. Gdyby były różnej parzystości, to nie dałoby się ustalić co zrobić z ostatnią krawędzią. Ale gdyby istotnie tak było, to nie zgadza się suma końców krawędzi - każdy kij ma 2 końce czyli końców jest parzyście wiele. A przy \(\displaystyle{ 2n-2}\) wierzchołkach nieparzystych i jeszcze dwóch o różnej parzystości wcale nie otrzymujemy parzystej sumy "końców". Czyli te 2 ostatnie są tej samej parzystości i możemy zdecydować o istnieniu lub wywaleniu ostatniej krawędzi. Niewywalone krawędzie odpowiadają malowaniu dającemu wszędzie nieparzystą liczbę pomalowanych pól.