Matematyka dyskretna - ebook

WSTĘP

Τοῦ δὲ ποσοῦ τὸ μέν ἐστι διωρισμένον, τὸ δὲ συνεχες.

Ilość jest bądź rozdzielna, bądź ciągła.

– Arystoteles, Kategorie (ok. 350 p.n.e.)

Ten wprowadzający podręcznik traktuje o matematyce dyskretnej, którą informatycy powinni znać, ale z reguły nie uczą się jej na kursach rachunku różniczkowego czy algebry liniowej. Celem naszym jest raczej wiedza szeroka niż głęboka, zaś tak samo jak pojęć czy umiejętności chcemy uczyć odpowiedniego sposobu myślenia.

Podkreślamy wagę sztuki przeprowadzania dowodów w nadziei, że informatycy nauczą się myśleć formalnie i precyzyjnie. Niemal każda formuła i twierdzenie są tu w pełni udowodnione. Tekst ukazuje kumulatywną naturę matematyki. Na przekór szerokiemu zakresowi tematycznemu, wyniki pozornie między sobą niezwiązane w dalszych rozdziałach będą oparte na pojęciach poznanych wcześniej.

Tekst wymaga znajomości matematyki na poziomie wstępu do rachunku różniczkowego, niekiedy używamy też samego rachunku różniczkowego. W rozdziale 21 na temat notacji asymptotycznej używamy granic, ale umieściliśmy tam też krótkie podsumowanie wszystkich potrzebnych podstawowych faktów. Dowody i ćwiczenia wykorzystujące podstawową wiedzę z zakresu pochodnych i całek, w tym zasadę l’Hopitala, można pominąć, nie tracąc ciągłości.

Przyspieszony jednosemestralny kurs na Harvardzie omawia większość materiału zawartego w tej książce. Na taki kurs uczęszczają zazwyczaj studenci pierwszego i drugiego roku, gdyż stanowi on wstęp do kursów na temat teorii obliczeń (automaty, obliczalność, analiza algorytmów). Podręcznik nadaje się również do użytku w szkołach średnich, dla uczniów matematyki lub informatyki zainteresowanych tematami matematycznie dla nich dostępnymi, ale znajdującymi się poza utartym szlakiem programu szkolnego.

Książka napisana została jako seria krótkich rozdziałów, z których każdy mógłby być tematem jednej lub dwóch godzin zajęć. Każdy rozdział kończy się krótkim podsumowaniem i około dziesięcioma zadaniami. Można z nich korzystać na zasadach pracy domowej lub użyć ich jako ćwiczeń do wspólnego rozwiązywania w niewielkich grupkach.

Nauczyciele, którzy wolą nie omawiać wszystkich tematów tu zawartych, mogą skracać książkę na wiele sposobów. Główny nurt książki zawiera rozdziały 1–8 na temat podstawowych pojęć, rozdziały 13–18 na temat grafów skierowanych i nieskierowanych oraz rozdziały 21–25 na temat notacji asymptotycznej i zliczania. Cztery bloki rozdziałów są opcjonalne i mogą być niezależnie włączone lub wyłączone z omawiania według uznania nauczyciela:

• rozdziały 9–12 o logice,

• rozdziały 19–20 o automatach i językach formalnych,

• rozdziały 26–29 o prawdopodobieństwie dyskretnym oraz

• rozdziały 30–31 o arytmetyce modularnej oraz kryptografii.

Ponadto żaden z tych bloków, o ile w ogóle się je omawia, nie musi być przerobiony w całości, ponieważ tylko materiał z późniejszych rozdziałów opiera się na rozdziałach wcześniejszych z tego samego bloku.

Naszym celem było dostarczenie tekstu uniwersalnego w stylistyce, a przez to nadającego się do szerokiego użytku, nie tak ciężkiego jak encyklopedyczny podręcznik. Przez cały czas staraliśmy się uszanować zarówno chęć do nauki studentów, jak i ich ograniczone zasoby czasu, uwagi i pieniędzy.

*

Z podziękowaniami dla zespołu CS20, który tworzą: Deborah Abel, Ben Adlam, Paul Bamberg, Hannah Blumberg, Crystal Chang, Corinne Curcie, Michelle Danoff, Jack Dent, Ruth Fing, Michael Gelbart, Kirk Goff, Gabriel Goldberg, Paul Handorff, Roger Huang, Steve Komarov, Abiola Laniyonu, Nicholas Longenbaugh, Erin Masatsugu, Keenan Monks, Anupa Murali, Eela Nagaraj, Rebecca Nesson, Jenny Nitishinskaya, Sparsh Sah, Maria Stoica, Tom Silver, Francisco Trujillo, Nathaniel Ver Steeg, Helen Wu, Yifan Wu, Charles Zang i Ben Zheng.

dla Alberta Meyera za jego hojną pomoc w początkowych okresie CS20,

