LXII Olimpiada Matematyczna II etap.

[wally]

Ogólnie realnym progiem jest 24, parę lat temu (59. OM) chyba był 25 (niech ktoś mnie poprawi jak się mylę), poziom zadań podobny (może nawet prostsze teraz?), więc jest to naprawdę realny próg.

[Panda]

Czyli w gruncie rzeczy błąd opisu - pewnie kwestia tego, czy sprawdzający się zagłębi.

KASZUBKA, nie kaszubskiego!!!!111oneoneeleven

Hah:D Tam serio nie ma "s"! Tyle razy widziałem twój nick i się nie zorientowałem :p

[tkrass]

Ogólnie realnym progiem jest 24, parę lat temu (59. OM) chyba był 25 (niech ktoś mnie poprawi jak się mylę), poziom zadań podobny (może nawet prostsze teraz?), więc jest to naprawdę realny próg.

Mylisz się, poprawiam cię.

[wally]

A jaka była minimalna liczba punktów z zawodów II stopnia potrzebna do uzyskania zakwalifikowania do finału 59.OM?

[kaszubki]

19

[Swistak]

Btw sprawdzi mi ktoś mój wielomian, abym już był pewien, że mam go dobrze ;p?

zad. 6:    

Oznaczmy \(\displaystyle{ R(x)=P(x)-Q(x)}\).
Lemat 1: Dla jakichś wielomianów A, B, C wielomian\(\displaystyle{ A(B(x)R(x)+C(x))}\) daję tę samą resztę z dzielenia przez R(x) co \(\displaystyle{ A(C(x))}\).
Dowód: \(\displaystyle{ A(B(x)R(x)+C(x))=a_{k}(B(x)R(x)+C(x))^{k}+...+a_{1}(B(x)R(x)+C(x))+a_0}\), ale \(\displaystyle{ (B(x)R(x)+C(x))^{j}}\) daję z dzielenia przez \(\displaystyle{ R(x)}\) tę samą resztę, co \(\displaystyle{ (C(x))^{j}}\), zatem \(\displaystyle{ a_{k}(B(x)R(x)+C(x))^{k}+...+a_{1}(B(x)R(x)+C(x))+a_0}\) daje z dzielenia przez \(\displaystyle{ R(x)}\) tę samą resztę, co \(\displaystyle{ a_{k}C(x)^{k}+...+a_{1}C(x)+a_0=A(C(x))}\), co dowodzi tezy lematu.

Z definicji \(\displaystyle{ R(x)}\) mamy, że \(\displaystyle{ P(x)}\) i \(\displaystyle{ Q(x)}\) dają z dzielenia przez \(\displaystyle{ R(x)}\) tę samą resztę zatem na mocy lematu 1 otrzymujemy, że \(\displaystyle{ P(P(x))}\) daję z dzielenia przez \(\displaystyle{ R(x)}\) tę samą resztę co \(\displaystyle{ P(Q(x))}\), a \(\displaystyle{ Q(Q(x))}\) tę samą resztę co \(\displaystyle{ Q(P(x))}\), a skoro \(\displaystyle{ P(Q(x))=Q(P(x))}\), to udowodniliśmy tezę dla n=2.
Teraz będziemy dowodzić indukcyjnie. Jeżeli mamy tezę udowodnioną dla jakiegoś n-1 i chcemy udowodnić dla jakiegoś n, to \(\displaystyle{ R(x)|P_{n-1}(x)-Q_{n-1}(x)}\), a mamy dowieść, że \(\displaystyle{ R(x)|P_{n}(x)-Q_{n}(x)}\), ale \(\displaystyle{ Q_{n}(x)=Q(Q_{n-1}(x))}\) co na mocy lematu 1 i założenia indukcyjnego daje taką samą resztę z dzielenia przez \(\displaystyle{ R(x)}\), co \(\displaystyle{ Q(P_{n-1}(x))}\), zatem naszym celem jest dowieść, że \(\displaystyle{ R(x)|P(P_{n-1}(x))-Q(P_{n-1}(x))=R(P_{n-1}(x))}\). Udowodniliśmy to wyżej dla \(\displaystyle{ n=2}\), zatem możemy napisać \(\displaystyle{ R(x)H(x)=R(P(x))}\) dla jakiegoś \(\displaystyle{ H(x)}\). Z tego wynika nam, że \(\displaystyle{ R(P_{n-1}(x))H(P_{n-1}(x))=R(P_{n}(x))}\), zatem \(\displaystyle{ R(P_{n-1}(x))|R(P_{n}(x))}\), co w oczywisty sposób implikuje nam to, co chcieliśmy dowieść.
c.b.d.u.

[XMaS11]

dobrze

[JaQb]

Heh, OM jest chyba po to, żeby trenowac ludzi w zakresie kręcenia długopisami, bo ja też przez te 2 dni się poprawiłem w tejże umiejętności;p.
Okazuje się, że zrobiłem wielomiany 3-4 razy szybciej niż Swistak:D dziwne;p.

[ElusiveN]

To może ja też dam mój wielomian. Cisnąłem indukcją, w której do końca brakło mi jednego przejścia, więc pewnie będzie 2 lub 5. Finału i tak nie będę miał, ale chcę wiedzieć, czy dobrze jedną rzecz wykminiłem:

Ukryta treść:    

Lemma1:

