[Rozgrzewka OM][MIX] Łańcuszek olimpijski

[Vax]

Co do zadania Kaszubkiego, jak timon92 zauważył proste AD, BF oraz CH są środkowymi w trójkącie, tak więc przecinają przeciwległy bok na 2 równe połowy, i teraz korzystając z Twierdzenia Cevy otrzymujemy, że przecinają się one w 1 punkcie.

[smigol]

Co do zadania kaszubkiego rozwiązanego przez timona92 z uwagą Vaxa to jak timon zauważył proste AD, BF oraz CH są środkowymi w trójkącie, tak więc przecinają przeciwległy bok na 2 równe połowy i teraz z prostego rachunku na wektorach otrzymujemy, że przecinają się one w jednym punkcie.

[Vax]

@smigol chodziło mi jedynie o to, że oprócz dodania komentarza, że środkowe przecinają się w jednym punkcie, możemy to udowodnić, stosując twierdzenie, które warto znać, bo może się przydać w innych podobnych zadaniach

Pozdrawiam.

[Swistak]

Aktualne zadanie:

W konkursie rzutu oszczepem brało udział 65 zawodników startowali po kolei i oddawali po 1 rzucie, każdy otrzymywał inny wynik, liderem w danym momencie będziemy nazywać tego zawodnika który do tej pory oddał najdłuższy rzut. Niech p oznacza prawdopodobieństwo iż lider zmienił się tylko raz w czasie całego konkursu, wykaż że \(\displaystyle{ p> \frac{1}{16}}\).

