LXIV (64) OM - II etap

[kicferk]

Swoją drogą - parę ludzi twierdziło u nas, że w zad 5 nie istnieje wielomian i mają na to dowód,

U nas też, chyba wszyscy(albo prawie) co myśleli, że to zrobili, nie wyłączając mnie, twierdzili że taki wielomian nie istnieje, aż do samego omówienia... A progu nie będę obstawiać coby nie zapeszyć.

[kaszubki]

Jeśli chodzi o typ zadań, w sumie dobrze, że tylko jedno kombi i właściwie brak jako takiej teorii liczb, można liczyć, że będzie tego więcej na finale.

Miałeś 2 teorie liczb, więc raczej finał nie będzie bogaty w zadania tego typu.

[lamapl123]

pomyłka

[SingleVariable]

Moje rozwiązanie zadania 1, może ktoś skontrolować i powiedzieć czy jest ok? Bo mi nie da jeśli się nie dowiem...

Ukryta treść:    

Otrzymujemy \(\displaystyle{ n|f( k_{1} )-f( k_{2} ) \Leftrightarrow n|(k_{1}-k_{2})(k_{1}+k_{2}+b)}\) analogicznie \(\displaystyle{ n|(k_{2}-k_{3})(k_{2}+k_{3}+b)}\) i \(\displaystyle{ n|(k_{3}-k_{1})(k_{1}+k_{3}+b)}\)
Kładąc \(\displaystyle{ (k_{1}+k_{2}+b)= a_{1}}\) , \(\displaystyle{ (k_{2}+k_{3}+b)=a _{2}}\) oraz \(\displaystyle{ (k_{1}+k_{3}+b)=a_{3}}\) Korzystam z własności \(\displaystyle{ NWD(a,b)=NWD(a-b,b)}\) \(\displaystyle{ NWD(a_{1} ,a _{2}) = NWD( k_{3}-k_{1},a _{2}) = t_{1}}\), z tąd wynika że \(\displaystyle{ t_{1}| k_{3}-k_{1}}\), analogicznie postępuje z każdą parą \(\displaystyle{ a_{i}}\) i=1,2,3 otrzymując że \(\displaystyle{ a_{i}=t_{i} \cdot w_{i}}\) gdzie \(\displaystyle{ w_{i}}\) są parami względnie pierwsze. Biorąc\(\displaystyle{ NWD(n,w_{i})= p_{i}}\) dostajemy że \(\displaystyle{ n=p_{1}p_{2}p_{3}\cdot u}\) (jakieś tam u) i teraz mamy że \(\displaystyle{ p_{2}p_{3}\cdot u|(k_{2}-k_{3})(t_{1})}\) i dostajemy analogicznie \(\displaystyle{ p_{1}p_{3}\cdot u|(k_{1}-k_{3})(t_{2})}\) i \(\displaystyle{ p_{1}p_{2}\cdot u|(k_{1}-k_{2})(t_{3})}\) mnożąc je stronami otrzymujemy że \(\displaystyle{ n^2 \cdot u|((k_{1}-k_{2}(k_{3}-k_{1})(k_{2}-k_{3}))^2}\) gdyż \(\displaystyle{ (t_{1})(t_{2})(t_{3})|(k_{1}-k_{2}(k_{3}-k_{1})(k_{2}-k_{3})}\)czyli teza

Jeśli tu jest blef, to czy mam jakiekolwiek szanse z tym rozwiązaniem na jakiekolwiek punkty?

[urojony]

Miałeś 2 teorie liczb, więc raczej finał nie będzie bogaty w zadania tego typu.

Ale te teorie liczb jakieś takie algebraiczne były.

BTW: właśnie się skapnąłem, że do zadania 6 nie zrobiłem żadnego rysunku. Nie wiem, dlaczego, ale po prostu nie przyszło mi to do głowy. Mam nadzieję, że nie zetną mi za to za bardzo.

[Elvis]

Nikt tu chyba jeszcze nie zamieścił mojego "rozwiązania" zadania 1, więc się podzielę. Ma ono tę zaletę, że uogólnia problem na przypadek wielomianu unormowanego \(\displaystyle{ k}\)-tego stopnia zerującego się w \(\displaystyle{ k+1}\) punktach; wówczas analogiczny iloczyn jest zerowy (w dowolnym pierścieniu przemiennym z jedynką, w szczególności pierścieniu reszt modulo \(\displaystyle{ n}\)).

Ukryta treść:    

Rachunki będziemy prowadzić modulo \(\displaystyle{ n}\). Weźmy macierz \(\displaystyle{ A = \begin{bmatrix}1 & k_1 & k_1^2 \\ 1 & k_2 & k_2^2 \\ 1 & k_3 & k_3^2 \end{bmatrix}}\) oraz wektor \(\displaystyle{ v = \begin{bmatrix} c \\ b \\ 1 \end{bmatrix}}\). Wówczas założenie możemy sformułować jako równość \(\displaystyle{ Av=0}\), a tezę jako \(\displaystyle{ \det A = 0}\) (jest to tzw. wyznacznik Vandermonde'a). Rozwiązanie sprowadza się wówczas do wzięcia macierzy dołączonej \(\displaystyle{ B}\) (to jest macierzy spełniającej \(\displaystyle{ BA=AB=\det A \cdot I}\)) i przeprowadzenia następującego rachunku:
\(\displaystyle{ 0 = B \cdot 0 = BAv = \det A \cdot v}\).
Przez porównanie trzeciej współrzędnej otrzymujemy \(\displaystyle{ \det A = 0}\).

[nobuddy]

Moje rozwiązanie zadania 1, może ktoś skontrolować i powiedzieć czy jest ok?

Nie wiem skąd bierzesz że \(\displaystyle{ w_i}\) są względnie pierwsze, ale dla

Ukryta treść:    

\(\displaystyle{ f(x)=x^2+3x+2}\)
\(\displaystyle{ k_1=1}\),
\(\displaystyle{ k_2=2}\)
\(\displaystyle{ k_3=5}\)
\(\displaystyle{ n=6}\)

teza zadania mi śmiga a wyszło \(\displaystyle{ w_1=w_3=3}\). Przelicz czy sie nie walnąłem gdzieś Chyba że zapisałeś coś źle, no bo z tego co piszesz \(\displaystyle{ w_1= \frac{a_1}{NWD(a_1, a_2)}}\) a \(\displaystyle{ w_2= \frac{a_2}{NWD(a_2, a_3)}}\), i gdyby w drugim zmienić indeks 3 na 1 to by rzeczywiście względnie pierwsze były, nie wiem jak ty robiłeś.

[SingleVariable]

chyba źle policzyles \(\displaystyle{ a_{1}}\) bo \(\displaystyle{ k_{1}+ k_{2}+b=1+2+2=5,}\) nie 3 ;D, a to że są względnie pierwsze biorę z tąd że \(\displaystyle{ w_{1}}\) nie dzieli a_{2} bo to wynika z \(\displaystyle{ w_1= \frac{a_1}{NWD(a_1, a_2)}}\) a więc w1 i a2 są względnie pierwsze a tym bardziej w1 będzie z w2 względnie pierwsze a fakt że w1 z w3 jest względnie pierwsze wziąłem z tąd że \(\displaystyle{ w_{3}= \frac{a_3}{NWD(a_1, a_3)}}\) a więc w3 jest względnie pierwsza z a1 a tym bardziej z w1, czyli w1 i w2 oraz w1 i w3 są względnie pierwsze, analogicznie pozostałe pary.

Mało zawału nie dostałem jak pomyślałem o tym że one niekoniecznie są względnie pierwsze wczesniej ale później wpadłem na to co powyżej, na omie niestety nie opisałem tego tak dokładnie :/ stwierdzając że to jest oczywiste, obetną dużo?

[nobuddy]

ale \(\displaystyle{ b=3 \Rightarrow a_1=6}\), nie?

ty ogólnie mówisz że jesli \(\displaystyle{ x= \frac{a}{NWD(a, b)}}\) to x jest wzglednie pierwsze z b, ale to nie prawda chociażby dla \(\displaystyle{ a=9}\), \(\displaystyle{ b=3}\).

edit: w ogóle mówisz nie dzieli czegośtam więc jest względnie pierwsze, co tez nie jest prawdą

[SingleVariable]

Racja , sam siebie wkręciłem:(

[Utumno]

Fajne zadanka, chociaz wg mnie troche za duzy dystans miedzy 1,2 i 4 (latwe i bardzo latwe) a reszta (wszystkie trudne i bardzo trudne).

Przyszlo mi do glowy pewne uogolnienie zad. 3. Otoz wbrew temu co twierdza niektorzy, mozliwe jest wypelnienie kwadratu 5x5 figurami jak z zadania. Trzeba tylko uzyc 11 'trojek' i... -2 'czworek' (co tez wynika ze wzoru na liczbe 'czworek' w kwadracie nxn). Cwiczenie dla czytelnika : uloz kwadrat 5x5 w ten sposob!

Pojdzmy dalej: ulozmy kwadrat 3x3. Oczywiscie zgodnie ze wzorami potrzebujemy teraz -3 czworek i 7 trojek, czyli w sumie 4. Ale latwo zauwazyc, ze mozna rowniez wziasc 4 'dodatnie' trojki i jedna 'ujemna' , (jak?) czyli w sumie 4-1=3 < 4. Wniosek jest taki, ze jesli dopuscimy 'ujemne' figury, to wynik zadania nie jest juz optymalny!

Nastepne wiec cwiczenie dla czytelnika: rozwiaz analogiczne zadanie z dodatkowym zalozeniem ze dopuszczamy 'ujemne' figury.

[Swistak]

Hm, moim zdaniem 3 było stosunkowo proste, istotnie nie zgadzam się z powszechnie panującym poglądem, że było bardzo trudne. Moim zdaniem prostsze od 1 i 4. Niektórzy pewnie z aż tak drastycznym stwierdzeniem się nie zgodzą, ale za to ja się wybitnie nie zgadzam, jakoby ono miało być wybitnie trudne. I liczby też tak mówią . Naprawdę ciężko wymyślić bardziej standardową kolorowankę ...

[jakub_jabulko]

Naprawdę ciężko wymyślić bardziej standardową kolorowankę ...

No właśnie, tu nie chodzi o trudność zadania, ale o typ. Wydaje mi się, że kolorowanki (jakiekolwiek by nie byłe łatwe) są nielubiane przez wielu ludzi. A przynajmniej przeze mnie. Sytuacja analogiczna do stereometrii sprzed 2-3 lat. Była mega banalna, ale dużo osób nie zrobiło jej właśnie dlatego, że była stereometrią.

[dwumian]

Hm, moim zdaniem 3 było stosunkowo proste, istotnie nie zgadzam się z powszechnie panującym poglądem, że było bardzo trudne. Moim zdaniem prostsze od 1...

Zgadzam się

[Errichto]

Też się zgadzam. Dla ludzi wiedzących cokolwiek o kolorowaniu było to zadanie na kilka minut rozkminy, góra kilkanaście.