a także dla Micheala Sobina, Scotta Josepha, Alexa Silversteina i Noam Wolf za ich krytykę i wsparcie w czasie pisania.

Harry Lewis i Rachel ZaxROZDZIAŁ 1
ZASADA SZUFLADKOWA

Skąd wiemy, że program komputerowy generuje trafne wyniki? Skąd wiemy, że dany program zakończy swoje działanie? Jeśli wiemy, czy w końcu się zatrzyma, to czy możemy przewidzieć, czy stanie się to w ciągu sekundy, godziny czy dnia? Intuicja, testy i „działało całkiem dobrze za każdym razem, gdy próbowaliśmy” nie powinny uchodzić za dowód stwierdzenia. Udowodnienie czegokolwiek wymaga formalnej argumentacji, gdzie zaczynamy od zdań, o których wiemy, że są prawdziwe i łączymy poszczególne zdania za pomocą niepodważalnych wniosków logicznych. Oto książka o matematyce używanej do argumentacji na temat działania programów komputerowych.

Matematyka informatyki nie stanowi jakieś specjalnej, oddzielnej dziedziny. Informatycy korzystają z niemal wszystkich gałęzi matematyki, także takich, o których nikt nigdy nie myślał, iż okażą się przydatne, do momentu, gdy rozwój informatyki znalazł dla nich zastosowanie. Tak więc książka ta zawiera rozdziały traktujące między innymi o logice matematycznej, teorii grafów, zliczaniu, teorii liczb i teorii prawdopodobieństwa dyskretnego. Z punktu widzenia tradycyjnego programu nauczania matematyki, lista powyższa zawiera rzeczy wzajemnie nieporównywalne. Wspólną cechą tych tematów jest to, że znajdują one zastosowanie w informatyce. Co więcej, wszystkie wchodzą w skład matematyki dyskretnej, co oznacza, że dotyczą one wielkości zmieniających się skokowo, a nie w sposób ciągły. Są one wyrażane raczej w postaci symboli i struktur niż w postaci liczb. Oczywiście rachunek różniczkowy w informatyce również jest bardzo ważny, ponieważ wspomaga on rozważania na temat wielkości ciągłych. W tej książce jednak rzadko będziemy używać całek i pochodnych.

***

Jedną z najważniejszych umiejętności wykształcanych przez myślenie matematyczne jest sztuka uogólniania. Dla przykładu, zdanie

Nie istnieje trójkąt o bokach długości 1, 2 i 6

jest prawdziwe, ale bardzo szczegółowe (patrz rys. 1.1). Boki o długości 1 i 2 muszą łączyć się z bokiem o długości 6 na obu jego końcach, ale nie są one razem na tyle długie, by potem spotkać się jeszcze w trzecim wierzchołku.

Rysunek 1.1. Czy może istnieć trójkąt o bokach długości 1, 2 i 6?

Bardziej ogólnym stwierdzeniem mogłoby być (patrz rys. 1.2):

Rysunek 1.2. Nie istnieje trójkąt o bokach długości a, b, c jeśli a + b ≤ c

Nie istnieje trójkąt o bokach mających długości a, b, c, jeśli a, b i c są liczbami takimi, że a + b ≤ c.

Drugie sformułowanie jest bardziej ogólne, ponieważ możemy wywnioskować pierwsze z drugiego, podstawiając a = 1, b = 2 i c = 6. Dotyczy ono również przypadku niepokazanego na rysunku – gdy a + b = c, tak więc wszystkie trzy „wierzchołki” znajdują się na jednej prostej. Ogólna zasada ma wreszcie tę zaletę, że nie tylko mówi nam, co jest niemożliwe, lecz także dodatkowo to wyjaśnia. Nie istnieje trójkąt 1 – 2 – 6, ponieważ 1 + 2 ≤ 6.

Tak więc formułujemy stwierdzenia w formie ogólnej z dwóch powodów. Po pierwsze, bardziej ogólne stwierdzenie jest bardziej przydatne: możemy je z powodzeniem zastosować do większej liczby sytuacji. Po drugie, ogólne stwierdzenie ułatwia zrozumienie tego, o co naprawdę chodzi, ponieważ pozbawione jest nieistotnych, rozpraszających szczegółów.

***

Następnym przykładem niech będzie dość prosty scenariusz.

Anna, Batul, Czarek, Deja, Ewelina, Fawwaz, Grzegorz, Hoon rozmawiają ze sobą i dowiadują się, że zarówno Deja, jak i Grzegorz urodzili się we wtorek.

(1.1)

No i co z tego? Gdy weźmiemy dwie dowolne osoby, to mogą być one urodzone w tym samym dniu tygodnia lub nie. A jednak dzieje się tutaj coś, co można uogólnić. Gdy tylko mamy do czynienia z przynajmniej ośmioma ludźmi, pewna para spośród nich musi być urodzona w tym samym dniu tygodnia, ponieważ tydzień ma tylko siedem dni. Pewne zdania, takie jak (1.1), muszą być prawdziwe, być może z innymi imionami i innym dniem tygodnia. Tak więc mamy tu bardziej ogólne stwierdzenie.

