Matematyka.pl

jgarnek pisze:Konkurs

Zadanie 1:    

W dowodzie skorzystamy z (dość znanego) twierdzenia Liouville'a o aproksymacji diofantycznej:

Jeśli \(\displaystyle{ \alpha}\) jest liczbą niewymierną, która jest pierwiastkiem wielomianu f stopnia n > 0 o współczynnikach całkowitych, to istnieje liczba rzeczywista A > 0 taka, że dla dowolnych liczb całkowitych p oraz q > 0 zachodzi \(\displaystyle{ |\alpha - \frac{p}{q}| > \frac{A}{q^n}}\).

Ukryta treść:    

Dowód (za wikipedią): Niech M oznacza największą wartość modułu pochodnej |f '(x)| wielomianu f w przedziale \(\displaystyle{ [\alpha - 1, \alpha + 1]}\). Niech \(\displaystyle{ \alpha_1, \alpha_2,\ldots ,\alpha_m}\) będą różnymi pierwiastkami wielomianu f, które są różne od \(\displaystyle{ \alpha}\). Wybierzmy taką liczbę A > 0, która spełnia warunek:

\(\displaystyle{ A < \min(1, \frac{1}{M}, |\alpha - \alpha_1|, |\alpha - \alpha_2|,\dots, |\alpha - \alpha_m|)}\)

Przypuśćmy, że istnieją takie liczby całkowite p, q, dla których nierówność podana w tezie lematu nie zachodzi. Oznacza to, że

\(\displaystyle{ \left|\alpha-\frac{p}{q}\right| \leqslant \frac{A}{q^n}\leqslant A < \min(1, |\alpha-\alpha_1|, |\alpha-\alpha_2|,\ldots , |\alpha-\alpha_m|)}\)

Wówczas p/q leży w przedziale \(\displaystyle{ [\alpha - 1, \alpha + 1]}\) oraz p/q nie jest żadną z liczb \(\displaystyle{ \alpha_1, \alpha_2,\ldots , \alpha_m}\). Zatem p/q nie jest też pierwiastkiem f, a ponadto żaden pierwiastek f nie leży pomiędzy \(\displaystyle{ \alpha}\) i p/q.

Na mocy twierdzenia o wartości średniej pomiędzy p/q i \(\displaystyle{ \alpha}\) istnieje taka liczba \(\displaystyle{ x_0}\), że

\(\displaystyle{ f(\alpha)-f\left(\frac{p}{q}\right) = \left(\alpha-\frac{p}{q}\right)\cdot f^{\prime}(x_0)}\)

