Teoria liczb

grupa starsza poniedziałek, 27 września 2004

Równania teorioliczbowe.

1. Rozwi _{}azać w liczbach całkowitych x, y, z.

x^{3} + 3y^{3} + 9z^{3} − 9xyz = 0.

2. Rozwi _{}azać w liczbach całkowitych dodatnich x, y:

x^{2} + 3y^{2} = 1998x.

3. Zadanie z poniedziałku, z szacowaniem.

4. Kwadraty w zadaniach. Dane s _{}a liczby całkowite nieujemne a i b, takie, że dla każdej liczby całkowitej nieujemnej n liczba 2^{n}a + b jest kwadratem liczby całkowitej. Wykazać, że a = 0.

Ci _{}ag Fibonacciego.

1. Dla każdego k istnieje x, że k | F_{x}.

2. NW D(F_{n+1} , F_{n}) = 1.

3. n | m ⇒ F_{n} | F_{m}.

4. F_{1} + F_{2} + … + F_{n} = F_{n+2} − 2.

5. F_{n}^{2} = F_{n−1} ∗ F_{n+1} + (−1)^{n+1} .

Reszty kwadratowe. Jeśli rozpatrzymy liczby 1^{2}, …, (p − 1)^{2} modulo liczba pierwsza nieparzysta p, to otrzymamy dokładnie \frac{p−1}{2} różnych reszt, każd _{}a dokładnie 2 razy.

1. Wykazać, że jeśli p > 3 jest pierwsze, to istniej _{}a liczby całkowite x, y, k takie, że 0 < 2k < p i

kp + 3 = x^{2} + y^{2}.

Małe twierdzenie Fermata. Jeśli p jest pierwsza, a a całkowita, to p | a^{p} − a. Jeśli p nie dzieli a, to p | a^{p−1} − 1.

Twierdzenie Eulera. Jeśli n jest całkowita dodatnia, a a całkowita wzgl_{}ednie pierwsza z n, to n | a^{ϕ(n)} − 1, gdzie ϕ(n) oznacza liczb_{}e liczb mniejszych od n wzgl_{}ednie pierwszych z n.

Zadania na MTF i Eulera. ”Cebulkologia”.

1. Niech p b_{}edzie liczb _{}a pierwsz _{}a. Wykazać, że jeśli liczba 11 …1 (p jedynek) dzieli si_{}e przez p, to p = 3.

2. Wykazać, że jeśli p jest pierwsze, to p | 11 …122 …2 …99 …9−123456789 (każda cyfra pojawia si_{}e w odjemnej p razy).

3. Wykazać, że jeśli p | a^{p} − b^{p}, p pierwsze, a, b całkowite, to p^{2} | a^{p} − b^{p}.

4. Wykazać, że żadna liczba n > 1 nie spełnia warunku n | 2^{n} − 1.

Algorytm euklidesa i dzielenie modulo p.

1. Jakie s _{}a liczby a, b < 1000, że algorytm euklidesa dla nich działa najwolniej?

2. Wykazać, że jeśli d = NW D(a, b), to istniej _{}a liczby całkowite x i y, że d = ax + by.

3. Wniosek: dla każdej liczby 0 < x < p (p - pierwsze) istnieje dokładnie jedna liczba 0 < y < p taka, że p | xy − 1.

Ciało ℤ_{p}. Reszty z dzielenia przez p dla p pierwszego tworz _{}a pełnoprawne ciało. Można dzielić przez reszty (poza zerem oczywiście). Wielomiany w ℤ_{p} maj _{}a rozwi _{}azania, zachodzi tw. Bezout.

Twierdzenie Wilsona. Jeśli p jest pierwsze, to p | (p − 1)! + 1.

Chińskie twierdzenie o resztach. Jeśli liczby całkowite n_{1}, n_{2}, …, n_{k} s _{}a parami wzgl_{}ednie pierwsze i n = n_{1} · n_{2} · . . . · n_{k}, zaś liczby a_{1}, a_{2}, …, a_{k} s _{}a dowolnymi liczbami całkowitymi, to istnieje dokładnie jedna liczba całkowita 0 x < n taka, że dla każdego i ∈ {1, 2, …, k} zachodzi własność:

x ≡ a_{i} mod n_{i}.

Inaczej mówi _{}ac, możemy ż _{}adać od x, aby miała określone reszty z dzielenia przez wzgl_{}ednie pierwsze liczby n_{i}, i to twierdzenie nam gwarantuje, że dokładnie jedna liczba taka poniżej n b_{}edzie istnieć.

