LXIII Olimpiada Matematyczna II etap.

[kammeleon18]

Swistak, a nie przypadkiem? \(\displaystyle{ c \ge a,b,d}\), także \(\displaystyle{ 0 \ge b^3+c^3 = a-c \leq 0}\)

A w ogóle skąd my mamy jakiekolwiek informacje o znaku wyrażenia \(\displaystyle{ b^3+c^3}\) ? Bo ja czegoś nie qmam.

[timon92]

mniej więcej chodzi o to, że jeśli (a,b,c,d) jest rozwiązaniem, to (-a, -b, -c, -d) też jest

więc możemy sobie przyjąć że c jest największe co do modułu i jednocześnie dodatnie

wówczas nierówności napisane przez Swistaka faktycznie są prawdziwe

[michal_z]

Próg 21. Dużo osób ma 3 zadania.

Moim zdaniem próg <= 18. Może jakiś mały zakładzik?

[andriej]

Próg moim zdaniem 17, może 18. Dużo osób ma 3 zadania, raczej mało kto >=4, jest też dużo blefów.

[Myrthan]

No zaskakująca olimpiada, zadania stosunkowo proste ale jak widać nie dla mnie bo mam dwa i na dwa punkty może jeszcze ugrałem jedno zadanie (pierwszy dzień "przespałem", szczególnie trzecie szkoda...). Myślę że próg będzie oscylował przy 18, ale chcąc być ścisły stawiam na 19 pkt. w krakowskim dużo osób miało pełne 3 zadania. Ogólnie to dwie osoby wyszły z mojej sali 1h<czas do konca. Czyli dużo osób walczyło i najlepszym nie "pykło" w 2h. To tak abstrahując mówię, bo każdy post tutaj to kopia poprzedniego łącznie z moim .

Powodzenia wszystkim w dostaniu się.

[Leszczu21]

Zadania nie były proste. Pierwsze nie było takie znowu łatwe. Drugie - może nie hard, ale stereo i samo to odstraszało ludzi. Trzecie faktycznie banalne. Czwarte wymagało nieco sprytu i jeśli ktoś podchodził do tego jak do innych równań funkcyjnych, to mógł mieć problem. Piąte było moim zdaniem trudniejsze niż rok temu. Szóste zadanie... no dobra, ono było frajerskie, ale i tak niedużo osób je ma, no i pewnie będą blefy ;P Obstawiam próg 17.

[Swistak]

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+n)=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+n)=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 .

[adamm]

Dowodziłeś LTE?

[kaszubki]

Nie udowodnił ani nie podał źródła dowodu :p

[Swistak]

Nie, całe rozwiązanie zajęło mi 4 strony i nie zdążyłem, bo się ledwo wyrobiłem xD. Lematu 3 też nie zdążyłem napisać, ale napisałem, że dowód można znaleźć w mojej pracy z finału LXI OM zad. 6 xD.

[Panda]

Czwarte wymagało nieco sprytu i jeśli ktoś podchodził do tego jak do innych równań funkcyjnych, to mógł mieć problem

Mnie się zdaje, że to typowa pała, nawet we wzorcówce. Inaczej niż "jak do innych równań funkcyjnych", czyli jak?

[Msciwoj]

Tak, Swistak robił 6. przez bite 20 minut, po czym przyszedł pewien człowiek i zauważył, że to rozwiązanie można skrócić. To było... niezwykle odkrywcze.

Ja sobie liczę 21, 2 za 1., 6 za 3., 2 za 4. (wyszło mi, że\(\displaystyle{ f(x) = -x + f(0)}\) oraz \(\displaystyle{ g(x) = -x + g(0)}\) i wziąłem się na ambicję, żeby dowieść, że koniecznie \(\displaystyle{ g(0) = f(0) = 0}\). W połowie przekształceń rąbnąłem się w znakach i mi to wyszło. Więcej jak 2 nie dostanę ), 6 za 5., 5 za 6. Skoro nawet w najbardziej "optymistycznych" scenariuszach próg większy niż 21 punktów nie będzie, to chyba mogę spać spokojnie.

[adamm]

wyszło mi, że\(\displaystyle{ f(x) = -x + f(0)}\) oraz \(\displaystyle{ g(x) = -x + g(0)}\) i wziąłem się na ambicję, żeby dowieść, że koniecznie \(\displaystyle{ g(0) = f(0) = 0}\). W połowie przekształceń rąbnąłem się w znakach i mi to wyszło. Więcej jak 2 nie dostanę

nie znam szczegółów, ale jak dla mnie to 5

[Marcinek665]

Czwarte wymagało nieco sprytu i jeśli ktoś podchodził do tego jak do innych równań funkcyjnych, to mógł mieć problem

Mnie się zdaje, że to typowa pała, nawet we wzorcówce. Inaczej niż "jak do innych równań funkcyjnych", czyli jak?

Ukryta treść:    

Niech \(\displaystyle{ f(0)=a}\), \(\displaystyle{ g(0)=b}\). Wtedy:

\(\displaystyle{ x=y=0 \Rightarrow g(a)=f(b)}\)

\(\displaystyle{ x=0 \Rightarrow g(a-y)=f(g(y))}\)

\(\displaystyle{ y=0 \Rightarrow g(f(x))=f(b)+x=g(a)+x}\) czyli \(\displaystyle{ g(f(x))=g(a)+x}\)

\(\displaystyle{ y=f(x) \Rightarrow b=f(g(f(x)))+x=f(g(a)+x)+x}\) czyli \(\displaystyle{ f(g(a)+x)=b-x}\)

Przedefiniujmy zmienną \(\displaystyle{ x}\) na \(\displaystyle{ x-g(a)}\) dostajemy \(\displaystyle{ f(x)=-x+g(a)+b = -x + \alpha}\)

Czyli \(\displaystyle{ f}\) jest liniowa.

No to wstawiamy do wyjściowego i wychodzi:

\(\displaystyle{ g(-x+\alpha - y) = -g(y) + \alpha + x}\)

Niech \(\displaystyle{ y=\alpha - x}\) wtedy:

\(\displaystyle{ b=-g(\alpha - x) + \alpha + x}\)

Zamieńmy zmienną \(\displaystyle{ x}\) na \(\displaystyle{ -x + \alpha}\)

Mamy:

\(\displaystyle{ g(x)=-x+2\alpha-b = -x + \beta}\)

Czyli \(\displaystyle{ f(x)=-x+\alpha}\) oraz \(\displaystyle{ g(x)=-x+\beta}\)

Znowu wracając do wyjściowego równania dostaniemy \(\displaystyle{ \beta = \alpha}\), więc funkcje to \(\displaystyle{ f(x)=g(x)=-x+\alpha}\), gdzie \(\displaystyle{ \alpha}\) jest dowolne rzczywiste

Takie niby fajne, ale łatwo było gdzieś przyblefić.

[Leszczu21]

Czwarte wymagało nieco sprytu i jeśli ktoś podchodził do tego jak do innych równań funkcyjnych, to mógł mieć problem

Mnie się zdaje, że to typowa pała, nawet we wzorcówce. Inaczej niż "jak do innych równań funkcyjnych", czyli jak?

Nie wiem, nie czytałem wzorcówki, ale jak je rozwiązywałem, to myślałem "o, jeszcze nigdy tak nie rozwiązywałem równania funkcyjnego" Trzeba było się skapnąć, że funkcja, która jest włożona w funkcję, jest liniowa i że to złożenie funkcji jest liniowe... i w ogóle Samo pałkarskie podstawianie nie wystarczy...