Matematyczno - Informatyczne Imperium Wiedzy

Matematyczno - Informatyczne Imperium Wiedzy

Trzy perły teorii liczb

Twierdzenie Van Der Waerden′a o ciągu arytmetycznym

Latem 1928 roku, "tematem dnia " w Getyndze był wynik osiągnięty przez młodego matematyka holenderskiego vad der Weaerdena, o którym z entuzjazmem mówili wszyscy tamtejsi matematycy. Problem był następujący: Wyobraź sobie ,że zbiór wszystkich liczba naturalnych należy podzielić w jakikolwiek sposób na dwie części (np. na liczby parzyste i nieparzyste, liczby pierwsze i złożone, albo w jakiś inny sposób). Czy wtedy można stwierdzić ,że postęp arytmetyczny o dowolnej długości można znaleźć w co najmniej jednej z tych części? .Wszystkim , którym to pytanie zadano, potraktowali ten problem na pierwszy rzut oka jako dość prosty, a jego twierdzące rozwiązanie wydaje się być niemal oczywistym. Pierwsze próby rozwiązania go nie doprowadziły do niczego. I jak matematycy w Getyndze oraz ich zagraniczni goście mieli w tradycji stałą współpracę ze sobą , stał się on szybko obiektem powszechnego zainteresowania. Wszyscy się nim zajmowali, od czcigodnego uczonego do młodego studenta. Po kilku tygodniach uległ on atakowi młodego mężczyzny, który przybył do Getyngi aby studiować. Holender, van der Waerden. Było to rozwiązanie elementarne, ale nie proste. Problem okazał się głęboki, choć wygląd był zwodniczo prosty. Właściwie van der Waerden udowodnił więcej niż było wymagane. W pierwszej kolejności, założył że liczby naturalne są podzielne nie tylko na dwie, ale wiele, powiedzmy k, klas (zbiorów). Po drugie, okazało się ,że nie jest konieczne rozłożenie całej sekwencji liczb naturalnych w celu zagwarantowania istnienia postępu arytmetycznego określonej długości l i przynajmniej jednej z tych klas; pewien segment wystarczy do tego celu. Długość n(k,l) tego segmentu jest funkcją liczb k i l. Oczywiście nie ma znaczenia gdzie weźmiemy ten segment, tak dług jak n(k,l) są kolejnymi liczbami naturalnymi. Twierdzenie van der Waerdena można sformułować jak następuje:
Niech k i l będą dwoma dowolnymi liczbami naturalnymi. Wtedy istnieją liczby naturalne n(k,l) takie ,że jeśli dowolny segment, o długości n(k,l), ciąg liczb naturalnych jest podzielny w dowolny sposób na k klas (niektóre z nich mogą być puste), wtedy postęp arytmetyczny, wtedy postęp arytmetyczny długości l pojawia się co najmniej raz w tych klasach.
To twierdzenie jest prawdziwe trywialnie dla l = 2. Aby to zobaczyć , wystarczy ustawić n(k,2) = k+1; jeśli k+1 liczb jest podzielnych na k klas, wtedy z pewnością co najmniej jedna z tych klas zawiera więcej niż jedną liczbę, a dowolna para liczb formuje postęp arytmetyczny długości 2, co udowadnia to twierdzenie. Udowodnimy to twierdzenie przez indukcję na l. W konsekwencji, będziemy zakładać ,ze twierdzenie zostało zweryfikowane dla jakiejś liczby l ≤ 2 i dla dowolnej wartości k, i wykażemy ,że zachowuje swoją poprawność dla liczby l+1 (i naturalnie również dla wszystkich wartości k)
Zgodnie z naszym założeniem, dla każdej liczby naturalnej k istnieje liczba naturalna n(k,l) taką ,że jeśli dowolny segment, długości n(k,l), z liczb naturalnych, jest podzielny w dowolny sposób na k klas, istnieje w co najmniej w jednej z tych klas postęp arytmetyczny o długości l. Musimy wtedy udowodnić ,że dla każdej liczby naturalnej , również istniej n(k,l+1). Rozwiążemy ten problem przez zbudowanie liczby n(k,l+1). W tym celu ustawimy
q₀ = l, n₀=n(k,l)
a potem definiujemy liczby q₁, q₂, ., n₁, n₂ sukcesywnie jak następuje : Jeśli q_s-1 i n_s-1 zostały już zdefiniowane dla pewnego s > 0 wstawiamy
(1) q_s = 2ns-1q_s-1 , n_s = n(k^1_s, l) (s = 1,2,.) Liczby n_s, q_s są oczywiście zdefiniowane niniejszym dla dowolnego s ≥ 0. Teraz zakładamy, że dla n(k,l+1) możemy wziąć liczbę q_k. Musimy wykazać wtedy ,że jeśli segment, długości q_k, ciągu liczb naturalnych jest podzielny w dowolny sposób na k klas, wtedy istnieje postęp arytmetycznych długości l+1 w co najmniej jednej z tych klas. Dla skrócenia , możemy ustawić l+1 = l′

Trzy perły teorii liczb

APPENDIKSY