[MIX] próbny II etap (2)

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX] próbny II etap (2)

Post autor: Dumel » 18 gru 2008, o 14:34

akurat Dumel do tego wzorcówki nie ma. zrobilem to zadanie pare miesiecy temu i jak pamietam bylo calkiem fajne, ale moj dowod pamietam jak przez mgle

Awatar użytkownika
max
Gość Specjalny
Gość Specjalny
Posty: 3306
Rejestracja: 10 gru 2005, o 17:48
Płeć: Mężczyzna
Lokalizacja: Lebendigentanz
Podziękował: 37 razy
Pomógł: 778 razy

[MIX] próbny II etap (2)

Post autor: max » 18 gru 2008, o 18:47

A jeśli tak, to wrzucę, zwłaszcza, że nie zaobserwowałem protestów;)
Mi też zadanie się spodobało.
Dumel pisze: zad. 6.
Niech \(\displaystyle{ k}\) będzie liczbą całkowitą dodatnią orac ciąg \(\displaystyle{ (a_n)}\) będzie zdefiniowany następująco:
\(\displaystyle{ a_1=k, a_n=k^{a_{n-1}}}\) dla \(\displaystyle{ n>1}\). Pakazać, że jeśli \(\displaystyle{ m}\) jest dowolną liczbą całkowitą dodatnią, to ciąg \(\displaystyle{ a_n}\) jest od pewnego miejsca stały modulo \(\displaystyle{ m}\).
Najpierw bardzo ogólna idea rozwiązania, a w zasadzie wskazówka, jeśli ktoś chciałby zrobić to samemu, ale brakuje mu pomysłu: indukcja, rząd modulo \(\displaystyle{ m}\), chińskie tw o resztach.

Poniżej jest pełne rozwiązanie.

.
.
.
.
.
.
.
.
.

Ustalmy dowolne \(\displaystyle{ k}\) całkowite dodatnie.
Dalej indukcja po \(\displaystyle{ m}\).

Dla \(\displaystyle{ m = 2}\) teza jest oczywista (wszystkie reszty są takie same jak reszty dla \(\displaystyle{ k}\)).

Załóżmy, że zachodzi dla wszystkich liczb naturalnych mniejszych od \(\displaystyle{ m}\).

Jeśli \(\displaystyle{ m = p^{\alpha}}\), gdzie \(\displaystyle{ p}\) jest liczbą pierwszą, \(\displaystyle{ \alpha > 0}\), to mamy dwie sytuacje:

(i) \(\displaystyle{ p|k}\), wtedy wszystkie reszty są od pewnego miejsca zerowe.

(ii) \(\displaystyle{ (p,k) = 1}\), wtedy niech \(\displaystyle{ l}\) będzie rzędem \(\displaystyle{ k}\) modulo \(\displaystyle{ p^{\alpha}}\). Ponieważ \(\displaystyle{ l n_{0}}\), wtedy również \(\displaystyle{ k^{a_{n}} \equiv k^{s}\pmod{p^{\alpha}}}\) dla \(\displaystyle{ n > n_{0}}\), czyli nasz ciąg jest też od pewnego miejsca stały modulo \(\displaystyle{ p^{\alpha}}\).

Jeśli \(\displaystyle{ m = p^{\alpha}\cdot m_{0}}\), gdzie \(\displaystyle{ p}\) jest liczbą pierwszą nie dzielącą \(\displaystyle{ m_{0}> 1}\) oraz \(\displaystyle{ \alpha > 0}\), to z założenia indukcyjnego wiemy, że nasz ciąg jest od pewnego miejsca stały modulo \(\displaystyle{ p^{\alpha}}\) i modulo \(\displaystyle{ m_{0}}\). Z chińskiego tw o resztach dostajemy, że musi być też od tego miejsca stały modulo \(\displaystyle{ p^{\alpha}\cdot m_{0}}\), co kończy krok indukcyjny.
Ostatnio zmieniony 13 gru 2009, o 17:42 przez max, łącznie zmieniany 1 raz.

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX] próbny II etap (2)

Post autor: Dumel » 18 gru 2008, o 21:21

dzieki za fajne rozwiązanie. ja tez wykorzystalem chińskie o resztach i rząd liczby \(\displaystyle{ p^\alpha}\) a reszte mialem jakos inaczej, nie pamietam dokladnie jak, w kazdym razie nieindukcyjnie

ODPOWIEDZ