kategoria II - timon92 11 stycznia 2011, 19:34

Miejsce na dyskusje i ocenę zadań z I konkursu forumowego ;).
Liga
Gość Specjalny
Gość Specjalny
Posty: 168
Rejestracja: 29 wrz 2006, o 18:17
Płeć: Mężczyzna
Lokalizacja: Forum Matematyka.pl

kategoria II - timon92 11 stycznia 2011, 19:34

Post autor: Liga »

timon92 pisze:1. Nie wprost załóżmy, że dla każdego \(\displaystyle{ c>0}\) istnieje para liczb \(\displaystyle{ (m,n)}\) taka że \(\displaystyle{ m,n \in \mathbb Z, n>0}\) oraz \(\displaystyle{ \left| \sqrt[3]2 - \frac{m}{n} \right| \le \frac{c}{n^3}}\)

Wówczas

\(\displaystyle{ \left| \sqrt[3]2 - \frac{m}{n} \right| \le \frac{c}{n^3} \iff \\
\left| n \sqrt[3]2 - m \right| \le \frac{c}{n^2} \iff \\
\left( n \sqrt[3]2 - m \right)^2 \le \frac{c^2}{n^4} \iff \\
\left( m - n \sqrt[3]2 \right)^2 - \frac{c^2}{n^4} \le 0 \iff \\
\left( m - n \sqrt[3]2 - \frac{c}{n^2} \right)\left( m - n \sqrt[3]2 + \frac{c}{n^2} \right) \le 0 \iff \\
m \in \left[ n \sqrt[3]2 - \frac{c}{n^2}, n \sqrt[3]2 + \frac{c}{n^2} \right]}\)


Oznacza to, że dla dowolnego \(\displaystyle{ c>0}\) w przedziale \(\displaystyle{ \left[ n \sqrt[3]2 - \frac{c}{n^2}, n \sqrt[3]2 + \frac{c}{n^2} \right]}\) znajduje się liczba całkowita. \(\displaystyle{ (*)}\)

Jednakże dla dodatniego \(\displaystyle{ c}\) spełniającego nierówności \(\displaystyle{ c < n^2 \{ \sqrt[3]2 \} \ (1)}\) oraz \(\displaystyle{ c < n^2 (1 - \{ \sqrt [3] 2 \}) \ (2)}\). (takie \(\displaystyle{ c}\) istnieje - wystarczy wziąć np. \(\displaystyle{ \frac{1}{2} \min \left(n^2 \{ \sqrt[3]2 \}, n^2 (1 - \{\sqrt [3] 2 \})\right)}\)) w oczywisty sposób zachodzą następujące nierówności

\(\displaystyle{ \lfloor \sqrt[3]2 \rfloor < \sqrt[3]2 - \frac{c}{n^2} < \sqrt[3]2 < \sqrt[3]{2} + \frac{c}{n^2} < \lfloor \sqrt[3]2 \rfloor + 1}\)

Łatwo sprawdzić, że pierwsza z nich jest równoważna \(\displaystyle{ (1)}\), dwie środkowe są równoważne \(\displaystyle{ c>0}\), ostatnia zaś jest równoważna \(\displaystyle{ (2)}\)

Wynika z nich, że w przedziale \(\displaystyle{ \left[ n \sqrt[3]2 - \frac{c}{n^2}, n \sqrt[3]2 + \frac{c}{n^2} \right]}\) nie ma liczby całkowitej, co jest sprzeczne z \(\displaystyle{ (*)}\). Otrzymana sprzeczność nie wprost kończy rozwiązanie zadania.





2. Zdefiniujmy nieskończone ciągi liczb rzeczywistych \(\displaystyle{ a_1,a_2,..., b_1,b_2,..., c_1,c_2,..., d_1,d_2,...}\) tak, by \(\displaystyle{ f^i(x) = \frac{a_ix+b_i}{c_ix+d_i}}\) dla \(\displaystyle{ i=1,2,...}\) . Zauważmy, że \(\displaystyle{ a_1=a,b_1=b,c_1=c,d_1=d}\). Ponadto