W dowolnej grupie ośmiu osób jakaś dwójka z nich urodziła się w tym samym dniu tygodnia.

Nawet to jednak nie jest tak naprawdę ogólne. Ta zbieżność nie ma nic wspólnego z cechami ludzi albo dni tygodnia, z wyjątkiem tego, ile czego jest. Z tego samego powodu, jeśli postawimy osiem filiżanek na siedmiu talerzykach, pewien talerzyk będzie miał na sobie dwie filiżanki. W zasadzie nie ma też nic magicznego w „ósemce” i „siódemce” z wyjątkiem tego, że pierwsza jest większa od drugiej. Jeśli hotel ma 1000 pokoi i 1001 gości, to jeden pokój musi mieścić co najmniej dwoje gości. Jak możemy wyrazić ogólną zasadę obejmującą naraz wszystkie przypadki bez omawiania zbędnych szczegółów któregokolwiek z nich?

Na początek potrzebujemy nowych pojęć. Zbiór jest kolekcją rzeczy, czyli elementów. Elementy należące do danego zbioru nazywamy jego zawartością. Elementy tworzące zawartość zbioru muszą być odrębne, co jest tylko innym sposobem powiedzenia, że wszystkie muszą różnić się między sobą. Tak więc osoby wymienione w (1.1) tworzą zbiór, zaś dni tygodnia tworzą inny zbiór. Niekiedy wypisujemy zawartość danego zbioru w sposób bezpośredni, jako listę w nawiasach klamrowych {}:

L = {Anna, Batul, Czarek, Deja, Ewelina, Fawwaz, Grzegorz, Hoon}

D = {niedziela, poniedziałek, wtorek, środa, czwartek, piątek, sobota}

Kiedy wypisujemy elementy zbioru, kolejność ich zapisania nie ma znaczenia – w każdej innej kolejności tworzą one ten sam zbiór. Zapis x ∈ X oznacza, że element x należy do zbioru X. Na przykład Czarek ∈ L, zaś czwartek ∈ D.

Aby rozmawiać na temat zbiorów, potrzebujemy pewnej podstawowej terminologii dotyczącej liczb. Liczba całkowita to jedna z liczb 0, 1, 2, … albo –1, –2, … Liczby rzeczywiste to wszystkie liczby na osi liczbowej, włączając w to wszystkie liczby całkowite oraz wszystkie liczby pomiędzy nimi, takie jak ½, – √2 czy π. Dana liczba jest dodatnia, jeśli jest większa od 0, ujemna, jeśli jest mniejsza od 0 i nieujemna, jeśli jest większa lub równa 0.

Na razie będziemy mówić tylko o zbiorach skończonych. Zbiór skończony to taki, którego elementy mogą być (przynajmniej w założeniu) wymienione jeden po drugim. Zbiór skończony ma liczebność albo moc, która jest wyrażana przez liczbę całkowitą nieujemną. Moc zbioru X oznaczamy jako |X|. W przykładzie dotyczącym osób i dni tygodnia, w których się urodzili, |L| = 8, zaś |D| = 7, ponieważ wymieniliśmy osiem osób, a dni w tygodniu jest siedem. Zbiór, który nie jest skończony – na przykład zbiór liczb całkowitych – jest nieskończony. Zbiory nieskończone również mają swoje rozmiary – jest to ciekawy temat, do którego powrócimy w rozdziale 7.

Funkcją z jednego zbioru na drugi nazywamy regułę, według której każdemu elementowi pierwszego zbioru przyporządkowuje się dokładnie jeden element drugiego zbioru. Jeśli f jest funkcją z X na Y, zaś x ∈ X, to f(x) jest tym elementem Y, który f przyporządkowuje elementowi x. Mówimy o x jako o argumencie funkcji f, zaś f(x) nazywamy wartością f na tym argumencie. Zapis f: X → Y oznacza, że f jest funkcją ze zbioru X na zbiór Y. Można na przykład zapisać u: L → D jako oznaczenie funkcji przyporządkowującej każdemu z ośmiu przyjaciół dzień tygodnia, w którym został on urodzony. Jeśli Karol urodził się we wtorek, to u(Karol) = wtorek.

Funkcję f : X → Y nazywamy niekiedy odwzorowaniem zbioru X na Y, zaś o f mówimy, że odwzorowuje element x ∈ X na element f(x) ∈ Y (w podobny sposób jak prawdziwa mapa odwzorowuje punkt na powierzchni za pomocą punktu na kartce papieru).

Wreszcie mamy sposób na wyrażenie ogólnej reguły, jaka rządzi przykładem (1.1)