jeśli \(\displaystyle{ x \neq y}\), to \(\displaystyle{ x-y|W(x) - W(y)}\). Dowód: Niech \(\displaystyle{ W}\) będzie postaci \(\displaystyle{ W(x) = \sum_{i=0}^{n}a_{i}x^{i}}\). Wielomian \(\displaystyle{ W(x) - W(y)}\) dzieli się przez \(\displaystyle{ x-y}\), bo \(\displaystyle{ x-y}\) dzieli \(\displaystyle{ x^{n} - y^{n}}\) dla każdego naturalnego \(\displaystyle{ n}\), więc \(\displaystyle{ x-y}\) dzieli każdy nawias \(\displaystyle{ W(x) - W(y)}\), co dowodzi słuszności lematu.

Teraz wątpliwości:

Lemma2:
\(\displaystyle{ P(x) - Q(x)| W(P(x)) - W(P(y))}\)

Połóżmy w lemacie1 \(\displaystyle{ x:=P(x), y:=Q(x)}\), stąd wynika, że:
\(\displaystyle{ P(x) - Q(x)| W(P(x)) - W(P(y))}\)
stąd łatwo było dojść do tezy zadania dla \(\displaystyle{ n=2}\) (dodać odpowiednie podzielności).

A wziąłem to stąd, że skoro lemat działa dla każdych różnych \(\displaystyle{ x,y}\), to działa w szczególności liczb \(\displaystyle{ x=P(x)}\) i \(\displaystyle{ y=Q(x)}\)

Czy mój lemat2 jest dobry? Chodzi o podstawienie, bo ktoś mi mówił, że dla wielomianów to się rozkracza. Jeśli jest źle, to prosiłbym o naprawienie tego, w miarę możliwości

[gulix]

optymistyczna wersja zakłada: 620662 = 20
pesymistyczna wersja: 600220 = 10
zależy jak będą się czepiać niedomówień itp. bzdetów
ale pewnie tak z 16-18 będę miał, oby starczyło

[Leszczu21]

ElusiveN, ja dowodziłem tylko lematu 1, lemat 2 wydał mi się być oczywistym. Zawsze można wtedy wyłączyć P(x)-Q(x) przed nawias. W mojej indukcji popełniłem taki błąd, że w pierwszym kroku pokazałem, że P(x)-Q(x)|P(P(x))-Q(Q(x)), nie wspominając nic o oczywistym co prawda fakcie, że P(x)-Q(x)|P(x)-Q(x), a w kroku indukcyjnym dla różnicy n-krotnych złożeń wielomianu korzystałem z tego, że P(x)-Q(x) dzieli (n-2)-krotne złożenie wielomianu. Czyli jedna linijka. Mam nadzieję, że 5 mi się dalej należy, bo to są tylko drobne usterki, a trzon zadania jest.

[Swistak]

Elusiven: Identyczny lemat masz we wzorcówce, więc nie rozumiem wątpliwości .

[Prastaruszek]

Uważam, że bardzo dobrze że drugi etap nie był nie-wiadomo-jak trudny. Oprócz tych najwybitniejszych w Olimpiadzie startują jeszcze osoby które nie mają doświadczenia/takich zdolności, więc oni mogli się zmierzyć z czymś w czym mieli szanse coś zdziałać.
A co by nie było nudno, może wrzucę moje rozwiązanie trzeciego, bo do firmówki jest niepodobne (albo przynajmniej mniej podobne niż firmówka):

Ukryta treść:    

Zauważmy, że
\(\displaystyle{ 2(2a ^{2}+3 b^{2})(2c ^{2}+3d ^{2})=2(2ac+3bd) ^{2}+3(2ad-2bc) ^{2}=2k ^{2}+3l ^{2}}\) Dla pewnych k i l nieujemnych. Wynika z tego przez prostą indukcję, że nasz iloczyn da się zwinąć do postaci \(\displaystyle{ \frac{2x ^{2}+3y ^{2} }{2 ^{2010} }}\), dla pewnych całkowitych nieujemnych x,y. Załóżmy, że nasz iloczyn jest kwadratem. Wówczas mamy równanie w liczbach całkowitych niujemnych: \(\displaystyle{ 2x ^{2}+3y ^{2}=2 ^{2010} z ^{2}}\). Jako, że
\(\displaystyle{ 2 ^{2010}=1}\) (mod 3), więc mamy równanie \(\displaystyle{ 2x ^{2}=z ^{2}}\)(mod 3). Jako, że jedynymi resztami kwadratów z dzielenia przez trzy sa 1 i 0, więc x=0, z=0(mod 3).Czyli x=3t, z=3e, jak wstawimy w równanie otrzymamy, że także y=3v. Otrzymamy wtedy, że
\(\displaystyle{ 2t ^{2}+3v ^{2}=2 ^{2010} e ^{2}}\) Czyli to samo równanie co na początku tylko z mniejszymi zmiennymi t,v,e. Nie możemy tego rozumowania powtarzać w nieskończoność, więc x,y,z=0. Ale z>0, bo kwadrat liczby z to iloczyn liczb dodatnich. Śprzeczność.

[ElusiveN]

To jest [ocenzurowano].

[Menda]

Osobiście uważam iż najłatwiejsze było zadanie 6, które nie wymagało niczego poza zastosowaniem indukcji zupełnej i skorzystaniem z założeń zadania, w przeciwieństwie do innych zadań które były albo lekko podchwytliwe albo wymagały np. znajomości wzoru na deltę. W każdym bądź razie życzę cierpliwości w oczekiwaniu na wyniki.
Chciałbym z tego miejsca serdecznie pozdrowić również krakowski komitet okręgowy, a w szczególności jego przewodniczącego który nie po raz pierwszy na otwarciu II etapu cytował moje posty z tegoż forum.

Pozdro