Przeskocz do treści

Delta mi!

Indukcja przyrodnicza

Tak zwana zasada indukcji przyrodniczej mówi: Gdy masz podejrzenie, że znalazłeś ogólny wzór, który działa dla każdej liczby naturalnej, to sprawdź go dla pierwszych paru wartości i dla jakiejś większej: jak wzór się zgadza, to zgadza się dla każdej liczby naturalnej...

Co, że to nie zawsze działa? No faktycznie, można podać bardzo proste zdania, które są prawdziwe tylko dla początkowych paru liczb, a potem przestają być prawdziwe. Najprostsze zdania to "twierdzenia" typu każda liczba naturalna |n jest mniejsza od miliona. Faktycznie, gdy sprawdzimy prawdziwość takiego zdania dla n = 1,2,3, dostajemy zdania prawdziwe. Nawet dla n = 100 jest to prawda. No ale - tu wszyscy się uśmiechamy - nawet małe dziecko wie, że w oczywisty sposób to stwierdzenie nie jest prawdziwe dla, na przykład, n = 1000001.

Jednak gdy wzór jest nieco bardziej zagmatwany, możemy dać się ponieść fałszywej intuicji, że skoro nieoczywisty fakt zaskakuje nas dla niewielkich wartości początkowych, to będzie tak zawsze. Różni matematycy ulegali takim mirażom. Jednym z nich był wielki Pierre de Fermat, który sądził, że liczby postaci 22n + 1 są pierwsze dla każdego n. Faktycznie, podstawiając |n = 0,1,2,3,4, dostajemy liczby 3, 5, 17, 257, 65 537 - wszystkie one są pierwsze. Jednak, co wykrył Euler nieco później, już piąta liczba Fermata równa  5 |22 +1 = 232 + 1 = 4294967297 może zostać przedstawiona w postaci iloczynu 641⋅67000417. Metoda, której użył Euler, bazowała na pewnym fakcie znanym też Fermatowi; historycy zastanawiają się, czemu Fermat tego nie zauważył. Podejrzewa się, że mógł po prostu pomylić się w obliczeniach.

Znalezienie rozkładu szóstej liczby Fermata, czyli |F6 = 18446744073709551617, było już poza zasięgiem uczonych niedysponujących komputerami, ale dziś wiadomo, że jest to liczba złożona i mniejszy z jej dwóch dzielników to 274 177. Za pomocą komputerów znaleziono również rozkłady liczb |F7,F8,F9,F10 i F11. Wiadomo też, że liczby Fermata o numerach od 12 do 30 są złożone. Co dalej - nie wiadomo, to znaczy nie wiadomo, czy są jakieś pierwsze liczby Fermata inne niż pięć początkowych i czy trzydziesta pierwsza lub któraś z dalszych liczb Fermata jest złożona.

obrazek

Podział koła n cięciwami

Podział koła n cięciwami

Jedną z metod odkrywania faktów o liczbach naturalnych jest obserwacja małych przypadków, postawienie hipotezy, zbadanie jej prawdziwości dla małych wartości, a następnie próba uogólnienia i, jeśli się da, udowodnienie - zazwyczaj przez indukcję - ogólnego wzoru. Spróbujmy zmierzyć się z takim oto zadaniem. Wybierzmy n punktów na brzegu koła i połączmy każdy z każdym. Na ile maksymalnie części dzielą koło wszystkie tak poprowadzone cięciwy? Widać, że aby nie zmarnować żadnego możliwego do uzyskania obszaru, wybrane punkty nie powinny być ułożone zbyt regularnie: żadne trzy cięciwy nie powinny się przecinać w tym samym punkcie. Zbadajmy parę początkowych wartości. Dla jednego punktu mamy 1 obszar - zero cięciw i całe koło. Dwa punkty tworzą jedną cięciwę i dwa obszary, trzy generują z cięciw trójkąt dzielący koło na 4 obszary. Cztery punkty dają nam 8 obszarów, pięć punktów 16 obszarów... No to już widzimy wzór: maksymalna liczba obszarów dla n punktów to po prostu |2n− 1. Sprawdzamy jeszcze dla n = 6 i bęc! Okazuje się, że nie da się wykroić 32 obszarów. Najwyżej 31.

Niestety nasz wzór jest błędny: nie uda się nam krok indukcyjny. Trzeba by pokazać, że nowy punkt zwiększa dwukrotnie liczbę obszarów, a dla większych n jest to niemożliwe. W rzeczywistości wzór na maksymalną liczbę obszarów to (n4) +(n2) + 1 albo, jak kto woli, |-1(n4 − 6n3 + 23n2 −18n + 24), 24 co przez przypadek dla pierwszych 5 wartości daje kolejne potęgi dwójki, ale potem już niekoniecznie (początkowe wartości to 1,2,4,8,16,31,57,99, 163,256, ...).

obrazek
obrazek

Teraz trochę bardziej zaawansowany przykład, ale robiący wrażenie. Wiąże się on z funkcją  f1(x) = sinc(x) (łac. sinus cardinalis), którą definiuje się następująco:

 ⎧⎪⎪sinx- dlax ≠ 0 sinc(x) = ⎪⎨ x ⎪⎪⎪1 dla x = 0. ⎩