Na pewno liderem w pewnym momencie zostanie gość, który oddał najdłuższy rzut i po jego rzucie zamiana lidera nie nastąpi ani razu. Jeżeli będzie on pierwszy w kolejce, to zmiana lidera nie nastąpi ani razu, zatem nie jest on 1-szy w kolejce. Jeżeli będzie n-ty w kolejce, to 1-szy zawodnik musiał oddać rzut dłuższy niż zawodnicy, którzy mieli numer startowy od 2 do n-1, a na to jest szansa \(\displaystyle{ \frac{1}{n-1}}\). Zatem prawdopodobieństwo, że zmiana lidera nastąpi dokładnie raz wynosi \(\displaystyle{ \frac{1}{65} \sum_{64}^{i=1} \frac{1}{i}}\), co na pewno jest większe od \(\displaystyle{ \frac{1}{16}}\). Aby tak było, to musi zachodzić \(\displaystyle{ \sum_{64}^{i=1} \frac{1}{i}>\frac{65}{16}}\), ale można zauważyć, że \(\displaystyle{ 1+\frac{1}{2}+\frac{1}{3}>\frac{33}{16}}\) oraz \(\displaystyle{ (\frac{1}{5}+...+\frac{1}{8} >\frac{1}{2} \ \ \frac{1}{9}+...+\frac{1}{16}>\frac{1}{2} \ \ \frac{1}{17}+...+\frac{1}{32}>\frac{1}{2} \ \ \frac{1}{33}+...+\frac{1}{64}>\frac{1}{2}}\), po zsumowaniu teza.

Dana jest liczba pierwsza p oraz liczby całkowite x, y, z takie, że \(\displaystyle{ 0<x<y<z<p}\). Wykazać, że jeśli \(\displaystyle{ x^{3}\equiv y^{3} \equiv z^{3} mod p}\), to \(\displaystyle{ x+y+z|x^{2}+y^{2}+z^{2}}\)

[ordyh]

Ukryta treść:    

Rozważmy 3 cykliczne kongruencje
\(\displaystyle{ x^3\equiv y^3 \pmod p}\)
\(\displaystyle{ x^3- y^3\equiv 0 \pmod p}\)
\(\displaystyle{ (x-y)(x^2+xy+y^2)\equiv 0 \pmod p}\)
ale \(\displaystyle{ (x-y,p) = 1}\), więc
\(\displaystyle{ x^2+xy+y^2\equiv 0 \pmod p}\)
podobnie:
\(\displaystyle{ y^2+yz+z^2\equiv 0 \pmod p}\)
Odejmując 2 powyższe kongruencje stronami otrzymujemy:
\(\displaystyle{ (x-z)(x+y+z) \equiv 0 \pmod p}\)
czyli
\(\displaystyle{ x+y+z \equiv 0 \pmod p}\)

Teraz dodajmy stronami kongruencje:
\(\displaystyle{ x^2+xy+y^2\equiv 0 \pmod p}\)
\(\displaystyle{ y^2+yz+z^2\equiv 0 \pmod p}\)
\(\displaystyle{ z^2+zx+x^2\equiv 0 \pmod p}\)
otrzymamy:
\(\displaystyle{ 2(x^2+y^2+z^2)+(xy+yz+zx) \equiv 0 \pmod p}\)
\(\displaystyle{ (x+y+z)^2 + (x^2+y^2+z^2)-(xy+yz+zx) \equiv 0 \pmod p}\)
\(\displaystyle{ x^2+y^2+z^2\equiv xy+yz+zx \pmod p}\)
korzystając z tego 3 linijki wyżej otrzymujemy:
\(\displaystyle{ 3(x^2+y^2+z^2)\equiv 0 \pmod p}\)
Ponieważ \(\displaystyle{ p>3}\), więc \(\displaystyle{ x^2+y^2+z^2\equiv 0 \pmod p}\)

Mamy więc:
\(\displaystyle{ a+b+c = kp}\)
\(\displaystyle{ a^2+b^2+c^2 = lp}\)
Zauważmy że \(\displaystyle{ k\in \{1,2\}}\).
Gdy \(\displaystyle{ k=1}\) to podzielność zachodzi w trywialny sposób, a gdy \(\displaystyle{ k=2}\), to zauważamy, że \(\displaystyle{ a\equiv a^2 \pmod 2}\), więc \(\displaystyle{ k=2 \Rightarrow 2|a+b+c \Rightarrow 2|a^2+b^2+c^2 = lp \Rightarrow 2|l}\), więc podzielność również zachodzi.

Ciąg liczb \(\displaystyle{ a_1, a_2, a_3, ...}\) jest określony następująco:
\(\displaystyle{ a_1=a_2=a_3=1}\)
\(\displaystyle{ a_{n+3}=\frac{a_{n+2}a_{n+1}+1}{a_n}}\)
Udowodnij, że wszystkie liczby tego ciągu są liczbami naturalnymi.

[jerzozwierz]

Ukryta treść:    

Rozważmy ciąg \(\displaystyle{ {b_i}}\) zdefiniowany następująco:
\(\displaystyle{ b_1 = 1}\)
\(\displaystyle{ b_2 = 1}\)
\(\displaystyle{ b_{n+2} = \begin{cases} 3b_{n+1} - b_n \ dla \ n \equiv 0 \ (mod \ 2) \\ 2b_{n+1} - b_n \ dla \ n \equiv 1 \ (mod \ 2) \end{cases}}\)
Przez prostą indukcję można pokazać, że dla każdego \(\displaystyle{ i}\) zachodzi \(\displaystyle{ a_i = b_i}\), z czego w oczywisty sposób wynika teza.

Nowe:
Niech \(\displaystyle{ P}\) będzie wielomianem o współczynnikach całkowitych, a \(\displaystyle{ m}\) bezkwadratową liczbą całkowitą.
Udowodnij, że jeśli \(\displaystyle{ P(3+ \sqrt{m})=0}\), to \(\displaystyle{ P(3- \sqrt{m})=0}\).

[KPR]

Ukryta treść:    

Pod argument wielomianu podstawiamy \(\displaystyle{ 3+\sqrt m}\) i potęgi rozwijamy z dwumianu Newtona. Otrzymamy sumę liczb całkowitych i liczb niewymiernych. Żeby \(\displaystyle{ 3+\sqrt m}\) było pierwiastkiem wielomianu, to te niewymierne muszą sumować się do 0 (całkowite zresztą też). Zatem jak weźmiemy wartość wielomianu dla \(\displaystyle{ 3-\sqrt m}\), to znowu otrzymujemy po rozwinięcie liczby całkowite i niewymierne. Nietrudno zauważyć (co wynika z dwumianu Newtona), że te niewymierne będą liczbami przeciwnymi do tych niewymiernych przy rozwinięciu wielomianu dla \(\displaystyle{ 3+\sqrt m}\). Zatem ich suma też będzie równa 0. Poza tym te całkowite, które otrzymamy będą takie same jak dla wartości \(\displaystyle{ 3+\sqrt m}\)(i ich suma też będzie równa 0) . Zatem wartość wielomianu będzie taka sama.

Udowodnić, że dla każdego naturalnego \(\displaystyle{ n \ge 2}\) istnieje \(\displaystyle{ x}\) naturalne takie, że \(\displaystyle{ x^3+17}\) jest podzielne przez \(\displaystyle{ 3^n}\), ale nie przez \(\displaystyle{ 3^{n+1}}\)

[Kimon]

Czy \(\displaystyle{ x}\) jest całkowite?
Jeśli nie to rozwiązanie jest trywialne:

Ukryta treść:    

\(\displaystyle{ n=2 \Rightarrow x= \sqrt[3]{2}, n>2 \Rightarrow x= \sqrt[3]{3^n - 17}}\)

[KPR]

całkowite, całkowite, naturalne nawet!

[darek20]

Ukryta treść:    

Z załozenia istnieje t takie że \(\displaystyle{ 3^{n} | t^{3}+17}\) wiec niech \(\displaystyle{ x=r*3^{n-1}+t , r}\)-liczba naturalna.
Zatem \(\displaystyle{ x^{3}+17\equiv r*3^{n}+t^{3}+17|mod{3^{n+1}}}\). A teraz możemy wybrać r w taki sposób, że \(\displaystyle{ 3^{n+1}| x^{3}+17}\)

[KPR]

Chyba coś jest nie tak. Bo rozumiem, że to miała być indukcja.
po 1. to nie udowodniłeś, że \(\displaystyle{ 3^{n+2}}\) nie dzieli \(\displaystyle{ x^3+17}\). Po 2. czemu \(\displaystyle{ x^3\equiv r \cdot 3^n+t^3(mod 3^{n+1})}\)?

[jerzozwierz]

Ja jeszcze dodam, że moje zadanie się ładnie rozwiązuje rozważając pierścień \(\displaystyle{ J[ \sqrt{m}]}\) liczb postaci \(\displaystyle{ a+b \sqrt{m}}\), gdzie a,b są całkowite. Definiujemy sprzężenie i
\(\displaystyle{ \sum_{i=0}^{n} a_i (3+ \sqrt{m})^i = 0 \Leftrightarrow \overline{ \left( \sum_{i=0}^{n} a_i (3+ \sqrt{m})^i \right) } = 0 \Leftrightarrow \sum_{i=0}^{n} a_i \overline{(3+ \sqrt{m})}^i = 0}\), czyli teza

[cyberciq]

Kimon mógłbyś mi wytłumaczyć dlaczego dla \(\displaystyle{ n=2}\), \(\displaystyle{ x= \sqrt[3]{2}}\) ? Bo 19 nie jest wielokrotnością 3 więc chyba coś nie gra.

[Swistak]

No tak, podyskutujmy nad rozwiązaniem Kimona, wydaje mi się, że mimo tego, że to jeszcze nie jest pełne rozwiązanie, to powinno po tym dość prędko paść.

[jerzozwierz]

Ukryta treść:    

Najpierw udowodnimy indukcyjnie, że dla każdego \(\displaystyle{ n}\) istnieje takie \(\displaystyle{ x}\), że \(\displaystyle{ 3^n | x^3 + 17}\). Dla \(\displaystyle{ n=2}\) bierzemy \(\displaystyle{ x=1}\). Teraz krok:
mamy takie \(\displaystyle{ m}\), że \(\displaystyle{ m^3 + 17 \equiv 0 \ (mod \ 3^n)}\). Jak \(\displaystyle{ m^3 + 17 \equiv 0 \ (mod \ 3^{n+1})}\) to jesteśmy w domu, a jak nie, to \(\displaystyle{ m^3 + 17 \equiv \epsilon 3^n \ (mod \ 3^{n+1})}\), gdzie \(\displaystyle{ \epsilon \in \left\{ -1,1 \right\}}\). Wtedy rozważamy liczbę \(\displaystyle{ m - \epsilon 3^{n-1}}\), skąd
\(\displaystyle{ \left( m - \epsilon 3^{n-1} \right) ^3 + 17 = m^3 - \epsilon 3^n m^2 + 3^{2n-1}m - \epsilon 3^{3n-3} + 17 \equiv \epsilon 3^n \left( m^2 - 1 \right) + 3^{2n-1}m - \epsilon 3^{3n-3} \equiv 0 \ (mod \ 3^{n+1})}\)
ponieważ dla każdego m niepodzielnego przez 3 mamy \(\displaystyle{ 3 | m^2 - 1}\).
Teraz właściwa część: (ale już odechciało mi się pisać) bierzemy nasze wygenerowane m, jak nie jest podzielne przez \(\displaystyle{ 3^{n+1}}\) to fajnie, a jak nie, to rozważamy liczbę \(\displaystyle{ m + 3^{n-1}}\). Okazuje się, że podzielność przez \(\displaystyle{ 3^n}\) się zachowuje, a te dwie liczby \(\displaystyle{ m^3 + 17}\) i \(\displaystyle{ \left( m + 3^{n-1} \right)^3 + 17}\) nie mogą być jednocześnie podzielne przez \(\displaystyle{ 3^{n+1}}\) (dowód podobny do tego powyżej).

Nowe zadanie: (jak swistak wrzuci rozwiązanie to się nie liczy)
Wyznacz wszystkie pary liczb pierwszych \(\displaystyle{ p,q}\) takich, że
\(\displaystyle{ pq | (5^p - 2^p)(5^q - 2^q)}\).