1. Czy istnieje zbiór 2004 liczb całkowitych dodatnich taki, że suma każdego niepustego podzbioru jest pot_{}eg _{}a liczby całkowitej o wykładniku wi_{}ekszym od jednego?

Stożkowe

grupa starsza środa, 29 września 2004

Elipsa. Zbiór punktów o równej sumie odległości od dwóch punktów, zwanych ogniskami.

1. Elipsa w stożku.

2. Ognisko odbite wzgl_{}edem stycznej, punkt styczności i drugie ognisko s _{}a współliniowe.

3. Rzuty ognisk na styczne leż _{}a na okr_{}egu.

4. Zadanie: Dane s _{}a ogniska i długość dużej osi elipsy oraz punkt P, który do tej elipsy nie należy. Skonstruować prost _{}a styczn _{}a do tej elipsy, przechodz _{}ac _{}a przez punkt P.

5. Zadanie: Wykazać, że iloczyn odległości ognisk danej elipsy od prostej stycznej do tej elipsy nie zależy od wyboru stycznej.

6. Elipsa wpisana w k _{}at wtw. k _{}aty mi_{}edy ogniskami a ramionami s _{}a równe.

7. Zastosowanie powyższego w trójk _{}acie: punkty dualne. Dualność ortocentrum i środka okregu opisanego.

8. Zadanie*, finał 54 OM: Sfera wpisana w czworościan ABCD jest styczna do ściany ABC w punkcie X, zaś sfera dopisana naprzeciwko wierzchołka D jest styczna do ściany ABC w punkcie Y. Wykazać, że X jest ortocentrum ABC wtedy i tylko wtedy, gdy Y jest środkiem okr_{}egu opisanego.

Parabola. Zbiór punktów o równej odległości od prostej (kierownicy) i punktu (ogniska).

1. Ognisko odbite wzgl_{}edem stycznej l _{}aduje na kierownicy.

2. Zadanie: Znaleźć zbiór rzutów ogniska na styczne.

3. Zadanie: Dane jest ognisko i kierownica paraboli oraz punkt P, który do tej paraboli nie należy. Skonstruować prost _{}a styczn _{}a do tej paraboli, przechodz _{}ac _{}a przez punkt P.

4. Zadanie: Proste l i m s _{}a styczne do paraboli p odpowiednio w punktach A i B. Wykazać,

że nast_{}epuj _{}ace warunki s _{}a równoważne:

• ognisko paraboli p leży na prostej AB,

• proste l i m s _{}a prostopadłe,

• punkt przeci_{}ecia prostych l i m należy do kierownicy paraboli p.

Hiperbola. Zbiór punktów o stałej różnicy odległości od dwóch punktów.

1. Zbiór obrazów symetrycznych ogniska wzgl_{}edem stycznych.

2. Zbiór rzutów ognisk na styczne.

Stożkowe

grupa najstarsza wtorek, 28 września 2004

Elipsa. Zbiór punktów o równej sumie odległości od dwóch punktów, zwanych ogniskami.

1. Elipsa w stożku.

2. Ognisko odbite wzgl_{}edem stycznej, punkt styczności i drugie ognisko s _{}a współliniowe.

3. Rzuty ognisk na styczne leż _{}a na okr_{}egu.

4. Zadanie: Dane s _{}a ogniska i długość dużej osi elipsy oraz punkt P, który do tej elipsy nie należy. Skonstruować prost _{}a styczn _{}a do tej elipsy, przechodz _{}ac _{}a przez punkt P.

5. Zadanie: Co to za punkty, z których widać elips_{}e pod k _{}atem prostym?

6. Zadanie: Wykazać, że iloczyn odległości ognisk danej elipsy od prostej stycznej do tej elipsy nie zależy od wyboru stycznej.

7. Elipsa wpisana w k _{}at wtw. k _{}aty mi_{}edy ogniskami a ramionami s _{}a równe.

8. Zastosowanie powyższego w trójk _{}acie: punkty dualne. Dualność ortocentrum i środka okregu opisanego.

9. Zadanie, finał 54 OM: Sfera wpisana w czworościan ABCD jest styczna do ściany ABC w punkcie X, zaś sfera dopisana naprzeciwko wierzchołka D jest styczna do ściany ABC w punkcie Y. Wykazać, że X jest ortocentrum ABC wtedy i tylko wtedy, gdy Y jest środkiem okr_{}egu opisanego.