\(\displaystyle{ \frac{a_{i+1}x+b_{i+1}}{c_{i+1}x+d_{i+1}}=f^{i+1}(x) = f(f^i(x)) = \frac{a \cdot f^i(x)+b}{c \cdot f^i(x)+d} = \frac{a \cdot \frac{a_ix+b_i}{c_ix+d_i}+b}{c \cdot \frac{a_ix+b_i}{c_ix+d_i}+d} = \\ \frac{a \cdot (a_ix+b_i)+b({c_ix+d_i})}{c \cdot({a_ix+b_i})+d({c_ix+d_i})} =
\frac{(aa_i+cb_i)x + ba_i+db_i}{(ac_i+cd_i)x+bc_i+dd_i}}\)


Dostajemy stąd rekurencję

\(\displaystyle{ a_{i+1} = aa_i+cb_i \\
b_{i+1} = ba_i+db_i \\
c_{i+1} = ac_i+cd_i \\
d_{i+1} = bc_i+dd_i}\)


Pokażemy indukcyjnie, że \(\displaystyle{ cb_i=bc_i \ (1)}\) oraz \(\displaystyle{ b(a_i-d_i) = (a-d)b_i \ (2)}\).

Dla \(\displaystyle{ i=1}\) równości te w oczywisty sposób zachodzą.

Załóżmy teraz, że równości \(\displaystyle{ (1),(2)}\) zachodzą dla pewnego \(\displaystyle{ i}\). Pokażemy, że zachodzą też dla \(\displaystyle{ i+1}\).

\(\displaystyle{ (1):}\)
\(\displaystyle{ cb_{i+1} = bc_{i+1} \iff \\ cba_i+cdb_i = abc_i+bcd_i \iff \\ cba_i + cdb_i = acb_i+bcd_i \iff \\ c (b(a_i-d_i) - (a-d)b_i)=0 \iff 0=0}\)

\(\displaystyle{ (2):}\)
\(\displaystyle{ b(a_{i+1}-d_{i+1}) = (a-d)b_{i+1} \iff \\
aba_i+bcb_i-b^2c_i-bdd_i=aba_i+adb_i-bda_i-d^2b_i \iff \\
b^2c_i-b^2c_i-bdd_i-adb_i+bda_i+d^2b_i=0 \iff \\
d(b(a_i-d_i) - (a-d)b_i)=0 \iff 0=0}\)


Na mocy indukcji matematycznej równości \(\displaystyle{ (1),(2)}\) zachodzą dla wszelkich \(\displaystyle{ i=1,2,3,...}\)

Zauważmy, że

\(\displaystyle{ F(0)=0 \implies \frac{a_{n} \cdot 0+b_{n}}{c_{n}\cdot 0+d_{n}} = 0 \implies b_n=0}\)

Z \(\displaystyle{ (1)}\) i założenia \(\displaystyle{ b \neq 0}\) mamy \(\displaystyle{ c_n=\frac{cb_n}{b} = 0}\). Natomiast z \(\displaystyle{ (2)}\) i z \(\displaystyle{ b \neq 0}\) mamy \(\displaystyle{ a_n-d_n=\frac{(a-d)b_n}{b} = 0 \implies a_n=d_n}\). Przeto

\(\displaystyle{ F(x) = \frac{a_nx+b_n}{c_nx+d_n} = \frac{a_nx}{a_n} = x}\), cbdu.





3. Nie wprost przypuśćmy, że nie istnieją permutacje \(\displaystyle{ a,b}\) takie, że \(\displaystyle{ n! | S(a) - S(b)}\), czyli, że dla dowolnych permutacji \(\displaystyle{ a,b}\) zachodzi \(\displaystyle{ S(a) \not \equiv S(b) \mod n! \quad (*)}\)

Niech \(\displaystyle{ p_1, p_2, ..., p_{n!}}\) będą różnymi permutacjami zbioru \(\displaystyle{ \{ 1,2,...,n \}}\). Jest ich \(\displaystyle{ n!}\), co w połączeniu z \(\displaystyle{ (*)}\) implikuje \(\displaystyle{ \{ S(p_1), S(p_2), ..., S(p_{n!}) \} = \{ 1,2,...,n! \} \mod n! \quad (**)}\)

Policzmy sumę \(\displaystyle{ \sum_{i=1}^{n!} S(p_i)}\) modulo \(\displaystyle{ n!}\) na dwa sposoby.

Skoro \(\displaystyle{ (**)}\), to \(\displaystyle{ \sum_{i=1}^{n!} S(p_i) \equiv \sum_{i=1}^{n!} i = \frac{n! \cdot (n!+1)}{2} = \frac{(n!)^2}{2} + \frac{n!}{2} \equiv \frac{n!}{2} \mod n!}\)