Jeśli f : X → Y oraz |X| > |Y|, to istnieją takie elementy x₁, x₂ ∈ X, że x1 ≠ x₂ i f(x₁) = f(x₂).

(1.2)

Twierdzenie (1.2) jest znane jako zasada szufladkowa, gdyż w formie matematycznej wyraża ten zdroworozsądkowy pomysł: jeśli mamy więcej rzeczy niż szufladek i każda rzecz idzie do pewnej szufladki, to któraś szufladka zawiera więcej niż jedną rzecz. Rzeczy są elementami zbioru X, zaś szufladki elementami zbioru Y (patrz rys. 1.3).

Rysunek 1.3. Zasada szufladkowa. Jeśli |X| > |Y|, zaś f jest dowolną funkcją z X na Y, to pewne dwa różne elementy X muszą mieć tę samą wartość funkcji f

Formalny dowód zasady szufladkowej podamy na stronie 39, gdy już wypracujemy odpowiednie narzędzia do przeprowadzania dowodów. Na razie przyjrzyjmy się bliżej powyższemu sformułowaniu zasady szufladkowej w celu lepszego zrozumienia języka matematyki. Oto niektóre z pytań, które moglibyśmy zadać:

1. Czym są X i Y?

Są zbiorami skończonymi. Aby wyrazić się całkowicie jasno, można by rozpocząć zdanie od frazy „Dla dowolnych zbiorów skończonych X i Y”, ale założenie, że f jest funkcją z X na Y ma sens tylko jeśli X i Y są zbiorami, zaś z kontekstu wiadomo, że zbiory, o których mowa, są skończone – i dzięki temu wiemy, jak porównywać ich rozmiary.

2. Dlaczego wybraliśmy „x₁” i „x₂” na nazwy elementów X?

Zasadniczo moglibyśmy wybrać dowolne nazwy zmiennych, „x” i „y” na przykład. Ale używanie wariantów oznaczenia „X” na nazwanie elementów zbioru X sugeruje, że x₁ i x₂ należą raczej do X niż do Y. Dzięki temu użycie „x₁” i „x₂” sprawia, że nasze zdanie łatwiej przeczytać i zrozumieć.

3. Czy wyrażenie „takie, że x₁ ≠ x₂” było konieczne? Zdanie jest prostsze bez tego i wydaje się, że mówiłoby dokładnie to samo.

Tak, „x₁ ≠ x₂” jest konieczne, i nie – zdanie nie mówi tego samego bez niego! Gdybyśmy nie powiedzieli „x₁ ≠ x₂”, wtedy „x₁” i „x₂” mogłyby być dwiema nazwami tego samego elementu. Gdybyśmy nie podkreślili, że x₁ i x₂ mają być różne od siebie, zdanie nie stałoby się przez to fałszywe – tylko trywialne! Oczywiście, jeśli x₁ = x₂, to f(x₁) = f(x₂). To jak mówić, że masa Ziemi jest równa masie trzeciej planety od Słońca. Innym sposobem wyrażenia zasady szufladkowej byłoby stwierdzenie, że „istnieją różne od siebie elementy x₁, x₂ ∈ X o własności takiej, że f(x₁) = f(x₂)”.

Jeszcze jedną rzecz warto tu podkreślić. Zdanie takie, jak „istnieją różne od siebie elementy x₁, x₂ ∈ X o własności takiej, że bla bla bla” nie oznacza, że istnieją dokładnie dwa elementy o takiej własności. Oznacza tylko, że przynajmniej dwa takie elementy istnieją na pewno – być może więcej, ale na pewno nie mniej.

***

Matematycy zawsze poszukują bardziej ogólnych postaci danej reguły, ponieważ wtedy może zostać ona użyta do wyjaśnienia większej liczby rzeczy. Jest na przykład równie oczywiste, że jeśli włożymy 15 rzeczy w 7 szufladek, to w którejś szufladce znajdą się przynajmniej 3 rzeczy – ale nie ma sposobu, by wywnioskować to z zasady szufladkowej w sformułowaniu, w jakim ją tu przedstawiliśmy. Oto bardziej ogólna jej wersja:

Twierdzenie 1.3. Rozszerzona zasada szufladkowa. Dla dowolnych skończonych zbiorów X i Y oraz dowolnej dodatniej liczby całkowitej k takich, że |X| > k · |Y|, jeśli f : X → Y, to istnieje przynajmniej k + 1 różnych elementów x₁, …, xk+1 ∈ X takich, że f(x₁) = … = f(xk+1).

Zasada szufladkowa jest szczególnym przypadkiem rozszerzonej zasady szufladkowej, dla którego k = 1.