Parabola. Zbiór punktów o równej odległości od prostej (kierownicy) i punktu (ogniska).

1. Ognisko odbite wzgl_{}edem stycznej l _{}aduje na kierownicy.

2. Zadanie: Znaleźć zbiór rzutów ogniska na styczne.

3. Zadanie: Dane jest ognisko i kierownica paraboli oraz punkt P, który do tej paraboli nie należy. Skonstruować prost _{}a styczn _{}a do tej paraboli, przechodz _{}ac _{}a przez punkt P.

4. Zadanie: Proste l i m s _{}a styczne do paraboli p odpowiednio w punktach A i B. Wykazać,

że nast_{}epuj _{}ace warunki s _{}a równoważne:

• ognisko paraboli p leży na prostej AB,

• proste l i m s _{}a prostopadłe,

• punkt przeci_{}ecia prostych l i m należy do kierownicy paraboli p.

Hiperbola. Zbiór punktów o stałej różnicy odległości od dwóch punktów.

1. Zbiór obrazów symetrycznych ogniska wzgl_{}edem stycznych.

2. Zbiór rzutów ognisk na styczne.

Zadania różne i różne fakciki.

1. Zadanie: Wewn _{}atrz trójk _{}ata ABC znajduje si_{}e punkt P.

(a) Wykazać, że odbicia symetryczne prostych AP, BP i CP wzgledem odpowiednio dwusiecznych wewn_{}etrznych k _{}atów A, B i C trójk _{}ata ABC przecinaj _{}a si_{}e w jednym punkcie Q.

(b) Wykazać, że rzuty prostok _{}atne punktów P i Q na boki trójk _{}ata ABC leż _{}a wszystkie na jednym okr_{}egu.

2. Zadanie: Niech M i N b_{}ed _{}a takimi punktami wewn _{}atrz trójk _{}ata ABC, że miary k _{}atów ∡MAB i ∡NAC oraz ∡MBA i ∡NBC s _{}a równe. Udowodnij, że:

\frac{AM · AN}{AB · AC} + \frac{BM · BN}{BA · BC} + \frac{CM · CN}{CA · CB} = 1.

3. Fakt: Twierdzenie Pascala i Brianchona działa również dla dowolnych stożkowych.

Nierówności

grupa pierwszoklasistów czwartek, 30 września 2004

1. Dowieść, że dla każdych rzeczywistych a, b, c, d > 0 zachodzi:

2\sqrt{a} + 3\sqrt[3]{b} 5\sqrt[5]{ab}

abc = 1 ⇒ (a + 2b)(b + 2c)(c + 2a) 27

a^{2} + b^{2} + c^{2} = 8 ⇒ a^{3} + b^{3} + c^{3} 16\sqrt{\frac{2}{3}}

\frac{ab}{c}+ \frac{bc}{a}+ \frac{ca}{b} a + b + c

2(a^{3} + b^{3} + c^{3}) bc(b + c) + ac(a + c) + ab(a + b)

\frac{abc}{d^{2}}+ \frac{abd}{c^{2}}+ \frac{acd}{b^{2}} + \frac{bcd}{a^{2}} a + b + c + d

a^{3}b + b^{3}c + c^{3}a a^{2}bc + b^{2}ac + c^{2}ab

(a + b + c)( \frac{1}{a} + \frac{1}{b} + \frac{1}{c}) 9

a + b + c + d \sqrt[10]{\frac{4^{5}}{27}ab^{2}c^{3}d^{4}}

\frac{1}{a} + \frac{1}{b} + \frac{4}{c} + \frac{16}{d} \frac{64}{a + b + c + d}

2. Dowieść, że dla każdej liczby naturalnej n 2 i dla każdych liczb rzeczywistych dodatnich x_{1}, x_{2}, …, x_{n} zachodzi nierówność:

∑_{i=1}^{n} ix_{i} \binom{n}{2} + ∑_{i=1}^{n} x_{i}^{i}

( ∑_{i=1}^{n} x_{i}) ( ∑_{i=1}^{n} \frac{1}{x_{i}} ) n^{2}

∑_{i=1}^{n} x_{i} = 1 ⇒ \frac{1}{x_{1} + x_{2}} + \frac{1}{x_{2} + x_{3}} + … + \frac{1}{x_{n−1} + x_{n}} + \frac{1}{x_{n} + x_{1}} \frac{n^{2}}{2}