Przyjrzyjmy się wykresowi tej funkcji. Widać, że z grubsza to, co jest nad osią ,OX przeważa nad tym, co jest pod nią. Innymi słowy, łączne pole między krzywą wykresu a osią OX nad tą osią jest większe od łącznego pola pod osią. Pola kolejnych fragmentów nad i pod osią dość szybko zanikają, a różnica sum tych pól dąży do pewnej wartości rzeczywistej. Jest to całka oznaczona  ∞ |p0 sinc(x)dx. Całka ta jest dość paskudna - funkcja |sinc nie ma elementarnej funkcji pierwotnej, ale można wyznaczyć wartość tej całki oznaczonej na całej dodatniej półosi. Jest ona równa dokładnie  π |2 .

Takie rzeczy się zdarzają. Jednak naprawdę ciekawie się robi, gdy nieco zmodyfikujemy funkcję podcałkową. Rozważmy funkcję | f3(x) = sinc(x) sinc(x3) . Jej wykres przypomina wykres funkcji |sinc(x), a całka |p∞ sinc(x) sinc(x )dx = π. 0 3 2 Rozważmy jeszcze funkcję  x x | f5(x) = sinc(x) sinc(3) sinc (5) . Jej całka na dodatniej półosi też wynosi dokładnie  π |2 .

Co dalej? Skoro tak dobrze nam idzie, to spróbujmy obliczyć całki z iloczynów kolejnych funkcji sinc z argumentami będącymi kolejnymi nieparzystymi ułamkami x. Zatem mamy

obrazek

No to już chyba nic złego się nie może stać. Tymczasem okazuje się, że

obrazek

wcale nie jest równe |12π , tylko  467807924713440738696537864469 |--------------------------------- π, 935615849440640907310521750000 co jest prawie dokładnie równe  1 |2 π, ale nie do końca. Ułamek, który stoi przed |π, ma w przybliżeniu wartość równą 0,499999999992646, więc różni się od 0,5 o niespełna jedną stumiliardową.

Nie muszę dodawać, że 13 jest ostatnią liczbą nieparzystą, dla której całka z iloczynu funkcji sinc z nieparzystymi mianownikami pod x jest dokładnie równa  π |2 . Potem ta cudowna własność zanika i dla każdej większej liczby nieparzystej całka ta już jest mniejsza od  π |2 . Co tu się dzieje?

Na ten fenomen wpadła dwójka matematyków kanadyjskich: David i Jonathan Borweinowie (ojciec i syn). W 2001 roku opublikowali pracę, która zszokowała wielu matematyków. Od tej pory całki omawianej postaci nazywane są całkami Borweinów (Borwein integrals). Jest sporo prac wyjaśniających przyczyny tej niezwykłej anomalii; żadna z nich nie odnosi się do pechowości liczby 13. W oryginalnej pracy autorzy piszą nawet, że podczas weryfikacji tego wyniku dla n = 15 sprawdzający go za pomocą komputera był przekonany o błędzie oprogramowania. Trudno się dziwić.

Najprościej można objaśnić moment załamania regularności, odnosząc się do transformat Fouriera i operatora konwolucji, co jednak wykracza poza zakres tego artykułu. Dla zainteresowanych polecam pracę H. Schmida Two curious integrals and a graphic proof. W skrócie, kluczową własnością trzynastki jest to, że jest to ostatnia nieparzysta liczba, dla której suma odwrotności kolejnych nieprzekraczających jej liczb nieparzystych (z pominięciem 1) nie przekracza jedynki. Po prostu |1-+ 1-+ 1+ -1+ -1+ -1 < 1, 3 5 7 9 11 13 ale po dodaniu |115 przekraczamy jedynkę. Co nam ta jedynka wadzi na drodze do uzyskania |π? 2 Tu niestety trzeba się odnieść do konwolucji - ja nie potrafię tego inaczej wytłumaczyć. Jednak za pomocą tego mechanizmu można się bawić w jeszcze bardziej szokujące wyniki. Na przykład całki

 ∞ x x x x x q sinc (--)sinc( ---)sinc(--- )sinc( ---)⋯ sinc( -------) dx 0 1 101 201 301 100n +1

będą równe |π2 tak długo, jak długo szereg ułamków  1 1 1 1 |---+ --- + ---+ ...+ -------- 101 201 301 100n + 1 nie przekroczy jedynki, a potem dla większych n już zawsze będą od  π |2 mniejsze. Dla jakiego |n to się stanie? Dla bardzo dużego. Naprawdę, bardzo. Chętnych zweryfikować ten rezultat własnoręcznie i sprawdzić, ile wyrazów tego szeregu czyni jego sumę większą od jedynki, śpieszę ostrzec, że na pewno prosta metoda polegająca na sumowaniu ułamków aż się minie jedynkę nie zadziała - po prostu nie doczekamy się wyników. Otóż najmniejszym n, dla którego ta całka będzie mniejsza od |π2 , jest |n = 15 341 178 777 673 149 429 167 740 440 969 249 338 310 889. Czyli początkowych |n− 1 całek będzie dokładnie równych  π |2 , a potem już żadna. No to teraz, zdolni informatycy, pytanie: jak można taką wartość tak dokładnie wyznaczyć? To samo w sobie jest bardzo ciekawym zadaniem. Więc nawet zachęcam tych, którzy mają dostęp do komputera i umieją programować, aby spróbowali wyznaczyć to graniczne |n. Ostrzegam: nie jest to proste zadanie.