Użyliśmy tu po raz pierwszy notacji na oznaczenie ciągu, wykorzystując tę samą zmienną z dolnymi indeksami liczbowymi zawartymi w danym przedziale. W tym przypadku xi, gdzie 1 ≤ i ≤ k + 1, tworzą ciąg o długości k + 1. Notacja ta jest bardzo wygodna, gdyż umożliwia użycie wyrażeń algebraicznych, takich jak k + 1, w indeksach. W podobny sposób do elementu o numerze 2i ciągu y₁, y₂, … możemy odnieść się poprzez oznaczenie y2i.

Minimalną wartość parametru k w rozszerzonej zasadzie szufladkowej zastosowanej do konkretnych zbiorów X i Y można określić, gdy rozmiary X i Y są znane. Aby to obliczenie było przeprowadzone w sposób precyzyjny, należy zastosować odpowiedni zapis.

Liczba całkowita p dzieli inną liczbę całkowitą q, co zapisujemy jako p | q, jeśli ułamek jest liczbą całkowitą – to znaczy można podzielić q przez p bez reszty. Jeśli p nie dzieli q, zapisujemy ten fakt następująco: p q, np. 3 7. Jeśli x jest dowolną liczbą rzeczywistą, zapis x oznacza największą liczbę całkowitą mniejszą lub równą x (nazywamy to cechą liczby x albo podłogą liczby x). Na przykład Potrzebujemy również notacji oznaczającej tzw. cechę górną: x, czyli sufit liczby x, jest najmniejszą liczbą całkowitą większą lub równą x, na przykład 3,7 = 4.

Z pomocą tej notacji możemy przeformułować rozszerzoną zasadę szufladkową w taki sposób, by określić minimalny rozmiar najbardziej wypełnionych szufladek dla danej liczby rzeczy i szufladek:

Twierdzenie 1.4. Rozszerzona zasada szufladkowa, wersja alternatywna. Niech X i Y będą dowolnymi skończonymi zbiorami i niech f : X → Y. Istnieje wtedy y ∈ Y taki, że f(x) = Y dla przynajmniej

wartości x.

Dowód. Niech m = |X| oraz n = |Y|. Jeśli n | m, to jest to przypadek rozszerzonej zasady szufladkowej dla k = m/n = 1 = – 1. Jeśli n m, to mamy znów do czynienia z zasadą szufladkową, gdzie k = – 1, ponieważ jest to największa liczba całkowita mniejsza od .■

***

Te wersje zasady szufladkowej podanej w ogólnej postaci wydają się być skomplikowanym sposobem wyrażenia rzeczy oczywistych. Używamy ich jednak do wyjaśnienia wielu różnorakich zjawisk – gdy tylko da się określić, co tym razem może być „szufladkami”, a co „rzeczami w szufladkach”. Zakończmy rozdział zastosowaniem w teorii liczb badającej własności liczb całkowitych. Na początek kilka podstawowych faktów.

Jeśli p | q, to p nazywamy dzielnikiem albo czynnikiem q.

Liczba pierwsza to dowolna liczba całkowita większa niż 1, która dzieli się tylko przez 1 i przez samą siebie. Na przykład 7 jest liczbą pierwszą, ponieważ dzieli się tylko przez 7 i 1, jednak 6 nie jest liczbą pierwszą, bo 6 = 2 · 3. Zauważmy, że 1 również nie jest liczbą pierwszą.

Twierdzenie 1.5. Podstawowe twierdzenie arytmetyki. Każdą liczbę całkowitą większą od 1 można w sposób jednoznaczny przedstawić w postaci iloczynu różnych pierwszych w porządku rosnącym i z wykładnikami całkowitymi dodatnimi.

Dowiedziemy tego twierdzenia w rozdziale 4, ale już teraz z niego skorzystamy. Rozkładem na czynniki pierwsze liczby n nazywamy jedyny taki iloczyn

gdzie pi są liczbami pierwszymi w porządku rosnącym, zaś ei są liczbami całkowitymi dodatnimi. Na przykład 180 = 2²·3²·5¹ i nie istnieje inny iloczyn równy 180, gdzie p₁ < p₂ < … < pk, wszystkie pi są liczbami pierwszymi, zaś ei są wykładnikami całkowitymi.

Rozkład na czynniki pierwsze iloczynu dwóch liczb całkowitych m i n łączy ze sobą rozkłady na czynniki pierwsze m i n – każdy czynnik pierwszy liczby m · n jest czynnikiem pierwszym jednej lub drugiej z tych liczb.

Twierdzenie 1.7. Jeśli m, n i p są liczbami całkowitymi większymi od 1, p jest liczbą pierwszą i p | m · n, to p | m, lub p | n.

Dowód. Na podstawie podstawowego twierdzenia arytmetyki (1.5) istnieje tylko jeden sposób zapisu

(1.6)

gdzie pi są liczbami pierwszymi. Ale p musi być jednym z pi, zaś każde z pi pojawia się w rozkładzie m lub n na czynniki pierwsze.■

