LXIII Olimpiada Matematyczna II etap.

[kaszubki]

Próg 19, bo nawet jak kogoś geometria przyprawia o mdłości, to bez problemu mógł skminić 3,5 zadania. Moim zdaniem zadania zbyt proste jak na 2 etap, no ale bywa. Niedługo jest romanian, to tam nie będę narzekał na proste zadania.

[michal_z]

No cóż, mój powszechny hejt na zadania z systemem dziesiętnym, a szczególnie z suma cyfr dały się we znaki. Pewnie za tym wszystkim stoi Kamil Duszenko .
Mi udało się wymyślić nieźle porąbane rozw. 6. Zacznę od tego, że jest niekonstruktywne .

Szkic mojego 6:
Główna idea: Znaleźć takie \(\displaystyle{ n}\), żeby \(\displaystyle{ 2^n}\) miało dużo dziewiątek na końcu, które się wykasują po dodaniu do tego \(\displaystyle{ n}\)
Lemat 1: \(\displaystyle{ 5^k}\) oraz \(\displaystyle{ 2^k}\) mają łącznie \(\displaystyle{ k+1}\) cyfr.
Lemat 2: \(\displaystyle{ v_p(a^n-b^n)=v_p(a-b)+v_p(n)}\), gdzie \(\displaystyle{ v_p(k)}\) to wykładnik najwyższej potęgi \(\displaystyle{ p}\), która dzieli \(\displaystyle{ k}\), \(\displaystyle{ p|a-b}\) (tzw. Lifting The Exponent Lemma)
Lemat 3: Istnieje nieskończenie wiele takich \(\displaystyle{ c}\), że \(\displaystyle{ 5^c}\) zaczyna się w zapisie dziesiętnym cyframi \(\displaystyle{ 11}\) (powszechnie znany lemat dla potęg dwójki i z góry zadanego ciągu cyfr)
Użycie właśnie tych lematów stanie się prostsze w trakcie rozwiązania.
Dla każdego takiego \(\displaystyle{ c}\), że \(\displaystyle{ 5^c}\) zaczyna się cyframi \(\displaystyle{ 11}\) wskażę pewne \(\displaystyle{ n}\) spełniające żądaną nierówność i zawsze będą to różne wartości. Łącząc to z lematem 3 udowodnię tezę zadania.
Ustalmy zatem \(\displaystyle{ c}\).
Rozpatrzmy możliwe wartości \(\displaystyle{ n=2^c, 2^c+1, ..., 2^c+4 \cdot 5^{c-1} -1}\).
Na mocy lematu 2 po pewnych obliczeniach dostaniemy, że jeżeli \(\displaystyle{ 10^c|2^a-2^b}\), to \(\displaystyle{ 4 \cdot 5^{c-1}|a-b}\), z czego wynika w prosty sposób, że liczby postaci \(\displaystyle{ 2^n}\) dla rozpatrywanych wartości \(\displaystyle{ n}\) dają różne reszty z dzielenia przez \(\displaystyle{ 10^c}\). Zauważmy też, że reszt z dzielenia przez \(\displaystyle{ 10^c}\) podzielnych przez \(\displaystyle{ 2^c}\), ale nie przez \(\displaystyle{ 5}\) jest \(\displaystyle{ 4 \cdot 5^{c-1}}\), a tylko takie mogą występować wśród takich wartości \(\displaystyle{ 2^n}\), zatem wszystkie one są przyjmowane przez odpowiednie \(\displaystyle{ 2^n}\) dokładnie raz. Ustalmy zatem nasze \(\displaystyle{ n}\), takie aby \(\displaystyle{ 2^n \equiv_{10^c} -2^c}\). Okazuje się, że spełnia ono warunki zadania. A czemu, to teraz to udowodnimy.
Zapiszmy \(\displaystyle{ 2^n}\) graficznie w postaci \(\displaystyle{ POCZATEK 99..99 KONIEC}\), gdzie KONIEC ma \(\displaystyle{ l}\) cyfr, gdzie \(\displaystyle{ l}\) to liczba cyfr \(\displaystyle{ 2^c}\). Blok 9 ma długość co najmniej \(\displaystyle{ c-l}\), a cyfra jedności początku nie jest 9.
Wtedy \(\displaystyle{ S(2^n) \geq S(POCZATEK)+9(c-l)+2}\)
Popatrzmy teraz na liczbę \(\displaystyle{ 2^n+n}\) jako na sumę \(\displaystyle{ 2^n+2^c}\) i \(\displaystyle{ n-2^c}\), pamiętajmy, że \(\displaystyle{ 2^c \leq n <2^c + 4 \cdot 5^{c-1}}\), obie są superważne .
\(\displaystyle{ S(2^n+2^c)=S(POCZATEK)+1=S(POCZATEK)+1}\).
\(\displaystyle{ 2^n+2^c}\) ma \(\displaystyle{ \geq c}\) zer na końcu zatem \(\displaystyle{ S(2^n+c)=S(2^n+2^c)+S(n-2^c)}\).
\(\displaystyle{ n-2^c<4 \cdot 5^{c-1}}\), ale \(\displaystyle{ 5^c}\) zaczyna się na \(\displaystyle{ 11}\), zatem \(\displaystyle{ 4 \cdot 5^{c-1}}\) ma dokładnie \(\displaystyle{ 1}\) cyfrę mniej niż \(\displaystyle{ 5^c}\). A \(\displaystyle{ 5^c}\) na mocy lematu 1 ma ich \(\displaystyle{ c+1-l}\), zatem \(\displaystyle{ 4 \cdot 5^{c-1}}\) ma ich \(\displaystyle{ c-l}\), zatem \(\displaystyle{ S(n-2^c) \leq 9(c-l)}\), czyli
\(\displaystyle{ S(2^n+c)=S(2^n+2^c)+S(n-2^c) \leq S(POCZATEK)+1 + 9(c-l)<S(POCZATEK)+9(c-l)+2 \leq S(2^n)}\).
UDAŁO SIĘ!!
Łatwo zauważyć, że zawsze produkujemy inne \(\displaystyle{ n}\), zatem jesteśmy w domu .