gdyż \(\displaystyle{ n>1}\).


Z drugiej strony łatwo zauważyć, że każda z liczb \(\displaystyle{ 1,2,...,n}\) wśród różnych permutacji zbioru \(\displaystyle{ \{ 1,2,...,n \}}\) występuje \(\displaystyle{ (n-1)!}\) razy na \(\displaystyle{ i}\)-tej pozycji dla \(\displaystyle{ i=1,2,...,n}\). Przeto

\(\displaystyle{ \sum_{i=1}^{n!} S(p_i) = \sum_{i=1}^{n!} \sum _{j=1}^{n} c_j p_{i_j} \equiv (n-1)! \left( \sum_{i=1}^{n} c_i \right) \cdot \left( \sum_{i=1}^{n} i \right) = \\ (n-1)! \cdot \frac{n(n+1)}{2} \cdot \sum_{i=1}^{n} c_i = n! \cdot \frac{n+1}{2} \cdot \sum_{i=1}^{n} c_i \equiv 0 \mod n!}\)

gdyż liczba \(\displaystyle{ \frac{n+1}{2}}\) jest całkowita (bo \(\displaystyle{ n}\) jest nieparzyste).

Pokazaliśmy więc, że \(\displaystyle{ \frac{n!}{2} \equiv 0 \mod n!}\), co jest oczywistą sprzecznością, która nie wprost kończy dowód.





4. Oznaczmy półproste z zadania \(\displaystyle{ k,l,m}\). Niech ich ich wspólnym punktem będzie \(\displaystyle{ O}\).

Rozważmy trójkąt ostrokątny \(\displaystyle{ ABC}\) o bokach długości \(\displaystyle{ a,b,c}\). Niech
\(\displaystyle{ X=-a^2+b^2+c^2, \\Y=a^2-b^2+c^2, \\ Z=a^2+b^2-c^2.}\)

Ponieważ trójkąt ten jest ostrokątny, więc \(\displaystyle{ X,Y,Z>0}\).

Obierzmy na półprostych \(\displaystyle{ k,l,m}\) punkty \(\displaystyle{ K,L,M}\) odpowiednio, takie że
\(\displaystyle{ OK^2 = \frac X 2 , \\
OL^2 = \frac Y 2 , \\
OM^2 = \frac Z 2 .}\)


Wówczas na mocy twierdzenia Pitagorasa mamy
\(\displaystyle{ KL^2 = OK^2 + OL^2 = \frac X 2 + \frac Y 2 = \frac{-a^2+b^2+c^2 + a^2 - b^2 + c^2}{2} = c^2 \implies \\ KL=c}\)

Analogicznie dostajemy, że \(\displaystyle{ LM = a, MK = b}\)

Wystarczy więc umieścić trójkąt \(\displaystyle{ ABC}\) w miejsce trójkąta \(\displaystyle{ KLM}\), ckd.





5. Teza nie jest prawdziwa.

Pokażemy, że wielomian \(\displaystyle{ W(x)=x+1}\) nie ma cyklu całkowitego długości co najmniej \(\displaystyle{ 2}\).

Przypuśćmy nie wprost, że wielomian \(\displaystyle{ W(x)}\) ma cykl całkowity \(\displaystyle{ (a_1,a_2,...,a_k)}\), przy czym \(\displaystyle{ k \ge 2}\). Wówczas \(\displaystyle{ a_{i+1}=W(a_i) = a_i+1 > a_i}\) dla każdego \(\displaystyle{ i=1,2,...,k-1}\). Zatem \(\displaystyle{ a_k > a_{k-1} > ... > a_1 \quad (*)}\).

Z drugiej strony mamy \(\displaystyle{ a_1 = W(a_k) = a_k+1 > a_k}\), co jest sprzeczne z \(\displaystyle{ (*)}\).

Otrzymana sprzeczność nie wprost kończy uzasadnienie odpowiedzi.
Awatar użytkownika
Sylwek
Użytkownik
Użytkownik
Posty: 2716
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 160 razy
Pomógł: 657 razy

kategoria II - timon92 11 stycznia 2011, 19:34

Post autor: Sylwek »

Oceny:

Zadanie 1: 6
Zadanie 2: 6
Zadanie 3: 6
Zadanie 4: 6
Zadanie 5: 6
ODPOWIEDZ