Wykładnik liczby pierwszej p w rozkładzie na czynniki pierwsze m · n stanowi sumę wykładników z rozkładów m i n (przyjmując wykładnik 0, jeśli p nie pojawia się w danym rozkładzie). Dla przykładu rozważmy iloczyn 18 · 10 = 180. Mamy:

18 = 2¹ · 3² (wykładnikami liczb 2, 3, 5 są 1, 2, 0)

10 = 2¹ · 5¹ (wykładnikami liczb 2, 3, 5 są 1, 0, 1)

180 = 2² · 3² · 5¹

= 21+1 · 32+0 · 50+1

Pokolorowaliśmy wykładniki, by wyeksponować, że wykładniki liczb 2, 3, 5 w iloczynie 180 są sumami wykładników liczb pierwszych w rozkładach na czynniki pierwsze dwóch czynników 18 i 10.

Innym ważnym faktem na temat liczb pierwszych jest to, że jest ich nieskończenie wiele.

Twierdzenie 1.8. Istnieją dowolnie wielkie liczby pierwsze.

„Dowolnie wielkie” znaczy, że dla każdego n > 0 istnieje liczba pierwsza większa niż n.

Dowód. Przyjmijmy jakąś wartość k, o której wiemy, że istnieje przynajmniej k liczb pierwszych i niech p₁, …, pk będzie ciągiem k pierwszych liczb pierwszych w porządku rosnącym. (Ponieważ p₁ = 2, p₂ = 3, p₃ = 5, na pewno moglibyśmy przyjąć k = 3). Pokażemy, jak znaleźć liczbę pierwszą większą niż pk. A ponieważ ten proces można powtarzać w nieskończoność, musi istnieć nieskończenie wiele liczb pierwszych.

Rozważmy liczbę N równą zwiększonemu o 1 iloczynowi k początkowych liczb pierwszych:

(1.9)

Dzielenie N przez którąkolwiek z liczb p₁, …, pk dałoby resztę 1. Tak więc N nie ma dzielników pierwszych mniejszych lub równych pk. Zatem N nie jest liczbą pierwszą, ale ma czynnik pierwszy większy od pk albo N jest liczbą pierwszą.■

W przypadku gdy k = 3, N = 2 · 3 · 5 + 1 = 31. Tutaj samo N jest liczbą pierwszą, a w zadaniu 1.11 prosimy o wskazanie przykładu, w którym N nie jest liczbą pierwszą.

Wspólnym dzielnikiem dwóch liczb jest liczba, która dzieli obie z nich. Na przykład 21 i 36 mają wspólne dzielniki 1 i 3, ale 16 i 21 nie mają wspólnych dzielników większych niż 1.

Po przypomnieniu podstaw przyjrzyjmy się przykładowi z teorii liczb, w którym używa się zasady szufladkowej.

Przykład 1.10. Wybierzmy m różnych liczb między 2 a 40 włącznie, gdzie m ≥ 13. Wtedy przynajmniej dwie z liczb mają wspólny dzielnik większy niż 1.

„Między a i b włącznie” oznacza wszystkie liczby, które są ≥ a, a także ≤ b – a, zatem w tym przypadku, włączając zarówno 2, jak i 40.

Rozwiązanie do przykładu. Zauważmy, że istnieje 12 liczb pierwszych mniejszych lub równych 40: 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37 i żadne dwie spośród nich nie mają wspólnego czynnika większego niż 1. Zdefiniujmy P jako zbiór tych 12 liczb pierwszych. (Musieliśmy określić, że m ≥ 13, ponieważ w przeciwnym razie stwierdzenie byłoby fałszywe dla m = 12, a zbiór P byłby właśnie kontrprzykładem). Rozważmy teraz zbiór X zawierający m liczb w przedziale od 2 do 40 włącznie. Możemy wyobrazić sobie elementy zbioru P jako szufladki, do których wkładamy elementy zbioru X. Aby włożyć coś do szufladki, używamy funkcji f : X→ P, gdzie f(x) jest najmniejszą liczbą pierwszą, która dzieli x. Dla przykładu f(16) = 2, f(17) = 17, zaś f(21) = 3. Ponieważ m > 12, to na podstawie zasady szufladkowej, wartości f muszą być równe dla pewnych dwóch różnych elementów X, a zatem przynajmniej dwa elementy X mają wspólny czynnik pierwszy.■

Podsumowanie rozdziału

■ Rozumowanie matematyczne skupia się na zasadach ogólnych wyabstrahowanych z poszczególnych przykładów i pozbawionych szczegółów.

■ Zbiór jest nieuporządkowaną kolekcją odrębnych rzeczy albo elementów. Elementy danego zbioru tworzą jego zawartość.

■ Zbiór jest skończony, jeśli jego elementy mogą zostać wymienione jeden po drugim. Liczba elementów zbioru skończonego X nazywamy jego liczebnością lub mocą oznaczamy jako |X|. Liczebność zbioru jest zawsze nieujemną liczbą całkowitą.