[Marcinek665]

Czy za nieuwzględnienie tego, że przecięcie symetralnej \(\displaystyle{ AI}\), prostej \(\displaystyle{ BC}\) i prostej \(\displaystyle{ OI}\) może leżeć po różnych stronach odcinka \(\displaystyle{ BC}\) będzie cięte? Bo rozumowanie wtedy jest zupełnie analogiczne, więc nie wiem.

[me123]

ja tam zrobiłam trzy: 1,3,4. Z moich znajomych także większość deklarowała 3, ale twierdzili, że pierwszy dzień łatwiejszy. podzielę się moim rozwiązaniem zadania 3.:

Ukryta treść:    

Niech \(\displaystyle{ a _{1},...,a _{m+1}}\) będą wybranymi przez nas liczbami, jeżeli dowolne dwie z nich mają wspólny dzielnik, to dzielimy je przez niego i nadajemy im nową wartość, uzyskaną po podzieleniu. Jeżeli w ten sposób dojdziemy do jedynki (dowolna liczba \(\displaystyle{ a _{i}}\) będzie równa 1), to oznacza, że początkowa wartość \(\displaystyle{ a _{i}}\) dzieli iloczyn pozostałych liczb. W przeciwnym wypadku, okazuje się, że musielibyśmy uzyskać po przekształceniach m+1 względnie pierwszych liczb (nie ma jedynki i nie ma wspólnych dzielników), a to daje sprzeczność bo mamy tylko m pierwszych liczb.

no i koniec

[TomciO]

podzielę się moim rozwiązaniem zadania 3.:

Ukryta treść:    

Niech \(\displaystyle{ a _{1},...,a _{m+1}}\) będą wybranymi przez nas liczbami, jeżeli dowolne dwie z nich mają wspólny dzielnik, to dzielimy je przez niego i nadajemy im nową wartość, uzyskaną po podzieleniu. Jeżeli w ten sposób dojdziemy do jedynki (dowolna liczba \(\displaystyle{ a _{i}}\) będzie równa 1), to oznacza, że początkowa wartość \(\displaystyle{ a _{i}}\) dzieli iloczyn pozostałych liczb. W przeciwnym wypadku, okazuje się, że musielibyśmy uzyskać po przekształceniach m+1 względnie pierwszych liczb (nie ma jedynki i nie ma wspólnych dzielników), a to daje sprzeczność bo mamy tylko m pierwszych liczb.

To nie jest poprawne.

Ukryta treść:    

Względnie pierwszość \(\displaystyle{ m+1}\) liczb, to nie jest to samo co względnie pierwszość parami. Np. liczby: \(\displaystyle{ 4, 6, 9}\) są względnie pierwsze jako trójka liczb, ale parami nie. No i widać, że jest ich trzy a mają w sumie tylko dwa dzielniki pierwsze

[Panda]

Jest, jest.
me123 w żadnym momencie nie chodzi o to, że wszystkie są względnie pierwsze. Jeśli jest jakaś para liczb nie względnie pierwszych, to dzieli przez \(\displaystyle{ NWD}\) i otrzymuje parę liczb względnie pierwszych. Może tak robić, bo przy mnożeniu \(\displaystyle{ m}\) liczb, przynajmniej jedna by brała udział, więc de facto dzielimy przez coś, co by było wtedy fragmentem \(\displaystyle{ NWD}\) i nic nie psuło.

Swoją drogą, piękne rozwiązanie, bardzo mi się podoba.

[Wysublimowany_Nick]

Podzielę się swoim 5-tym, bo jeszcze nie było żadnego, a wzorcówka mi się nie podoba.

Ukryta treść:    