Ponieważ \(\displaystyle{ \alpha}\) jest pierwiastkiem f, a p/q nie, zatem \(\displaystyle{ |f '(x_0)| > 0}\) i:

\(\displaystyle{ \left|\alpha-\frac{p}{q}\right| = \frac{|f(\alpha)-f\left(\frac{p}{q}\right)|}{|f^{\prime}(x_0)|}= \frac{|f\left(\frac{p}{q}\right)|}{|f^{\prime}(x_0)|}}\)

Ponieważ f jest postaci \(\displaystyle{ \sum_{i=0}^{n}c_i\cdot x^i}\), gdzie każde \(\displaystyle{ c_i}\) jest całkowite, |f(p/q)| można zapisać jako

\(\displaystyle{ |f\left(\frac{p}{q}\right)| = |\sum_{i=0}^{n}c_i\left(\frac{p}{q}\right)^i| = \frac{|\sum_{i=0}^{n}c_ip^iq^{n-i}|}{q^n} \geqslant \frac{1}{q^n}.}\)

Ostatnia nierówność zachodzi, gdyż p/q nie jest pierwiastkiem wielomianu f, a \(\displaystyle{ c_i}\) są liczbami całkowitymi.

Zatem, \(\displaystyle{ |f(p/q)| \ge \frac{1}{qn}}\), a skoro \(\displaystyle{ |f '(x_0)| \le M}\) na mocy określenia liczby M i 1/M > A z definicji A, otrzymujemy stąd sprzeczność:

\(\displaystyle{ \left|\alpha-\frac{p}{q}\right| = \frac{\left|f\left(\frac{p}{q}\right)\right|}{|f^{\prime}(x_0)|} \geqslant \frac{1}{Mq^n} > \frac{A}{q^n}\geqslant \left|\alpha-\frac{p}{q}\right|.}\)

Wynika stąd, że nie istnieją liczby p i q o takich własnościach, co dowodzi lematu.

Dowód ten znajdziemy również np. w książce Jarosława Górnickiego "Okruchy Matematyki" w rozdziale "Liczby przestępne i liczby Liouville'a".

Liczba \(\displaystyle{ \sqrt[3]{2}}\) jest pierwiastkiem wielomianu \(\displaystyle{ f(x)=x^3-2}\). Wielomian ten nie ma pierwiastków
wymiernych (można to sprawdzić, korzystając z twierdzenia o pierwiastkach wymiernych), więc \(\displaystyle{ \sqrt[3]{2}}\) jest liczbą niewymierną i algebraiczną stopnia 3. Korzystając z twierdzenia Liouville'a o aproksymacji diofantycznej uzyskujemy więc tezę zadania.

Zadanie 2:    

Zauważmy, że dla każdego \(\displaystyle{ m \in \mathbb{N}}\) funkcja \(\displaystyle{ f^{(m)}}\) jest funkcją wymierną. Istotnie, dla \(\displaystyle{ m=1}\)
teza jest prawdziwa, zaś jeżeli \(\displaystyle{ f^{(m-1)}(x)=\frac{a_{m-1}x+b_{m-1}}{c_{m-1}x+d_{m-1}}}\), to
\(\displaystyle{ f^{m}(x)=f^{(m-1)}(f(x)) = \frac{a_{m-1}\frac{ax+b}{cx+d}+b_{m-1}}{c_{m-1}\frac{ax+b}{cx+d}x+d_{m-1}}=
\frac{(a_{m-1} a+b_{m-1} c)x+(ba_{m-1}+db_{m-1})}{(ac_{m-1}+cd_{m-1})x + (bc_{m-1}+dd_{m-1})}=
\frac{a_{m}x+b_{m}}{c_{m}x+d_{m}}}\)

czyli \(\displaystyle{ f^{(m)}}\) jest również funkcją wymierną, przy czym otrzymaliśmy układ rekurencji:

\(\displaystyle{ a_{m}=aa_{m-1}+cb_{m-1}}\)

\(\displaystyle{ b_{m}=ba_{m-1}+db_{m-1}}\)

\(\displaystyle{ c_{m}=ac_{m-1}+cd_{m-1}}\)

\(\displaystyle{ d_{m}=bc_{m-1}+dd_{m-1}}\)

z wyrazami początkowymi:

\(\displaystyle{ a_1=a, \quad b_1=b, \quad c_1=c, \quad d_1=d}\)

Dla \(\displaystyle{ m \ge 1}\) zachodzą następujące 2 zależności:

\(\displaystyle{ cb_m=bc_m}\) (*)

\(\displaystyle{ ba_m+db_m=ab_m+bd_m}\) (**)

Dowód indukcyjny:

Ukryta treść:    

Dla m=1 teza jest oczywista. Załóżmy, że obydwie równości są prawdziwe dla m, pokażemy, że są również prawdziwe dla m+1:

\(\displaystyle{ cb_{m+1}=bc_{m+1}\Leftrightarrow c(ba_{m}+db_{m}) = b (ac_{m}+cd_{m}) \Leftrightarrow}\)

(korzystamy z tezy indukcyjnej-(**))

\(\displaystyle{ \Leftrightarrow c(ab_m+bd_m) = b (ac_{m}+cd_{m}) \Leftrightarrow cab_m=bac_{m}}\)

(korzystamy z tezy indukcyjnej-(*))

\(\displaystyle{ \Leftrightarrow ab c_m=ba c_{m} \Leftrightarrow 0=0}\)

co jest prawdą. Dalej udowodnimy równość (2):

\(\displaystyle{ ba_{m+1}+db_{m+1}=ab_{m+1}+bd_{m+1} \Leftrightarrow b(aa_m+cb_m)+d(ba_m+db_m)= a(ba_m+db_m)+b(bc_m+dd_m) \Leftrightarrow}\)

Po skróceniu podobnych wyrazów:

\(\displaystyle{ \Leftrightarrow bc b_m+bd a_m+d^2 b_m=ad b_m+b^2 c_m+bd d_m \Leftrightarrow bd a_m+d^2 b_m=ad b_m+bd d_m \Leftrightarrow}\)

(skorzystaliśmy z założenia indukcyjnego- (*))

\(\displaystyle{ \Leftrightarrow d(b a_m+d b_m-a b_m-b d_m)=0}\)

ale zgodnie z założeniem indukcyjnym (**) drugi nawias jest równy 0. To oznacza, że udowadniana równość jest prawdziwa i kończy dowód indukcyjny.

Z faktu \(\displaystyle{ f(0) \neq 0}\) wynika, że funkcja ta jest w tym punkcie nieokreślona lub przybiera wartość rzeczywistą różną od 0. Jeżeli jest ona nieokreślona, to nie możemy określić również liczby \(\displaystyle{ f^{n}(0)}\).
Załóżmy więc, że \(\displaystyle{ f(0) \in \mathbb{R} \setminus\{0\}}\). To oznacza, że
\(\displaystyle{ f(0)=\frac{b}{d}\neq0 \Leftrightarrow b\neq 0}\)
Ponadto:
\(\displaystyle{ F(0)=0 \Leftrightarrow \frac{a_n\cdot0+b_n}{c_n\cdot0+d_n}=0 \Leftrightarrow b_n=0}\)
Podstawiając \(\displaystyle{ b_n=0}\) do dwóch udowodnionych powyżej równań- (*) oraz (**):
\(\displaystyle{ bc_n=0 \Leftrightarrow c_n=0}\)
\(\displaystyle{ ba_n=bd_n \Leftrightarrow a_n=d_n}\)
(skorzystaliśmy z tego, że \(\displaystyle{ b \neq 0}\)). Podstawiając \(\displaystyle{ b_n=c_n=0, a_n=d_n}\):
\(\displaystyle{ F(x)=\frac{a_nx+b_n}{c_nx+d_n}=\frac{a_nx}{a_n}=x}\)

Zadanie 3:    

Niech \(\displaystyle{ p_1, p_2,...,p_{n!}}\) będą wszystkimi permutacjami zbioru \(\displaystyle{ \{ 1, \ldots, n \}}\). Niech też
\(\displaystyle{ p_i=(a_{i1}, a_{i2},..., a_{in})}\) dla i=1,2, ..., n. Załóżmy nie wprost, że dla dowolnych
\(\displaystyle{ i, j \in \{ 1, \ldots, n \}, \, i \neq j}\) mamy \(\displaystyle{ n! \not | S(p_i)-S(p_j)}\).
To oznacza oczywiście, że wszystkie z liczb \(\displaystyle{ S(p_i)}\) dla i=1, 2,..., n! dają różne reszty \(\displaystyle{ \pmod{n!}}\). Niech \(\displaystyle{ r_i}\) oznacza dodatnią resztę z dzielenia liczby \(\displaystyle{ S(p_i)}\) przez n!.
Wtedy liczby \(\displaystyle{ r_1, r_2, ..., r_{n!}}\) są pewną permutacją zbioru \(\displaystyle{ \{0,1,2,..., n!-1\}}\), więc:

\(\displaystyle{ \sum_{i=1}^{n!}S(p_i) \equiv \sum_{i=0}^{n!-1}i \equiv \frac{n!(n!-1)}{2} \pmod{n!}}\)

Z drugiej strony, dowolna liczba ze zbioru \(\displaystyle{ \{ 1, \ldots, n \}}\) występuje w (n-1)!
permutacjach na j-tym miejscu (gdzie \(\displaystyle{ j\in \{ 1, \ldots, n \}}\)), więc:

\(\displaystyle{ \sum_{i=1}^{n!}S(p_i)= \sum_{i=1}^{n!} \sum_{j=1}^{n}c_ja_{ij}= \sum_{j=1}^{n} c_j(n-1)!(1+2+3+...+n)=
\sum_{j=1}^{n} c_j(n-1)! \cdot \frac{n(n+1)}{2}}\)

Liczba n+1 jest parzysta, więc liczba \(\displaystyle{ n!\cdot\frac{n+1}{2}}\) dzieli się przez n!, czyli
\(\displaystyle{ \frac{n!(n!-1)}{2} \equiv \sum_{i=1}^{n!}S(p_i) \equiv \sum_{j=1}^{n} c_j \cdot n! \cdot \frac{n+1}{2} \equiv 0 \pmod{n!}}\)

To oznacza, że liczba \(\displaystyle{ \frac{n!(n!-1)}{2}}\) powinna dzielić się przez n!. Ale
\(\displaystyle{ \frac{n!(n!-1)}{2}:n!=\frac{(n!-1)}{2} \not \in \mathbb{Z}}\)
gdyż dla n>1 mamy \(\displaystyle{ 2|n!=1\cdot 2\cdot \ldots n \Rightarrow 2 \not |n!-1}\). Uzyskana sprzeczność kończy dowód.

Zadanie 4:    

Wprowadźmy taki układ współrzędnych, by punkt (0,0,0) znajdował się w wspólnym punkcie 3 półprostych,
zaś proste te pokrywały się z dodatnimi półosiami OX, OY, OZ. Załóżmy też, że trójkąt, który chcemy umieścić
w układzie współrzędnych ma boki długości a,b,c. Trójkąt ten jest ostrokątny, więc suma kwadratów długości
dowolnych 2 boków jest większa od kwadratu długości trzeciego boku
(\(\displaystyle{ a^2+b^2-c^2=2ab\cos \alpha>0}\), bo \(\displaystyle{ \alpha}\), czyli kąt między bokami o długości a, b jest ostry. Analogicznie dla pozostałych dwóch boków). Przyjmijmy:

\(\displaystyle{ x=\sqrt{\frac{b^2+c^2-a^2}{2}}}\)

\(\displaystyle{ y=\sqrt{\frac{a^2+c^2-b^2}{2}}}\)

\(\displaystyle{ z=\sqrt{\frac{a^2+b^2-c^2}{2}}}\)

oraz \(\displaystyle{ A=(x,0,0), B=(0,y,0), C=(0,0,z)}\). Wtedy, ponieważ liczby x,y,z są dodatnie, punkty A, B, C leżą na półprostych z zadania.
Ponadto: \(\displaystyle{ |AB|=\sqrt{x^2+y^2}=c, |AC|=\sqrt{x^2+z^2}=b, |BC|=\sqrt{y^2+z^2}=a}\).
Trójkąt ABC ma więc boki długości a,b,c- jest przystający do trójkąta, który chcieliśmy umieścić na tych półprostych, co kończy dowód.

Zadanie 5:    

Pokażemy, że jest to nieprawda, przez podanie kontrprzykładu. Niech \(\displaystyle{ P(x)=x+1}\) (oczywiście P jest wielomianem o współczynnikach całkowitych). Załóżmy nie wprost, że wielomian ten ma cykl
\(\displaystyle{ (a_1, a_2, ..., a_k)}\) oraz k>1. Zauważmy, że

\(\displaystyle{ 1>0 \Rightarrow P(x)=1+x>x}\)

dla dowolnego x rzeczywistego. Stąd: \(\displaystyle{ a_{i}<P(a_i)=a_{i+1}}\)- ciąg (\(\displaystyle{ a_i}\)) jest więc
ściśle rosnący, czyli
\(\displaystyle{ a_1<a_2<...<a_k<P(a_k)=a_1}\)
Sprzeczność kończy dowód.

Pozdrawiam, jgarnek