■ Funkcją albo odwzorowaniem między dwoma zbiorami nazywamy regułę przyporządkowującą każdemu elementowi pierwszego zbioru jeden element drugiego.

■ Zasada szufladkowa głosi, że jeśli X jest zbiorem rzeczy, a Y jest zbiorem szufladek i |X| > |Y|, to każda funkcja przyporządkowująca rzeczy do szufladek wkłada do pewnej szufladki więcej niż jedną rzecz.

■ Rozszerzona zasada szufladkowa głosi, że jeśli X jest zbiorem rzeczy, a Y jest zbiorem szufladek i |X| > k|Y|, to każda funkcja przyporządkowująca rzeczy do szufladek wkłada do pewnej szufladki więcej niż k rzeczy.

■ Ciąg wyrażeń można zapisać jako powtarzającą się zmienną z różnymi indeksami numerycznymi, tak jak x₁, …, xn. Indeks danego wyrażenia może być wyrażeniem algebraicznym.

■ Podstawowe twierdzenie arytmetyki głosi, że każda liczba całkowita dodatnia ma dokładnie jeden rozkład na czynniki pierwsze.

Zadania

1.1. Co oznaczają następujące zapisy?

(a) |{0, 1, 2, 3, 4, 5, 6}|

(b)

(c)

(d) Zbiór dzielników liczby 100.

(e) Zbiór czynników pierwszych liczby 100

1.2. Niech f(n) będzie największym czynnikiem pierwszym liczby n. Czy może się zdarzyć, że x < y, ale f(x) > f(y)? Podaj przykład i wyjaśnij, dlaczego jest to możliwe.

1.3. W jakim przypadku x = x – 1?

1.4. Wyobraźmy sobie kwadrat 9 × 9 przegródek, w każdej z których siedzi jeden gołąb (Mamy więc 81 gołębi w 81 przegródkach – patrz rys. 1.4.) Przypuśćmy, że wszystkie gołębie naraz przemieszczają się do sąsiedniej przegródki – w górę, w dół, w lewo lub prawo. (Gołębie ze skrajnych przegródek nie mogą wyjść z kwadratu). Wykaż, że w pewnej przegródce znajdą się dwa gołębie. Podpowiedź: liczba 9 tylko tu rozprasza. Wypróbuj kilka mniejszych liczb, żeby zobaczyć, co się dzieje.

Rysunek 1.4. W środku każdej przegródki w kwadracie 9 × 9 siedzi jeden gołąb. Wszystkie naraz przemieszczają się o jedno miejsce od aktualnie zajmowanego – w lewo, w prawo, w górę lub w dół. Czy pewna przegródka musi na koniec zawierać dwa gołębie?

1.5. Wykaż, że w dowolnej grupie osób dwie z nich muszą mieć tę samą liczbę przyjaciół w grupie. (Musimy przyjąć tu pewne ważne założenia: nikt nie jest przyjacielem samego siebie, zaś przyjaźń jest symetryczna – jeśli A jest przyjacielem B, to B jest przyjacielem A.)

1.6. Dla danych pięciu dowolnych punktów na sferze wykaż, że cztery z nich muszą znajdować się na tej samej domkniętej półsferze, gdzie „domknięta” oznacza, że półsfera zawiera również ograniczający je okrąg. Wskazówka: Przez dowolne dwa punkty na sferze można przeprowadzić między nimi okrąg wielki, czyli największy okrąg na sferze.

1.7. Wykaż, że dla dowolnej grupy 25 osób trójka z nich musi mieć urodziny w tym samym miesiącu.

1.8. Mamy kolekcję monet o sześciu różnych nominałach: 1, 2, 5, 10, 20 i 50 groszy. Ile monet musi zawierać ta kolekcja, skoro wiemy, że przynajmniej 100 z nich ma ten sam nominał?

1.9. Dwadzieścia pięć osób uczęszcza codziennie na zajęcia jogi na ten samej siłowni, na której odbywa się osiem zajęć jogi dziennie. Każdy z uczestników nosi niebieską, czerwoną albo zieloną bluzkę w czasie ćwiczeń. Wykaż, że dowolnego dnia odbywa się przynajmniej jedna sesja jogi, podczas której dwie osoby noszą bluzki tego samego koloru.

1.10. Wykaż, że jeśli wybierzemy dowolne cztery liczby naturalne z przedziału od 1 do 60 włącznie, to dwie z nich muszą różnić się co najwyżej o 19.

1.11. Znajdź liczbę k o własności takiej, że iloczyn pierwszych k liczb pierwszych plus 1 nie jest liczbą pierwszą, ale ma czynnik pierwszy większy niż którakolwiek z k pierwszych liczb pierwszych. (Nie ma żadnego sprytnego triku pozwalającego na rozwiązanie tego zadania – trzeba po prostu wypróbować różne możliwości!)