\(\displaystyle{ D}\) - przecięcie \(\displaystyle{ CI}\) z okręgiem opisanym, \(\displaystyle{ E}\) - przecięcie \(\displaystyle{ BI}\) z nim. Zatem \(\displaystyle{ AD = BD = DI, AE = EC = EI}\). \(\displaystyle{ ADIE}\) jest deltoidem, więc \(\displaystyle{ DE}\) jest symetralną \(\displaystyle{ AI.}\) Kąty \(\displaystyle{ BAC, BDC, BEC}\) są oparte na \(\displaystyle{ BC}\) i mają po \(\displaystyle{ 60^\circ}\). Skoro jednak \(\displaystyle{ \angle BDC = 60^\circ}\) i \(\displaystyle{ BD = DI}\), to \(\displaystyle{ BDI}\) jest równoboczny. Analogicznie \(\displaystyle{ CEI}\) jest równoboczny. Zatem \(\displaystyle{ DBCE}\) jest trapezem równoramiennym. Na jego osi symetrii leżą: \(\displaystyle{ O}\) - środek okręgu, który przechodzi sam na siebie, \(\displaystyle{ I}\) - przecięcie przekątnych oraz punkt przecięcia \(\displaystyle{ BC}\) i \(\displaystyle{ DE}\) (pokazanie, że one się przecinają jest trywialne).

[TomciO]

Jest, jest.
me123 w żadnym momencie nie chodzi o to, że wszystkie są względnie pierwsze. Jeśli jest jakaś para liczb nie względnie pierwszych, to dzieli przez \(\displaystyle{ NWD}\) i otrzymuje parę liczb względnie pierwszych. Może tak robić, bo przy mnożeniu \(\displaystyle{ m}\) liczb, przynajmniej jedna by brała udział, więc de facto dzielimy przez coś, co by było wtedy fragmentem \(\displaystyle{ NWD}\) i nic nie psuło.

Ok. Teraz rozumiem

[adamm]

Czy za nieuwzględnienie tego, że przecięcie symetralnej \(\displaystyle{ AI}\), prostej \(\displaystyle{ BC}\) i prostej \(\displaystyle{ OI}\) może leżeć po różnych stronach odcinka \(\displaystyle{ BC}\) będzie cięte? Bo rozumowanie wtedy jest zupełnie analogiczne, więc nie wiem.

Podbijam pytanie.

[kaszubki]

Czy za nieuwzględnienie tego, że przecięcie symetralnej \(\displaystyle{ AI}\), prostej \(\displaystyle{ BC}\) i prostej \(\displaystyle{ OI}\) może leżeć po różnych stronach odcinka \(\displaystyle{ BC}\) będzie cięte? Bo rozumowanie wtedy jest zupełnie analogiczne, więc nie wiem.

Podbijam pytanie.

Podejrzewam, że tak.

Wysublimowany_Nick: bardzo ładne rozwiązanie, miałem to samo.

[Prastaruszek]

Zadania były harde. Próg nie przekroczy 18 pktów.

[Msciwoj]

Czy za nieuwzględnienie tego, że przecięcie symetralnej \(\displaystyle{ AI}\), prostej \(\displaystyle{ BC}\) i prostej \(\displaystyle{ OI}\) może leżeć po różnych stronach odcinka \(\displaystyle{ BC}\) będzie cięte? Bo rozumowanie wtedy jest zupełnie analogiczne, więc nie wiem.

Podbijam pytanie.

Ja uważam, że nie będzie, przynajmniej nie powinno. Poza tym, rozumowanie nie jest zupełnie analogiczne, tylko wręcz identyczne. Przynajmniej moje. Punkty \(\displaystyle{ B}\) i \(\displaystyle{ C}\) nie są w żaden sposób rozróżnione w treści zadania. Możemy je ordynarnie zamienić miejscami. I nagle okazuje się, że rzeczony punkt przecięcia leży po drugiej stronie odcinka \(\displaystyle{ BC}\)! To straszne! Innymi słowy, poprawny rysunek zadania będzie dalej poprawny, jeżeli zastosujemy do niego jakąkolwiek izometrię... A w szczególności symetrię względem symetralnej odcinka \(\displaystyle{ BC}\). Przyjmujemy sobie więc któryś z tych punktów jako leżący po prawej stronie (albo na górze, w lewym dolnym rogu itp. - zależnie od orientacji rysunku) "dla ustalenia uwagi". Jak dla mnie to jest oczywiste, ale może jestem młody i głupi.

[Marcinek665]

Punkty \(\displaystyle{ B}\) i \(\displaystyle{ C}\) nie są w żaden sposób rozróżnione w treści zadania. Możemy je ordynarnie zamienić miejscami.

No właśnie o to mi chodzi!

Tak z ciekawości: czy jest ktoś, kto rozwiązywał układ zakładając, ze \(\displaystyle{ a=\max\{a,b,c,d\}}\)? Bo bardzo mało (a może nawet nikt) moich znajomych tak robiło.

[Mruczek]

Ja tak rozwiązywałem, i paru moich kolegów też.

[kammeleon18]

Tak z ciekawości: czy jest ktoś, kto rozwiązywał układ zakładając, ze \(\displaystyle{ a=\max\{a,b,c,d\}}\)? Bo bardzo mało (a może nawet nikt) moich znajomych tak robiło.

jeżeli Cię to ciekawi to ja pokazałem, że \(\displaystyle{ a \le -d\le-b\le c\le a}\) czy coś w tym stylu.