(x_{1} + x_{2})(x_{2} + x_{3}) …(x_{n−1} + x_{n})(x_{n} + x_{1}) 2^{n}x_{1}x_{2} …x_{n}

∑_{i=1}^{n} x_{i} = 1 ⇒ (1 + x_{1})(1 + x_{2}) …(1 + x_{n}) (n + 1)^{n}x_{1}x_{2} …x_{n}

∑_{i=1}^{n} \frac{x_{i−2} + x_{i+1}}{x_{i−1} + x_{i}} n

3. Udowodnić, że jeśli a, b, c s _{}a długościami boków trójk _{}ata, to:

\frac{3}{2} \frac{a}{b + c} + \frac{b}{c + a} + \frac{c}{a + b} < 2

\frac{1}{a} + \frac{1}{b} + \frac{1}{c} \frac{1}{a + b − c} + \frac{1}{a − b + c} + \frac{1}{−a + b + c}

\sqrt{a + b − c} + \sqrt{a − b + c} + \sqrt{−a + b + c} \sqrt{a} + \sqrt{b}+ \sqrt{c} Wielomiany w kombinatoryce

grupa najstarsza czwartek, 30 września 2004

Dwumian Newtona, podstawowe tożsamości i dowody kombinatoryczne i wielomianowe. Dużo dać, by wćwiczyć. Każdego przy tablicy do jednego.

Liczby Stirlinga I i II rodzaju. Jeśli liczby Bella robimy, tak naprawd_{}e. Funkcje tworz _{}ace - definicja, pomysł. Dodawanie, mnożenie. Wykładnicze funkcje

tworz _{}ace.

Rozwi _{}azywanie równań rekurencyjnych. Wpierw Fibonacciopodobne. Nast_{}epnie liczby Catalana. I ew. liczby Bella.

Enumeratory. Przykład: kombinacje z powtórzeniami. Zasada właczeń i wył _{}aczeń.. D(k) - liczba tych elementów z X, ktżoe maj _{}a dokładnie

k spośród własności A_{1}, A_{2}, . . .. S_{i} - suma mocy przeci_{}eć i-tek zbiorów.

D(k) = ∑_{j=k}^{∞} (−1)^{j−k} \binom{j}{k} S_{j}

Przykład: liczba funkcji z n na k.

Wieżomiany. Funkcja tworz _{}aca. Jakiś przykład. Wzór z zabieraniem jednego. Wzor na odwracanie:

r_{k}(B) = \frac{1}{(m − k)!} ∑_{i=0}^{k} (−1)^{i} \binom{n − i}{k − i} (n − i)!r_{i}(C).

Dzielenie liczby na sum_{}e innych liczb. Wpierw enumetator podstawowy. Dalej inne sztuczki: dokładnie tyle i tyle składników. Tylko nieparzyste. Itd.

Diagram Ferrersa. Tożsamość Eulera:

nP (n) = ∑_{k=0}^{n−1} σ(n − k)P (k).

Zadanka a’la Onufry. Wyznaczyć wszystkie ci _{}agi a_{1} a_{2} … a_{n} liczb nieujemnych o minimalnej długości, że

∑_{i=1}^{n} a_{i} = 25, ∑_{i=1}^{n} a_{i}^{2} = 33, ∑_{i=1}^{n} a_{i}^{3} = 49, ∑_{i=1}^{n} a_{i}^{4} = 81.

Metody sumowania i szacowania sum

grupa najstarsza sobota, 2 października 2004

Indukcja. H_{2^{n}} n + 1. Zaburzanie. ax^{k}. n2^{n}. Zmiana kolejności sumowania. Rachunek różnicowy. Definicja. Liniowość. Taka całka. Całkowanie przez cz_{}eści. Kilka

przykładów.

Szybko zmieniaj _{}ace si_{}e składniki. Np. ∑ _{k=1}^{n} k^{k}. Liczba nieporz _{}adków i jej oszacowanie. Rozwini_{}ecie e^{x} w szereg. Całkowanie. Szacowanie przez całk_{}e. Szacujemy H_{n}. Wzór sumacyjny Eulera-McLaurina. Idea, co małe, co duże, sk _{}ad to si_{}e bierze. Szacu-

jemy H_{n} jeszcze lepiej. Szacowanie n!. Wnioski: szacowanie n!, 1/n itd. Wzór Stirlinga, itd. (1 + \frac{1}{n})^{n}.