1.12. Wykaż, że w dowolnym zbiorze 9 liczb całkowitych dodatnich dwie z nich mają wspólne wszystkie swoje czynniki pierwsze mniejsze lub równe 5.

1.13. Funkcja mieszająca (inaczej funkcja skrótów) prowadząca z łańcuchów tekstowych na liczby wyprowadza numeryczną wartość h(s) (skrót) z łańcuchu tekstowego s – na przykład poprzez dodanie wszystkich kodów numerycznych liter w danym łańcuchu i wzięcie reszty z dzielenia wyniku przez daną liczbę pierwszą p. Funkcja mieszająca powinna dawać powtarzalne wyniki (tzn. dwukrotne obliczenie h(s) z tego samego łańcucha s daje nam tę samą wartość) tak, by wyniki z dużym prawdopodobieństwem rozkładały się równo między możliwymi wartościami (od 0 do p – 1). Gdy funkcja mieszająca daje dwie takie same wartości dla dwóch różnych łańcuchów, mówimy wówczas, że oba te łańcuchy kolidują ze sobą na tej wartości. Liczymy liczbę kolizji na danej wartości w ten sposób, że jest ich o jeden mniej niż różnych łańcuchów z tą samą wartością funkcji mieszającej – czyli jeśli na przykład 2 łańcuchy mają tę samą wartość, to mamy 1 kolizję na tej wartości. Jeśli mamy m łańcuchów i p możliwych skrótów, to jaka jest minimalna liczba kolizji, które muszą zajść na wartości o największej liczbie kolizji? A jaka jest maksymalna liczba kolizji, które mogą zajść na niektórych wartościach?PRZYPISY

Stąd pochodzi określenie „mapowanie” (ang. mapping), które jest stosowane w informatyce do nazwania procesu polegającego na przyporządkowywaniu jednych zasobów danego systemu do drugich, mających najczęściej charakter wirtualny (przyp. red.).

W silniejszym sensie termin „konstruktywny” jest stosowany się w szkole matematyki konstruktywnej odrzucającej wszelkie dowody nieprowadzące do konstrukcji rzeczy, której istnienia próbuje się udowodnić. W matematyce konstruktywnej niedozwolone jest wnioskowanie z faktu, iż jedno zdanie jest fałszywe, że jego negacja jest z gruntu prawdziwa; prawdziwość negacji tego zdania trzeba zawsze udowodnić wprost. Matematyka konstruktywna zakazuje na przykład dowodzenia nie wprost (tj. poprzez reductio ad absurdum, co wyjaśniamy niżej) oraz argumentacji takiej jak w przypadku zadania 2.14. Informatycy preferują dowody, które same z siebie generują algorytmy, ale ogólnie rzecz biorąc, nie upierają się przy wyłącznie „konstruktywnych dowodach” w sensie ścisłym, w jakim by użył tego terminu matematyk konstruktywny. Na nasze potrzeby, aby wykazać, że jakieś zdanie jest prawdziwe, wystarczy wykazać, że jego negacja nie jest prawdą.

W tym miejscu po raz pierwszy używamy zmiennych takich jak „p” i „q” do reprezentacji zdań, tzn. stwierdzeń, które mogą być prawdziwe lub fałszywe. Rozdział 9 jest poświęcony obliczeniom przeprowadzanym na takich zmiennych zdaniowych, czyli tzw. rachunkowi zdań. Tutaj używamy zmiennych zdaniowych wyłącznie w celu ilustracji sposobów, na jakie można łączyć zdania składowe.

Jest to pierwszy i najprostszy wynik całego działu matematyki zwanego teorią Ramseya. Nazwano ją na cześć matematyka i filozofia Franka P. Ramseya (1903–1930), który jako pierwszy dowiódł tego twierdzenia podczas studiów nad problemem z logiki kwantyfikatorów.

Zdanie to znane jest pod nazwą hipotezy Goldbacha. Nie wiemy, czy jest prawdziwe, nie wiemy też, czy jest fałszywe.

W tym wzorze umieszczamy w nawiasie „(2i+1)”, bo nie byłoby jednoznaczne, czy suma odnosi się do całości wyrażenia, czy tylko do 2i. Wyrażenie to ma całkiem inną wartość niż

Nazwa bit pochodzi od angielskiego „BInary digiT” (cyfra dwójkowa), ale również od tego, że stanowi on malutką cząstkę (bit) informacji.

Nazwana na cześć norweskiego matematyka Axela Thue’ego (1863–1922). Ciąg ten nazywamy niekiedy również słowem Thue’ego–Morse’a lub słowem Thue’ego–Morse’a–Prouheta na cześć matematyka amerykańskiego Marstona Morse’a (1892–1977) oraz francuskiego Eugene Prouheta (1819–1867), który pośrednio użył tego ciągu już w 1851 roku.