szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 18 kwi 2009, o 10:58 
Użytkownik

Posty: 659
Lokalizacja: Strzyżów
Wykaż, ze istnieje liczba postaci 20072007...20070...0, która jest podzielna przez 2008.
Góra
Kobieta Offline
PostNapisane: 18 kwi 2009, o 12:28 
Użytkownik

Posty: 5357
Lokalizacja: Gliwice
20072007...20070...0=10^s(2008-1)(1+10^4+(10^4)^2+\cdots +(10^4)^k)
wystarczy więc pokazać, że istnieją takie s i k, że a=10^s (1+10^4 +(10^4 )^2 +\cdots + (10^4 )^k )=_{2008}0;
ponieważ 2008=4x3x167, to ta kongruencja jest równoważna z układem kongruencji a=0 mod 4, a=0 mod 3, a=0 mod 167. pierwsza jest spełniona jeśli tylko s jest co najmniej 2, druga jest spełniona jeśli tylko k=2 modulo 3; dla trzeciej zauważmy, że ponieważ 167 jest liczbą pierwszą względnie pierwszą z 10^4, to z małego twierdzenia Fermata mamy (10^4)^{166}=_{167}1. Wobec tego suma b:=1+10^4+\cdots \ (10^4)^{165} przystaje modulo 167 do każdej sumy postaci (10^4)^{166c}+(10^4)^{166c+1}\cdots + (10^4)^{166(c+1)-1}. Wystarczy takich sum wziąć 167 - wtedy ostatni występujący wykładnik jest postaci 166\cdot 166-1, a ta liczba przystaje do 2 modulo 3, więc to może być k.

Pozdrawiam.

PS można to oczywiście zapisać za pomocą podzielności, ale zapis z kongruencjami jest krótszy.
Góra
Mężczyzna Offline
PostNapisane: 20 kwi 2009, o 18:29 
Użytkownik
Avatar użytkownika

Posty: 370
Lokalizacja: Przemyśl/Kraków
To zadanie pojawiło się na etapie rejonowym ( drugim na trzy) pewnego konkursu wojewódzkiego dla pierwszych klas. Na 99,9% można je zrobić bez użycia MTF, więc jak ktoś znałby inną metodę to mógłby ją przedstawić :)
Góra
Kobieta Offline
PostNapisane: 20 kwi 2009, o 18:52 
Użytkownik

Posty: 5357
Lokalizacja: Gliwice
Można zrobić bez MTF: różnych reszt z dzielenia przez 167 jest tylko 167, więc muszą się w pewnym momencie zacząć powtarzać, czyli dla pewnego m<167 musi być (10^4)^{m}=_{167}1.
reszta tak, jak wyżej, zapisana za pomocą podzielności.
Pozdrawiam.
Góra
Mężczyzna Offline
PostNapisane: 20 kwi 2009, o 19:55 
Użytkownik
Avatar użytkownika

Posty: 370
Lokalizacja: Przemyśl/Kraków
Ok, dzięki, mam nadzieję, że dobrze zrozumiałem.
Góra
Kobieta Offline
PostNapisane: 20 kwi 2009, o 20:08 
Użytkownik

Posty: 5357
Lokalizacja: Gliwice
Dokładniej to wygląda tak (to wyżej napisałam w skrócie):
różnych reszt z dzielenia przez 167 jest 167, rozpatrzmy więc liczbę (10^4)^{166}. Jej reszta z dzielenia przez 167 musi się pokryć z któraś wcześniejszą, powiedzmy z resztą z dzielenia (10^4)^i przez 167 (licząc i od 0, bo mamy w tej sumie też 1) - a wtedy (10^4)^{i}=_{167}(10^4)^{166}, skąd mamy (10^4)^{166-i}=_{167}1.

Pozdrawiam.
Góra
Mężczyzna Offline
PostNapisane: 21 kwi 2009, o 08:01 
Użytkownik
Avatar użytkownika

Posty: 370
Lokalizacja: Przemyśl/Kraków
W tamtym nawiasie nie ma żadnych różnic, tylko sumy. Możesz pokazać w jaki sposób to redukuje się?
Góra
Mężczyzna Offline
PostNapisane: 21 kwi 2009, o 16:32 
Gość Specjalny

Posty: 2628
Lokalizacja: Warszawa
Niech

a_n=\underbrace{20072007\ldots 2007}_{n}

Rozważmy 2008 liczb a_1, a_2, a_3, \ldots, a_{2008}. Jeśli któraś z liczb przystaje do 0\pmod{2008} to koniec. Wydaje mi się jednak, że żadna z nich nie przystaje do zera, ale to nie jest takie ważne. Można sobie to udowodnić jak ktoś chce. Jeśli żadna z liczb nie jest podzielna przez 2008, to z zasady szufladkowej Dirichleta są dwie takie liczby i,j \quad i>j, że

a_i \equiv a_j \pmod{2008}

Szukaną liczbą jest więc a_i - a_j.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podzielność przez 41  szprot_w_oleju  7
 Podzielność liczby przez 5 - zadanie 2  Wiesiek7  4
 Podzielność , Z cyfr 1,2,3,4 utworzono wszystkie możliwe  KoszmarnyKarolek  5
 Potęga podzielna przez 240  inkaust  2
 Podzielność przez 6 - zadanie 2  monikap7  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl