Matematyka konkretna 1000 DPI.pdf

WydawnictwoNaukowePWN Ronald L. Graham, Donald E. Knuth Oren Patashnik Matematyka konkretna

Matematyka konkretna

Ronald L. Graham, Donald E. Knuth Oren Patashnik Matematyka konkretna Wydanie trzecie Zjęzyka angielskiego przełożyli P.Chrząstowski, A.Czumaj, L. Gąsieniec, M.Raczunas Wydawnictwo Naukowe PWN Warszawa 2001

Dane oryginału: Ronald L. Graham, AT&T Bell Laboratories D onald E. Knuth, Stanford University Oren Patashnik, Center for Communications Research Concrete Mathematics. A Foundation for Computer Science Copyright © 1994 by Addison-Wesley Publishing Company, Inc. First published by Addison-Wesley Publishing Company, One Jacob Way, Reading, Massachusetts, 01867 USA Okładka i strony tytułowe Bokiewicz &; Freudenreich Redaktor M ałgorzata K opczyńska Redaktor techniczny B eata Stelęgowska Copyright © for the Polish edition by Wydawnictwo Naukowe PWN Sp. z o.o. Warszawa 1996 Copyright © for the Polish edition by Wydawnictwo Naukowe PWN SA Warszawa 1998 ISBN 83-01-12124-6

Spis treści Przedm owa ..................................................................................................... 7 N otacja ............................................................................................................... 13 1. Problem y rekurencyjne ...................................................................... 15 1.1.Wieże z Hanoi ....................................................................................... 15 1.2. Proste na płaszczyźnie ........................................................................ 19 1.3. Problem Józefa Flawiusza ................................................................... 23 Ćwiczenia ................................................................................................... 32 2 . Sumy .............................................................................................................. 37 2 .1. Notacja .................................................................................................... 37 2 .2 . Sumy i rekurencje ............................................................................... 41 2.3. Przekształcenia sum ............................................................................ 46 2.4. Sumy wielokrotne ............................................................................... 51 2.5. Metody ogólne ....................................................................................... 59 2.6. Rachunek różnicowy i różniczkowy .................................................. 65 2.7. Sumy nieskończone .............................................................................. 75 Ćwiczenia ................................................................................................... 81 3. Funkfcje całkowitoliczbowe ................................................................ 87 3.1. Funkcje podłoga i sufit ...................................................................... 87 3.2. Użycie funkcji podłoga i sufit ........................................................... 90 3.3. Rekurencje z podłogą i sufitem .......................................................100 3.4. Działanie dwuargumentowe ‘mod’ .....................................................103 3.5. Sumy podłogi i sufitu ...........................................................................108 Ćwiczenia ....................................................................................................117 4. Teoria liczb ..................................................................................................124 4.1. Podzielność ..............................................................................................124 4.2. Liczby pierwsze ...................................................................................... 128 4.3. Pierwsze przykłady ...............................................................................130 4.4. Współczynniki rozkładu silni .......................................................... 135 4.5. Liczby względnie pierwsze ................................................................139 4.6. Relacja kongruencji ‘mod’ ................................................................148 4.7. Niezależne reszty ................................................................................... 151 4.8. Dalsze zastosowania ........................................................................... 154 4.9. Fi oraz mi ................................................................................................158 Ćwiczenia ....................................................................................................171

5. W spółczynniki dwum ianowe ............................................................. 180 5.1. Podstawowe tożsamości ........................................................................180 5.2. Podstawowe ćwiczenia, ..........................................................................201 5.3. Podstawowe techniki ............................................................................. 215 5.4. Funkcje tworzące ................................................................................... 226 5.5. Funkcje hipergeometryczne ................................................................ 234 5.6. Przekształcenia hipergeometryczne ...................................................247 5.7. Częściowe sumy hipergeometryczne ................................................. 253 5.8. Sumowanie mechaniczne ......................................................................260 Ćwiczenia ....................................................................................................273 6 . Liczby szczególne ....................................................................................288 6.1. Liczby Stirlinga ...................................................................................... 288 6.2.Liczby Eulera .......................................................................................... 299 6.3. Liczby harmoniczne :............. ............................................................... 304 6.4. Sumowanie harmoniczne ......................................................................311 6.5. Liczby Bernoulliego ...............................................................................316 6.6. Liczby Fibonacciego ..............................................................................324 6.7. Kontynuanty ...........................................................................................336 Ćwiczenia ....................................................................................................345 7. Funkcje tworzące ..................................................................................... 356 7.1. Teoria domina i rozmieniania .............................................................356 7.2. Podstawowe techniki .............................................................................368 7.3. Rozwiązywanie rekurencji ....................................................................374 7.4. Szczególne funkcje tworzące ................................................................389 7.5. Sploty ........................................................................................................392 7.6. Wykładnicze funkcje tworzące ...........................................................404 7.7. Funkcje tworzące Dirichleta ................................................................410 Ćwiczenia ....................................................................................................412 8 . Prawdopodobieństwo dyskretne ......................................................423 8.1. Definicje ................................................................................................... 423 8.2.Wartość oczekiwana i wariancja ........................................................ 429 8.3. Funkcje tworzące prawdopodobieństwa ........................................... 437 8.4. Rzucanie monetą ...................................................................................444 8.5. Haszowanie ..............................................................................................455 Ćwiczenia ....................................................................................................472 9. Asym ptotyka ............................................................................................. 485 9.1. Hierarchia ................................................................................................486 9.2. Notacja O ................................................................................................489 9.3. Przekształcenia typu O ........................................................................497 9.4. Dwie sztuczki asymptotyczne .............................................................512 9.5. Wzór sumacyjny Eulera ...................................................................... 518 9.6.Końcowe sumowania .............................................................................525 Ćwiczenia ....................................................................................................540 A. Odpowiedzi do ćwiczeń ........................................................................ 547 B. Bibliografia .................................................................................................672 C. Źródła ćwiczeń ..........................................................................................694 Skorowidz .......................................................................................... ...............700 W ykaz ta b e l.................................................................................................... 718

Przedmowa Książka ta powstała na podstawie wykładu o tej samej nazwie prowadzonego na Uniwersytecie Stanforda od 1970 r. Zazwyczaj przedmiot ten wybierało około 50 studentów, głównie magistrantów i doktorantów, choć zdarzali się również studenci starszych i młodszych lat. Ci, którzy zaliczyli ten przedmiot, zaczęli prowadzić podobne wykłady na innych uczelniach. Wygląda na to, że nadszedł czas, kiedy powinno się zaprezentować materiał wykładu szerszej publiczności (włączając w to studentów pierwszego roku). Matematyka konkretna powstała w czasie burzliwej dekady. Zaczęto kwe­ stionować wtedy nie podważane do tej pory wartości, przy czym kolebkę niepokojów stanowiły uniwersytety. Rewidowano programy studiów uniwer­ syteckich, i matematyka nie uniknęła znalezienia się pod lupą. John Ham- mersley napisał wtedy prowokujący artykuł „O osłabieniu umiejętności ma­ tematycznych przez ‘Matematykę Współczesną’ i przez jej podobne papki in­ telektualne serwowane w szkołach i na uniwersytetach” [176]. Inni przerażeni matematycy [333] pytali wręcz „Czy można uratować matematykę?” Jeden z autorów tej książki (DEK) wplątał się w pisanie serii książek pod tytułem The Art of Computer Programming (Sztuka programowania komputerów) i w trakcie przygotowywania pierwszego tomu zorientował się, że brakuje mu narzędzi matematycznych. Te, których potrzebował w celu gruntownego zrozumienia programów komputerowych, różniły się znacznie od tych, które poznał w czasie, kiedy odbywał klasyczne studia matematyczne. Wprowa­ dził więc nowy przedmiot, aby uczyć tego, czego jemu samemu brakowało w czasie jego studiów. Tytuł wykładu „Matematyka Konkretna” miał początkowo stanowić an­ tidotum na coś, co się wtedy nazywało „Matematyka Abstrakcyjna”, jako że ta druga na fali mody nazwanej „Nową Matematyką” została wyprana nagle ze wszystkich konkretnych wyników stanowiących rdzeń matematycznej kla­ syki. Matematyka abstrakcyjna jest wspaniałym przedmiotem i nie ma w niej niczego złego: jest piękna, ogólna i użyteczna. Niestety, jej promotorzy doszli do wniosku, że cała reszta matematyki jest nic nie warta. Uogólnianie stało się tak modne, że całe pokolenie matematyków nie było w stanie docenić piękna „Czytelnik, poziom przedstawienia — tego typu rzeczy powinny znaleźć się w przedmowie.” P. R. Halmos [173] „Ludzie używający odpowiedniego żargonu dość szybko zdobywają powierzchowny autorytet: mogą wygłaszać górnolotne, a pozbawione wartości opinie. Liczy się jednak nie umiejętność mielenia jęzorem, ani nawet brylowania znajomością aktualnego stanu wiedzy matematycznej, lecz raczej zdolność wykorzystania tego, czego się nauczyło i zastosowania posiadanej wiedzy do rozwiązywania praktycznych problemów matematycznych. W skrócie chodzi nam nie o słowa, a o czyny.” J. Hammersley [176]

[W tym miejscu i wielokrotnie później autorzy bawią się nieprzetłumaczalną grą słów. Słowo „concrete” po angielsku oznacza również beton. Tłumacze] „ Jest to z gruntu niesłuszne, aby uczyć abstrakcji przed konkretem.” Z. A. Melzak [267] „Rdzeń matematyki stanowią konkretne przykłady i konkretne problemy.” RR.Halmos [172] [Znowu nieprzetłumaczalna gra słów. „Ciągły” po angielsku, to continuous, a „ dyskretny’, to discrete, co daje po zlepieniu co n cre te — konkretny.] Matematyka konkretna jest pomostem do matematyki abstrakcyjnej. przypadków szczególnych, ani podjąć wyzwania rozwiązywania konkretnych problemów ilościowych, czy nawet dostrzec wartość w tym, że ktoś posiada sprawność rachunkową. Upojona sukcesami matematyka abstrakcyjna zaczęła tracić kontakt z rzeczywistością. Potrzeba było konkretnej przeciwwagi, aby przywrócić wykształceniu matematycznemu zdrową równowagę. Wykładając po raz pierwszy Matematykę Konkretną na Uniwersytecie Stanforda, DEK wyjaśniał ten cokolwiek dziwny tytuł wykładu mówiąc, że jest to próba przedstawienia matematycznego wykładu kursowego w sposób twardy, a nie miękki. Zapowiedział, że wbrew oczekiwaniom niektórych jego kolegów nie zamierza uczyć teorii wiązek, ani twierdzenia Stone’a o wło­ żeniu, ani nawet uzwarcenia Stone’a-Ćecha. (Kilku studentów z wydziału inżynieryjnego wstało i po cichu opuściło salę) Choć Matematyka Konkretna powstała w reakcji na inne trendy, rzeczy­ wiste przyczyny jej powstania były pozytywne, a nie negatywne. W miarę, jak wykład ten stawał się w trakcie studiów popularnym przedmiotem, jego treść „utwardzając się” okazywała się użyteczna w wielu nowych zastosowaniach. Tymczasem nadeszło nowe potwierdzenie trafności nazwy tej dziedziny, gdy Z. A. Melzak opublikował dwuczęściową książkę pod tytułem Companion to Concrete Mathematics [267]. Materiał matematyki konkretnej zdaje się na pierwszy rzut oka być wor­ kiem przypadkowych chwytów, jednak praktykowanie ich przetwarza go w zorganizowany warsztat z gotowymi narzędziami. W rzeczywistości przed­ stawione w tej książce techniki charakteryzują się pewną jednorodnością i na wielu wywierają duże wrażenie. Kiedy inny z autorów (RLG) po raz pierwszy prowadził ten przedmiot w 1979 r., studentom tak się wykład spodobał, że wielu z nich zobaczył jeszcze raz rok później. Czym dokładnie jest Matematyka Konkretna? Jest to mieszanina ma­ tematyki ciągłej i dyskretnej. Konkretniej, w jej zakres wchodzi usyste­ matyzowane przetwarzanie wzorów matematycznych oparte na zestawie od­ powiednich technik rozwiązywania problemów. Gdy opanujesz, Czytelniku, materiał zawarty w tej książce, wówczas wszystko, czego będziesz potrzebo­ wał, to niezmącony umysł, trochę papieru i całkiem niemało pisania, aby wyliczać wartości jakichś horrendalnie wyglądających sum, rozwiązywać zło­ żone relacje rekurencyjne i odkrywać subtelne wzorce w danych. Będziesz na tyle biegły w stosowaniu technik algebraicznych, że często będziesz wolał znajdywać wartości dokładne, niż ich oszacowania. Podstawowe zagadnienia ujęte w tej książce zawierają sumy, rekuren- cje, elementarną teorię liczb, współczynniki dwumianowe, funkcje tworzące, prawdopodobieństwo dyskretne i metody asymptotyczne. Główny nacisk jest położony nawet nie na twierdzenia egzystencjalne, czy myślenie kombinato- ryczne, a na techniki rachunkowe. Celem książki jest bowiem zaznajomienie

czytelnika z działaniami dyskretnymi (takimi jak część całkowita, czy sumo­ wanie skończone) w podobnym stopniu, w jakim studiujący analizę matema­ tyczną zapoznają się z działaniami ciągłymi (takimi jak wartość bezwzględna czy całkowanie). Warto zauważyć, że przedstawiona lista zagadnień różni się zasadniczo od tego, co zwyczajowo jest wykładane pod nazwą „Matematyki Dyskretnej”. Potrzebujemy więc odrębnej nazwy, a „Matematyka Konkretna” okazała się nazwą równie wygodną, jak pozostałe powszechnie używane dla określenia innych dziedzin. Początkowo podręcznikiem do stanfordzkiego wykładu był rozdział „Ma- thematical Preliminaries” z książki The A rt of Computer Programming [207]. Materiał zawarty na 110 stronach tego rozdziału był jednak zbyt zwięzły, więc trzeci z autorów (OP) wpadł na pomysł opracowania notatek uzupełniają­ cych, które przyjęły całkiem spore rozmiary. Książka ta stanowi rozwinięcie tych notatek. Jest to więc uzupełnienie wspomnianego rozdziału i bardziej przystępne wprowadzenie do materiału w nim zawartego. Niektóre znajdu­ jące się tam zbyt zaawansowane części pominięto w tej książce, inne z kolei zagadnienia dodano dla pełności wywodu. Autorzy mieli dużo satysfakcji przy tworzeniu tej książki, gdyż jej te­ mat krzepł przed ich oczyma i zaczynał żyć swoim własnym życiem; w czasie pracy nad nią książka ta zdawała pisać się sama. Co więcej, przyjęte przez nas dość niekonwencjonalne metody przedstawienia materiału tak dobrze za­ częły do siebie pasować, że — po latach doświadczeń— nie możemy oprzeć się wrażeniu, że książka ta jest rodzajem manifestu na temat tego, w jaki sposób powinno się uprawiać matematykę. Z naszego punktu widzenia książka ta jest bajką o matematycznym pięknie i przypadku. Mamy nadzieję, że czytelnicy podzielą z nami choć e tej przyjemności, którą mieliśmy w trakcie tworzenia tej książki. Książka ta powstała w środowisku uniwersyteckim, staraliśmy się więc oddać ducha współcześnie prowadzonych zajęć za pomocą nieformalnego stylu prezentacji materiału. Niektórzy uważają, że matematyka to przedsię­ wzięcie poważne i że musi w związku z tym być zimna i sucha. My jednak sądzimy, że matematyka jest zabawą i nie wstydzimy się tego ujawnić. W imię czego mielibyśmy oddzielać grubą kreską pracę od zabawy? Matematyka konkretna jest pełna pociągających wzorców; przekształcenia nie zawsze są łatwe, ale uzyskiwane odpowiedzi bywają zaskakująco atrakcyjne. Radości i smutki naszej matematycznej pracy są oddane tu wprost, gdyż są częścią naszego życia. Studenci zawsze wiedzą lepiej od swoich nauczycieli, więc poprosiliśmy kilku z nich o wyrażenie szczerych opinii w postaci „graffiti” na margine­ sach. Niektóre z nich są banalne, inne głębokie, niektóre ostrzegają o niejed­ „Czytelnik zaawansowany przeskakując części, które wydają mu się zbyt elementarne, często traci więcej, niż czytelnik początkujący, przeskakujący części, które wydają się mu zbyt złożone” . G. Pólya [298] „ . .. betonowa kamizelka ratunkowa rzucona studentom tonącym w morzu abstrakcji.” W. Gottschalk [Zobaczcie, ile jest w tej książce Deńnicji, Lematów, Twierdzeń...]

Graffiti matematyczne: Uwolnić grupę! Domknąć pierścień! Zbadać przestrzeń nad ciałem. N = 1 => P = N P . Szczerze mówiąc, mało mnie to interesuje. To był najfajniejszy wykład, na jaki kiedykolwiek chodziłem. Ale dobrze jest czasami podsumowywać przerobiony materiał. Rozumiem, matematyka konkretna, to po prostu zaćwiczanie. Ćwiczenia domowe były trudne, ale dały mi dużo. Każda godzina się opłaciła. Domowe zadania egzaminacyjne są niezbędne— tak trzymać! Egzaminy były trudniejsze niż to, czego się spodziewałem po ćwiczeniach domowych. noznacznościach i niezręcznościach, inne są typowymi komentarzami czynio­ nymi przez zdolnych gości z ostatnich rzędów; niektóre są pozytywne, inne są negatywne, a jeszcze inne są zerowe. Wszystkie jednak wynikły z prawdzi­ wych odczuć powstałych w trakcie czytania, co powinno ułatwić przyswoje­ nie tego materiału. (Pomysł ubarwienia tekstu książki takimi komentarzami pochodzi z podręcznika dla studentów Wstępując na Stanford, w którym ofi­ cjalne teksty są kontrowane przez komentarze studentów kończących studia. Na przykład Stanford pisze: „Jest parę rzeczy, których nie możesz nie za­ uważyć w tym amorficznym tworze, jaki stanowi Stanford”, a na marginesie czytamy: „Amorficzny ... o co tu, kurczę, chodzi? Typowy pseudointelek- tualizm panoszący się tutaj”. Stanford: „Nie ma granic dla potencjału, jaki stanowi grupa wspólnie żyjących studentów.” Graffito: „Akademiki Stan­ forda to coś w rodzaju ZOO bez dozorcy.”) Na marginesach pojawią się także dokładne cytaty z prac znanych ma­ tematyków minionych pokoleń, przytaczające oryginalne słowa, których uży­ wali ^anonsując niektóre z ich fundamentalnych odkryć. Niemniej jednak, uznaliśmy za właściwe przemieszać nazwiska takie jak Leibniz, Euler czy Gauss z nazwiskami tych, którzy po nich kontynuowali pracę. Matematyka jest ciągłym wyzwaniem dla ludzi na całym świecie. Ta bogata tkanina utkana jest z wielu wątków. Książka ta zawiera ponad 500 ćwiczeń podzielonych na sześć kategorii: • Rozgrzewkę stanowią ćwiczenia, które w s z y s c y c z y t e ln ic y powinni spróbować rozwiązać przy pierwszym czytaniu. • Podstawy, to ćwiczenia, które pozwalają wprowadzić fakty najłatwiej przyswajalne za pomocą próby ich samodzielnego odkrycia. • Ćwiczenia dom owe, to zadania mające pogłębić zrozumienie przero­ bionego w danym rozdziale materiału. • Zadania egzam inacyjne zazwyczaj dotyczą materiału z dwóch lub więcej rozdziałów. Stanowiły one najczęściej domowe zadania zalicze­ niowe, a nie zadania do rozwiązania w czasie egzaminu tradycyjnego, przeprowadzanego we wspólnej sali pod presją czasu. • Ćwiczenia dodatkowe wykraczają poza materiał, który przewidziany został dla średniego studenta uczącego się matematyki konkretnej według tej książki. Rozszerzają one materiał w różnych ciekawych kierunkach. • Problem y badawcze dadzą się, albo się nie dadzą rozwiązać przez czło­ wieka, ale te, które tu proponujemy są warte zastanowienia się i próby podejścia do rozwiązania (nie pod presją czasu). Odpowiedzi do wszystkich ćwiczeń są w Dodatku A, często z informacją o po­ wiązanych z nimi wynikach. (Oczywiście „odpowiedzi” na problemy badaw­ cze są niepełne, jednakże nawet w takich przypadkach podajemy wskazówki

L ł ł Z Przedmowa lub wyniki częściowe, które mogą być użyteczne przy rozwiązywaniu tych pro­ blemów). Zachęcamy Czytelników do zaglądania do odpowiedzi, szczególnie do odpowiedzi do zadań rozgrzewkowych, ale tylko p o dokonaniu rzetelnej próby rozwiązania danego zadania bez podglądania. W Dodatku C próbowaliśmy dla każdego ćwiczenia określić źródła, gdyż uważamy, że wymyślenie dobrego zadania wymaga często ogromnego nakładu energii i (lub) szczęścia. Niestety matematycy wprowadzili zwyczaj zapoży­ czania ćwiczeń bez cytowania źródeł. Uważamy, że przeciwna taktyka, zacho­ wywana np. w książkach i czasopismach szachowych (gdzie zwykle podaje się nazwiska twórców, daty i miejsca pierwszych publikacji cytowanych zadań szachowych) jest znacznie lepsza. Nie udało się nam jednak zlokalizować źró­ deł wielu zadań, które stały się częścią folkloru matematycznego. Będziemy wdzięczni za wskazanie każdego nie znanego nam lub niedokładnie podanego źródła któregokolwiek z przedstawionych ćwiczeń lub zadań. Chcielibyśmy poznać jak najwięcej szczegółów i poprawić niedoróbki w następnych wyda­ niach tej książki. Matematyczne czcionki, których używamy w tej książce, zostały zapro­ jektowane przez Hermanna Zapfa [227] na zlecenie AMS (American Mathe- matical Society— Amerykańskiego Towarzystwa Matematycznego) i opraco­ wane przez komitet, w skład którego wchodzili: B. Beeton, R. P. Boas, L. K. Durst, D.E. Knuth, P. Murdock, R. S. Palais, P. Renz, E. Swanson, S.B. Whidden, i W. B. Woolf. Pomysłem, który legł u podstaw projektu Zapfa, było uchwycenie stylu, jakim mógłby się posługiwać matematyk dysponujący przepięknym charakterem pisma. Pismo ręczne ma tę przewagę nad mecha­ nicznym, że matematycy zwykle pracują z długopisem, ołówkiem lub kredą. (Jednym z przykładów rozwiązań tego projektu jest znak zero, ‘0’, który jest lekko zaostrzony na górze, ponieważ rzadko kiedy pisząc zero udaje się je precyzyjnie zaokrąglić domykając na górze.) Symbole są pisane pionowo, a nie kursywą, tak więc indeksy i akcenty układają się bardziej naturalnie. Ta nowa rodzina czcionek została nazwana AMS Euler, na cześć wielkiego matematyka szwajcarskiego Leonharda Eulera (1707-1783), który tak dużo odkrył w matematyce, którą się dziś posługujemy. Pośród czcionek można wyodrębnić takie zbiory, jak Euler Text (AaBbCc aż do X xYyZz), Euler Fraktur (21a £c aż do 2}t) 33) i Euler Script Capitals (A ¥>6 aż do X y Z), jak również Euler Greek (AaB|3 Ty aż do XxAł/4,^ a>) i symbole szczególne takie jak jp lub K. Szczególnie cieszy nas to, że możemy zainaugurować ro­ dzinę czcionek Eulera w tej właśnie książce, ponieważ duch Eulera przenika tu każdą stronę: Matematyka konkretna jest matematyką eulerowską. Autorzy są szczególnie wdzięczni Andreiowi Broderowi, Ernstowi May- rowi, Andrew Yao i Frances Yao, którzy mieli znaczny wpływ na tę książkę w latach, gdy wykładali Matematykę Dyskretną na Stanfordzie. Ponadto kieru- Ci, którzy będą oszukiwali, mogą zaliczyć ten materiał przepisując odpowiedzi, ale oszukają tylko siebie samych. mmm-

Przypadkowemu studentowi zaleciłbym trzymanie się z dala od tego wykładu. Nie widzę, jak to, czego się do tej pory nauczyłem, mogłoby mi w czymkolwiek pomóc. Miałem sporo kłopotów z tym przedmiotem, ale wiem, że wyostrzył moją sprawność matematyczną i umysłową. [Uwaga o błędach typograficznych odnosi się niestety tylko do angielskiego oryginału.] jemy 1024 podziękowania tym asystentom, którzy twórczo przetworzyli to, co działo się w czasie ćwiczeń w latach, kiedy je prowadzili i którzy poma­ gali w opracowywaniu zadań egzaminacyjnych. Ich lista zamieszczona jest w dodatku C. Książka ta, która w dużej części wyrosła z prowadzonych przez nich w ciągu 16 lat notatek, byłaby nie powstała bez ich wspaniałej pracy. Wiele innych osób przyczyniło się do tego, że książka ta ujrzała światło dzienne. Chcielibyśmy dla przykładu odnotować wkład studentów Uniwer­ sytetów Browna, Columbia, CUNY, Princeton, Rice i Stanforda, którzy do­ pomogli w wyborze graffiti i w poprawianiu pierwszych maszynopisów. Kon­ takty z wydawnictwem Addison-Wesley były bardzo pomocne i efektywne. W szczególności chcielibyśmy wyrazić naszą wdzięczność wydawcy — Peterowi Gordonowi, redaktorowi technicznemu— pani Bette Aaronson, projektan­ towi— Royowi Brownowi i redaktorowi— Lynowi Dupre. National Science Foundation i Office of Naval Research wspomogły nas nieocenionymi gran­ tami. Cheryl Graham była niezwykle pomocna przy opracowywaniu skoro­ widza. Przede wszystkim jednak chcielibyśmy podziękować naszym żonom (Jill, Fan i Amy) za ich cierpliwość, pomoc, zachęty i pomysły. Obecne, drugie wydanie tej książki, zawiera nowy rozdział 5.8, który przedstawia pewne ważne pomysły odkryte przez Dorona Zeilbergera krótko po tym, jak pierwsze wydanie poszło do druku. Prawie na każdej stronie tego wydania można znaleźć poprawki w stosunku do wydania pierwszego. Próbowaliśmy stworzyć książkę bezbłędną, ale jesteśmy autorami omyl­ nymi. Apelujemy więc gorąco o poprawianie wszelkich błędów przez nas po­ czynionych. Wyznaczamy nagrodę w wysokości 2,56 dolara, którą wypłacimy z wdzięcznością każdemu pierwszemu odkrywcy jakiegokolwiek błędu mate­ matycznego, historycznego lub typograficznego. Murray Hill, New Jersey — RLG i Stanford, Kalifornia DEK maj 1988 i październik 1993 OP

Notacja Niektóre^pomysły notacyjne użyte w tej książce nie stały się (jeszcze ?) stan­ dardem. Poniżej przedstawiamy listę tych symboli, które mogą być nie znane czytelnikom, czytającym o podobnych rzeczach w innych książkach. Obok podajemy numery stron, na których pojawiają się ich objaśnienia. W celu uzyskania odnośników do innych, częściej spotykanych oznaczeń, zajrzyj też do skorowidza na końcu książki. Oznaczenie Nazwa Strona lnx logarytm naturalny: loge x 309 lgx logarytm dwójkowy: log2 x 90 log x logarytm dziesiętny: log10x 496 w podłoga: m ax{n | n ^ x, całkowite n } 87 M sufit: min{n | n ^ x, całkowite n} 87 x mod y reszta: x —y [x/yj 103 m część ułamkowa: x mod 1 90 y f (x) óx sumowanie nieoznaczone 67 V" f (x) óx Ł—a sumowanie oznaczone 68 x^ potęga ubywająca: x!/(x —n)! 66,241 X* potęga przyrastająca: V(x + tl)/F (x) 66,241 n\ podsilnia: rt!/0 ! —n ! /l! H-------b (—1)nrt!/n! 223 mz część rzeczywista: x, jeśli z = x + iy 83 3z część urojona: y, jeśli z = x + iy 83

H,ln [(*) T l m_ rt m n m liczba harmoniczna: 1/1 H-------h 1/n uogólniona liczba harmoniczna: 1/ 1XH-------b 1/n x m-ta pochodna funkcji f w z cykliczna liczba Stirlinga („pierwszego rodzaju”) podzbiorowa liczba Stirlinga („drugiego rodzaju”) liczba Eulera liczba Eulera drugiego rodzaju c # A fcn]f(z) [a.. |3] [m = n] [m\n] [m\\n] [m_Ln] (am ... a0)b pozycyjny zapis liczby Y.™=o K(ai,.. ., an) wielomiany kontynuant Q>k funkcja hipergeometryczna moc zbioru: liczba elementów w zbiorze A współczynnik przy zn w rozwinięciu f (z) przedział domknięty: zbiór {x | oc^ x ^ (3} 1 jeśli m = u, w przeciwnym razie 0 * 1 jeśli m dzieli n, w przeciwnym razie 0 * 1 jeśli m dokładnie dzieli n, w przeciwnym razie 0 * 1 jeśli m jest względnie pierwsze z n, w przeciwnym razie 0 * 46 310 518 290 289 299 302 26 337 234 57 226 94 40 124 173 139 *W ogólności, jeśli S jest dowolnym stwierdzeniem, które może być prawdą lub fałszem, to nawiasowa notacja [S] oznacza 1, jeśli S jest prawdą, a 0 w przeciwnym razie. W tekście książki używamy pojedynczych cudzysłowów (*...*) w celu oznaczenia tekstu samego w sobie, tak jak został napisany, a podwójnych („... ”)—tak jak ma zostać przeczytany. W związku z tym słowo ‘słowo’jest czasami nazywane „słowem.” Wyrażenie postaci ‘a/b c’ ma to samo znaczenie, co ‘a/(b c)\ Ponadto logx/log-y = (logx)/(logy) oraz 2rt! = 2(rt!).

| i | Problemy rekurencyjne W rozdziale tym zajmujemy się trzema przykładowymi problemami, które będą stanowiły przedsmak tego, co nas czeka. Problemy te mają dwie wspólne cechy: wszystkie były wielokrotnie badane przez matematyków, a ich rozwią­ zanie opiera się na pojęciu rekurencji. Rekurencja polega na tym, że roz­ wiązanie badanego problemu wyraża się za pomocą rozwiązań tego samego problemu dla danych o mniejszych rozmiarach. 1.1. W ieże z Hanoi Przyjrzyjmy się na początek zgrabnej łamigłówce zwanej Wieżami z Hanoi. Łamigłówkę tę wymyślił francuski matematyk Edouard Lucas w roku 1883. Mamy wieżę złożoną z 8 krążków ułożonych jeden na drugim i nadzianych na jeden z 3 prętów malejącymi średnicami ku górze: Zadanie polega na przeniesieniu całej wieży krążków na jeden z pozosta­ łych prętów, przy czym w każdym ruchu można brać tylko jeden krążek i nie wolno położyć większego krążka na mniejszym. Lucas [260] ubarwił swoje zadanie legendą o znacznie wyższej Wieży Brahmy, która miała mieć 64 krążki z czystego złota spoczywające na 3 dia­ mentowych igłach. U zarania czasu Bóg umieścił te złote krążki na pierwszej z igieł i polecił grupie mnichów, aby przełożyli je na igłę trzecią zgodnie z po­ Ci, którzy jeszcze tego nie znają, niech podniosą rękę. OK, a teraz cała reszta może spokojnie przeskoczyć do równania (1.1). Złoto— o rany! Nasze krążki są pewnie z czegoś konkretniejszego?

danymi regułami. Mnisi pracują bez wytchnienia dzień i noc. Kiedy skończą, wieża rozsypie się i nastąpi koniec świata. Wcale nie jest oczywiste, że łamigłówka ta ma jakiekolwiek rozwiązanie. Chwila zastanowienia (lub wcześniejsza znajomość problemu) pozwala nam być jednak dobrej myśli. Powstaje teraz pytanie: jaki jest najszybszy spo­ sób wykonania zadania? Ściślej: ile co najmniej ruchów trzeba wykonać, aby przenieść wieżę? Najlepszą metodą zaatakowania problemu tego typu jest pewne jego uogólnienie. Wieża Brahmy zawiera 64 krążki, wieża z Hanoi — 8. Zasta­ nówmy się, co się dzieje w przypadku n krążków. Jedną z zalet takiego podejścia jest to, że możemy wejść w nasz problem nieco głębiej. W rzeczywistości, jak to jeszcze wielokrotnie w tej książce zo­ baczymy, warto r o z w a ż a ć d ro b n e p rzyp ad k i najpierw. Łatwo jest prze­ łożyć wieżę składającą się z jednego lub dwóch krążków. Po paru próbach znajdziemy też bez trudu metodę dla trzech. Następnym krokiem przy rozwiązywaniu problemu będzie wprowadze­ nie odpowiedniej notacji: n a zw ij i z w y c ięż a j. Niech będzie minimalną liczbą ruchów konieczną do przeniesienia n krążków z jednego pręta na drugi zgodnie z zasadami Lucasa. Oczywiście Ti jest równe 1, a Tz = 3. Możemy też natychmiast otrzymać dodatkową wartość, gdy rozważymy przypadek najdrobniejszy ze wszystkich. Oczywiście To = 0, ponieważ żadne ruchy nie są potrzebne, aby przenieść zero krążków! Sprytni matematycy nie wstydzą się myśleć detalicznie (think smali), gdyż przypadki ogólne są ła­ twiejsze do ogarnięcia, gdy dokładnie zrozumiemy sytuacje krańcowe (nawet gdy są trywialne). Spójrzmy na to z innej strony i postarajmy się myśleć z rozmachem (think big)\ jak można przenieść dużą wieżę? Próby z trzema krążkami pokazują, że do celu prowadzi przeniesienie 2 górnych krążków na pręt środkowy, następ­ nie przeniesienie trzeciego krążka na pręt docelowy i w końcu przeniesienie na ten pręt pozostałych dwóch krążków. Pomysł ten dostarcza nam ogólnej metody dla n krążków: najpierw przenieś n —1 wierzchnich krążków na pręt pomocniczy (to wymaga Tn_i ruchów), następnie przenieś największy krą­ żek na pręt docelowy (1 ruch) i w końcu przenieś położone na pomocniczym pręcie n — 1 krążków na pręt docelowy (znów T^-i ruchów). Możemy zatem przenieść n krążków (dla n > 0) w co najwyżej 2Tn_i + 1 ruchach: Tn ^ 2Ta_i + 1 , dla n > 0. W powyższym wzorze występuje ‘^ ’ zamiast ‘= *, gdyż jak na razie poka­ zaliśmy, że 2Tn_i + 1 ruchów wystarcza. Nie pokazaliśmy jeszcze tego, że konieczne jest użycie co najmniej 2Tn_i + 1 ruchów. Nietrudno jest jednak dojść do tego.

1.1. W ieże z Hanoi I Czy może istnieć lepsze rozwiązanie? Okazuje się, że nie. W którymś momencie musimy przecież ruszyć największy krążek i wtedy pozostałe n —1 musi leżeć na pręcie pomocniczym. Aby je tam przenieść, musimy wykonać co najmniej Tn-i ruchów. Oczywiście gdybyśmy byli rozrzutni, moglibyśmy największy krążek jeszcze poprzekładać sobie tam i z powrotem, ale po doko­ naniu tego po raz ostatni musimy znowu przenieść rt —1 krążków (z których wszystkie w tym momencie muszą się znaleźć na jednym pręcie) na najwięk­ szy z nich znajdujący się już na pręcie docelowym, a to wymaga znów Tn_i ruchów. Zatem n—1 + i dla n > 0 . Te dwie nierówności wraz z trywialnym rozwiązaniem dla rt = 0 dają To = 0; Tn = 2Tn_i + 1 , dla rt > 0 . (i-i; Zauważmy, że te wzory są zgodne ze znanymi nam już wartościami Ti = 1 i T2 = 3. Doświadczenie z małymi liczbami pomogło nam nie tylko znaleźć ogólny wzór, lecz także pozwoliło nam sprawdzić, czy nie popełniliśmy jakie­ goś głupiego błędu. Takie weryfikacje będą bardzo użyteczne, gdy napotkamy bardziej skomplikowane obliczenia w późniejszych rozdziałach. Zestaw równości takich jak (1 .1) nazywany jest rekurencją (używa się też na nie określenia relacji rekurencyjnej lub rekursywnej). Rekurencją składa się z podania wartości brzegowej i z równania wyrażającego ogólną wartość za pomocą wartości wyrazów wcześniejszych. Czasami nazywamy rekurencją samo równanie ogólne, choć z technicznego punktu widzenia potrzeba tam jeszcze wartości brzegowej. Wyprowadzona rekurencją pozwala na obliczenie Tn dla każdego n. Nikt jednak nie lubi wyliczać wartości z zależności rekurencyjnej: dla dużych n jest to zbyt pracochłonne. Rekurencją dostarcza nam jedynie informacji lokalnej. Rozwiązanie rekurencji zadowalałoby nas znacznie bardziej. Chcielibyśmy więc uzyskać zgrabną „zwartą postać” na Tn, za pomocą której moglibyśmy szybko dostawać żądane wartości nawet dla dużych rt. Mając taką zwartą postać możemy lepiej zrozumieć, czym w rzeczywistości jest Tn. Jak zatem rozwiązuje się taką rekurencję? Można oczywiście zgadnąć wynik i pokazać, że mieliśmy rację. Najlepiej w tym celu jest znowu przyjrzeć się drobnym przypadkom. Liczymy więc kolejno: T3 = 2-3 + 1 = 7; T4 = 2*7+1 =15; T5 = 2*15 + 1 = 31; Tg = 2*31+1 =63. Aha! To niewątpliwie wygląda, jak gdyby Większość publikowanych „ rozwiązań” problemu Lucasa, takich jak na przykład podane przez Allardice’a i Frasera [7], nie zawiera uzasadnienia tego, że Tu musi być nie mniejsze niż 2Tn—1+ 1. Tak, ta k.. .ja już to gdzieś widziałem. Tn = 2n - 1 , dla rt >. 0 . (1.2 ) W każdym razie działa przynajmniej dla n ^ 6 . I I P JL

1 . Problem y rekurencyjne Indukcja matematyczna pozwala dowieść, że możemy wspiąć się na drabinę tak wysoko jak chcemy przez wykazanie, że możemy wspiąć się na najniższy szczebel (baza), a następnie, że z każdego szczebla możemy wspiąć się na następny (krok indukcyjny). Indukcja matematyczna stanowi ogólne narzędzie dowodzenia, że pew­ ne stwierdzenie o liczbie naturalnej rt jest prawdziwe dla wszystkich n no- Najpierw wykazujemy prawdziwość dla możliwie małego n 0— nazywamy to bazą indukcji. Następnie dowodzimy stwierdzenia dla rt > rto, zakładając, że zostało ono już udowodnione dla wszystkich wartości pomiędzy no i n —1 włącznie — tę fazę nazywamy krokiem indukcyjnym. Dowód taki dostarcza nam nieskończonej liczby wyników za pomocą skończonego nakładu pracy. Definicje rekurencyjne wyśmienicie nadają się do dowodów indukcyjnych. W naszym przypadku na przykład wzór (1.2 ) wynika bezpośrednio z (1 .1): Baza jest oczywista, gdyż To = 2° — 1 = 0 . Krok indukcyjny wynika dla n > 0 natychmiast, gdy założymy, że wzór (1 .2 ) zachodzi dla n zastąpionego przez n —1: Tn = 2Tn_, + 1 = 2(2n_1 - 1) + 1 = 2n - 1 . Okazuje się więc, że wzór (1.2 ) zachodzi również dla n. Świetnie! Nasze po­ szukiwania wzoru na Tn zostały zakończone sukcesem. Oczywiście nie oznacza to końca pracy mnichów: wciąż sumiennie prze­ kładają krążki i jeszcze zajmie im to trochę czasu, gdyż dla n = 64 trzeba wykonać 264—1 ruchów (około 18 trylionów). Nawet z niemożliwą do zrealizo­ wania prędkością jednego ruchu na mikrosekundę przełożenie wieży Brahmy zajęłoby im ponad 5000 wieków. Oryginalna łamigłówka Lucasa była nieco bardziej realna: wymagała jedynie 28 —1 = 255 ruchów, co wprawnej ręce zajmuje około 4 minut. Rekurencją wież z Hanoi jest typowa dla wielu przypadków, z którymi spotykamy się w zastosowaniach najprzeróżniejszych rodzajów. Znalezienie postaci zwartej dla pewnej wielkości takiej jak Tn będzie przebiegało w na­ stępujących fazach: 1 . Przypatrz się małym przypadkom. To daje wyobrażenie o problemie i pomaga w fazach 2 i 3. 2. Zgadnij postać wyrażenia matematycznego opisującego szukaną wartość i udowodnij jego poprawność. W przypadku wież z Hanoi jest to reku- rencja (1.1), która pozwala nam wyliczyć wartość Tn.dla każdego n. 3. Znajdź i udowodnij zwartą postać naszego wyrażenia matematycznego. Dla wież z Hanoi będzie to rozwiązanie rekurencji (1.2 ). W książce tej będziemy się przede wszystkim zajmowali fazą trzecią. Istotnie, będziemy często przeskakiwali fazy 1 i 2 , gdyż wyrażenie matematyczne bę­ dzie nam dane na starcie. Nawet wtedy jednak, przy badaniu pojawiających się podproblemów, będziemy wracali do faz 1 i 2 . Analizując wieże z Hanoi doszliśmy do poprawnego rozwiązania, ale po drodze wykonaliśmy „indukcyjny skok” — musieliśmy w pewnym momencie polegać trochę na szczęściu, że uda się nam zgadnąć wynik. Jednym z głów­

1.2. Proste na płaszczyźnie nych celów tej książki jest wyjaśnienie, jak można rozwiązywać rekurencje bez bycia jasnowidzem. Zobaczmy dla przykładu, w jaki sposób rekurencją (1 .1) może się uprościć przez dodatnie 1 do obu stron równości: ( ^ To + 1 = i ; r ' 1 Tn + 1 = 2Tn_i + 2 , dla rt > 0. ' ! i Teraz jeśli przyjmiemy Un = Tn + 1, to otrzymamy U0 = 1; Un = 2 Un_, dla n > 0 . (i-3) Nie trzeba być geniuszem, aby odkryć, że rozwiązanie tej rekurencji, to po prostu Un = 2n; zatem Tn = 2n —1. Nawet komputer by to zauważył. Interesujące: pozbywamy się +1 w (1.1) przez dodanie jedynki, a nie odjęcie! 1.2. Proste na płaszczyźnie Drugi z naszych przykładów będzie miał charakter geometryczny. Ile kawał­ ków pizzy można uzyskać za pomocą rt prostoliniowych cięć nożem? Albo, ściślej, jaka jest największa liczba Lu obszarów wyznaczonych przez n pro­ stych na płaszczyźnie? Problem ten został rozwiązany przez szwajcarskiego matematyka Jacoba Steinera w 1826 roku [339]. Jak zwykle, rozważymy na początku drobne przypadki, pamiętając aby zacząć od najdrobniejszego z nich. Płaszczyzna bez prostych ma jeden obszar, płaszczyzna z jedną prostą— 2 obszary, z dwiema— 4. Lo = 1 Li = 2 (Każda prosta przedłuża się w obu kierunkach w nieskończoność). A zatem, myślimy, Ln = 2n. Oczywiście! Dodanie nowej prostej po­ dwaja po prostu liczbę obszarów. Niestety, nie jest to prawdą. Tak byłoby, gdyby ri-ta prosta mogła podzielić każdy zastany obszar na dwa. Niewąt­ pliwie można za pomocą tej prostej podzielić taki obszar na co najwyżej dwa kawałki, gdyż każdy z zastanych obszarów jest wypukły. (Prosta może podzielić obszar wypukły na co najwyżej dwa obszary, każdy z nich znów wypukły). Kiedy jednak dodamy trzecią prostą— pogrubioną na rysunku poniżej— przekonamy się, że może ona podzielić co najwyżej 3 spośród 4 (Pizza z serem szwajcarskim?) Obszar jest wypukły, jeśli zawiera wszystkie odcinki łączące dowolne dwa z jego punktów. (To nie jest dokładnie to, co na ten temat można przeczytać w słowniku, ale to jest coś, w co wierzą matematycy.)

1 . Problem y rekurencyj 2 0 obszarów, niezależnie od tego, jak poprowadziliśmy poprzednie 2 proste: Zatem nie możemy uzyskać więcej niż L3 = 4 + 3 = 7 obszarów. Po krótkim zastanowieniu się dostrzeżemy właściwe uogólnienie: n-ta prosta (dla n > 0 ) zwiększa liczbę obszarów o k wtedy i tylko wtedy, gdy przecina k spośród zastanych obszarów. Dzieje się tak z kolei wtedy i tylko wtedy, gdy przecina zastane proste w k —1 różnych punktach. Dwie proste mogą przeciąć się w co najwyżej jednym punkcie, a więc nowa prosta może przeciąć co najwyżej n —1 zastanych prostych w co najwyżej n —1 różnych punktach, zatem musi być k ^ n. Udało sięnamznaleźć ograniczenie górne: Ln ^ Ln_i + t l , dla n > 0. Co więcej, za pomocą indukcji można łatwo pokazać, że w powyższym wzo­ rze możemy uzyskać równość. Wystarczy tak poprowadzić n-tą prostą, żeby nie była równoległa do żadnej innej (zatem wszystkie je będzie przecinać) i tak, żeby nie przechodziła przez żaden z istniejących już punktów przecięcia (zatem wszystkie proste będzie przecinać w różnych punktach). Uzyskana rekurencją przedstawia się następująco: ' 1-0 = 1 ; (i-4) Ln = Ln_i + rt, , dla rt > 0. Znane już wartości Li, L2 i L3 zgadzają się,więcją akceptujemy. Przystąpmy teraz do poszukiwań postaci zwartej. Moglibyśmy zacząć bawić się w zgadywanie, tak jak poprzednio, ale ciąg 1, 2, 4, 7, 11, 16, ... niczego nie przypomina. Spróbujmy więc inaczej. Rekurencję często można zrozumieć „rozwijając” ją tak jak poniżej: Rozwijając? Raczej nazwałbym to wtykaniem w siebie. Ln — Ln_i + Tl = Lrt- 2 + (n —1) + n = 'Ln _3 + (n - 2 ) + (n - 1 ) + n — Lo + 1 + 2 H-------1- (rt —2 ) + (n —1) + n = 1 + Sn , gdzie Sn = 1 + 2 + 3 H-------1- (rt —1 ) + n .

1.2. Proste na płaszczyźnie Innymi słowy, Ln jest o 1 większe od sumy Sn początkowych rt liczb natu­ ralnych. Liczby Sn pojawiają się na tyle często, że warto zrobić zestawienie paru początkowych wartości. Będziemy mogli łatwiej skojarzyć te liczby, gdy zo­ baczymy je następnym razem. n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 s n 1 3 6 10 15 21 28 36 45 55 66 78 91 105 Liczby te są także zwane liczbami trójkątnymi, gdyż Sn jest liczbą kul bilar­ dowych ułożonych w trójkąt o n rzędach. Na przykład, przy n = 4 trójkątne ustawienie ’vX wymaga S4 = 10 kul. Aby wyliczyć Sn, możemy skorzystać z pomysłu Gaussa, do którego do­ szedł w roku 1786, mając zaledwie 9 lat [88] (zobacz także Euler [114, część 1, §415]): Sn = + s n = 1 rt + 2 + 3 + + (n —1) + (rt —2 ) + + (rt —1) + + 2 + 2Sr,, —' (n + 1) + (tl+ I) + (ti + 1) + ••• + (n + 1) + (n + 1) Dodajemy po prostu ciąg Sn do niego samego w odwrotnej kolejności, tak żeby każda z rt kolumn po prawej stronie sumowała się do n + 1. Po uprosz­ czeniu otrzymujemy Sr, = n ( n + 1 (i-5) Wygląda na to, że Gaussowi przypisuje się kupę rzeczy — albo rzeczywiście był niezły, albo miał świetnego agenta prasowego. A może miał po prostu magnetyzującą osobowość? Dobrze, mamy więc rozwiązanie Ln , 2 l2 ± ! ! + 1 , (1.6) Jako eksperci moglibyśmy być zadowoleni z uzyskanego wyprowadzenia i uznać je za dowód, choć trochę machaliśmy rękami przy rozwijaniu i od­ wracaniu ciągu. Studenci matematyki powinni jednak móc sprostać wyższym wymaganiom; nie jest więc złym pomysłem przedstawić precyzyjny dowód przez indukcję. Kluczowym przejściem indukcyjnym jest Ln = Ln_i + n = ( j { n - l ) n + 1) + n = jn { n + 1) + 1 . W tym momencie bez wątpienia mamy już postać zwartą (1.6 ). Od pewnego czasu mówimy o postaciach zwartych bez precyzowania, co to takiego. Zwykle wiadomo, o jaką postać chodzi. Rekurencje takie jak (1 .1) czy (1.4 ) nie są w postaci zwartej — wyrażają pewną wielkość odwołując się Bogiem a prawdą Gaussjest często nazywany największym matematykiem wszechczasów. Dobrze jest więc zrozumieć przynajmniej jedno zjego odkryć.

W końcu rt! może być całkiem sensownie przybliżane wzorem Stirlinga, w którym występują tylko „przyzwoite” operacje, o czym później w tej książce. Czy „nieskończona litera V”jest pojęciem ścisłym? ... oraz chwili zamyślenia ... do niej samej. Z kolei rozwiązania takie jak (1.2 ) lub (1.6 ) są zwarte. Sumy typu 1 + 2 H-------b tl nie są w postaci zwartej — oszustwa dokonuje się przez użycie notacji ‘ ’— za to wyrażenia typu n(n -b 1) / 2 mają postać zwartą. Zgrubna definicja mogłaby wyglądać następująco: Wyrażenie na wartość f (n) jest w postaci zwartej, jeśli możemy je wyliczyć stosując skończoną, nieza­ leżną od n, liczbę „dobrze znanych” działań standardowych. Na przykład, 2n —1 i n ( n + l ) / 2 są w postaci zwartej, gdyż wykorzystują i to w jawny sposób jedynie dodawanie, odejmowanie, mnożenie, dzielenie i potęgowanie. Liczba wszystkich prostych postaci zwartych jest ograniczona. Na do­ miar złego istnieją rekurencje nie mające zwartych odpowiedników. Kiedy takie rekurencje napotykamy odpowiednio często, uzupełniamy arsenał pod­ stawowych operacji; manewr ten zwiększa wydatnie zakres problemów mają­ cych swe rozwiązanie w „prostych” postaciach zwartych. Przykładem takiej operacji jest iloczyn początkowych rt liczb naturalnych, n!, który okazał się tak ważny, że obecnie uznajemy go za operację podstawową. Przyjmujemy więc, że wzór n! jest w postaci zwartej, choć jego odpowiednik ‘ 1 *2 *... -n* nie jest. A teraz, króciutko, pewien wariant problemu prostych na płaszczyźnie. Załóżmy, że zamiast prostych mamy załamane linie tworzące coś w rodzaju nieskończonej litery V. Jaka jest maksymalna liczba Vn obszarów możliwych do uzyskania przez ułożenie takich n nieskończonych V na płaszczyźnie? Spodziewamy się, że Vn powinno być tak ze dwa-trzy razy większe od Ln. Zobaczmy: Zi = 2 Z2 = 7 Przyjrzawszy się tym drobnym przypadkom, po chwili namysłu zauwa­ żamy, że zagięte linie przypominają parę przecinających się prostych, z tym że niektóre obszary zlewają się po tej stronie, po której „podwójne” proste nie przedłużają się poza punkt spotkania. 4

1.3. Problem Józefa Flawiusza i Obszary 2 , 3 i 4, które byłyby rozłączne w przypadku dwóch prostych, stają się jednym obszarem, jeśli dopuścimy załamanie jednej prostej. Tracimy więc 2 obszary. Niemniej jednak, zawsze tak możemy przesunąć to załamanie, żeby punkt załamania leżał „poza” rejonem przecięć z innymi prostymi; w tym przypadku te 2 obszary to będzie wszystko, co stracimy. Ubędą nam zatem tylko dwa obszary dla każdej załamanej prostej. Mamy więc Z n = I_2n —2n = 2 n (2 n + 1 )/2 + 1 —2n = 2u2 —n + 1 , (i-7) Porównując zwarte postacie wzorów (1.6 ) i (1.7), dochodzimy do wniosku, że dla dużych n mamy Ln ~ 5 u 2 , Z n - 2n2 ; dostajemy więc 4 razy tyle obszarów w przypadku linii załamanych, niż w przypadku normalnych prostych. W późniejszych rozdziałach dokładnie omó­ wimy, jak analizować przybliżone zachowanie się funkcji całkowitoliczbowych dla dużych n. (Symbol *~ł zdefiniowany jest w rozdziale 9.1.) W ćwiczeniu 18 znajdziecie dalsze szczegóły. 1.3. Problem Józefa Flawiusza Ostatni z wprowadzających przykładów będzie wariantem starożytnego pro­ blemu nazwanego tak od znanego historyka pierwszego wieku naszej ery Jó­ zefa Flawiusza. Legenda głosi, że Flawiusz nie byłby dziś znany, gdyby nie jego talent matematyczny. W trakcie wojny rzymsko-żydowskiej został wraz z grupą 41 żydowskich powstańców otoczony przez Rzymian w jaskini. Wo­ ląc samobójstwo od pojmania, powstańcy zdecydowali się utworzyć krąg i zabijać co trzecią osobę, aż nikt nie pozostanie przy życiu. Flawiusz jednak wraz ze swoim przyjacielem nie zgadzał się na to nonsensowne samobójstwo i szybko wyliczył, gdzie on i jego przyjaciel powinni stanąć w kręgu, aby uniknąć śmierci. W naszej wersji załóżmy, że mamy n ludzi ponumerowanych od 1 do n ustawionych w kręgu. Eliminować będziemy co drugą osobę, aż pozostanie tylko jeden człowiek żywy. Niech na przykład początkowa konfiguracja dla u = 10 wygląda następująco: r v ' ' I (Ahrens [6, tom 2] oraz Herstein i Kaplansky [187] omawiają interesującą historię tego problemu. Sam Flawiusz jest zbyt pobieżny [197].) ... dając nam tym samym szansę usłyszenia tej historii.

Oto mamy przypadek, gdzie n = 0 nie ma sensu. Nawet zły strzał ma swoją wartość: pozwala nam wciągnąć się w problem. Tu leży pies pogrzebany. Mamy przecież ][2n) = nowaliczba[]{n)), przy czym nowaliczba(k) = 2k —1 . Porządek eliminowania jest taki: 2, 4, 6 , 8 , 10, 3, 7, 1, 9, tak więc numer 5 przeżywa. Nasz problem polega teraz ogólnie na wyliczeniu przeżywającego numeru J(n). Wiemy już, że J(10) = 5 . Pierwszy pomysł: J(rt) = n /2 dla parzystych n; przypadek n = 2 zgadza się: J(2) = 1. Kilka następnych wartości jest już jednak innych — hipoteza upada dla n = 4 i n = 6 . rt 1 2 3 4 5 6 J(n) 1 1 3 1 3 5 Przyjrzyjmy się tym wartościom i spróbujmy lepiej strzelić. Hmmm ... wy­ gląda na to, że J(n) zawsze jest nieparzyste. Faktycznie, są po temu powody: Pierwsza runda wokół okręgu eliminuje wszystkie numery parzyste. Co wię­ cej, jeśli n jest liczbą parzystą, to dochodzimy po niej do sytuacji podobnej, tyle że mamy do czynienia z połową ludzi, a ich numery się tylko trochę zmieniły. Załóżmy więc, że zaczęliśmy z 2n osobami. Po pierwszej rundzie wokół okręgu zostaniemy z i kolejny obrót zaczniemy od numeru 3. Mamy sytuację taką, jak gdybyśmy zaczęli z n osobami, których numery zostały podwojone i zmniejszone o 1. Mamy więc, J(2n) = 2J(n) —1 , d l a u ^ l . Możemy teraz od razu przejść do dużych rt. Jeżeli, na przykład, J(10) = 5, to J(20) = 2J(10) —1 = 2 - 5 - 1 = 9. Podobnie, J(40) = 17, i teraz już możemy stąd wywnioskować, że J(5 •2m) = 2m+1 + 1. Jak w takim razie będzie to wyglądało z liczbami nieparzystymi? W przy­ padku 2rt + 1 osób widać, że osoba o numerze 1 odpada zaraz po osobie o

numerze 2n i zostajemy wtedy z 2n + 1 2n —1 3 5 9 7 Znowu otrzymaliśmy tak jakby n osób, lecz tym razem ich numery są po­ dwojone i powiększone o 1. W związku z tym Łącząc te dwa równania z J(1) = 1 otrzymujemy rekurencję obejmującą wszystkie przypadki: Tym razem nasza rekurencja jest bardziej „wydajna”, ponieważ za każdym razem, gdy korzystamy z tej rekurencji, zamiast otrzymywania J(n) z J(tl—1) mamy mniej więcej dwukrotne zmniejszenie argumentu n. Możemy zatem ob­ liczyć np. J(1000000) za pomocą zaledwie 19 kroków wynikających z (1.8). Wciąż jednak brakuje nam postaci zwartej; dawałoby to szybszą metodę wy­ liczania J(n), a ponadto byłoby bardziej pouczające. W końcu posiadanie postaci zwartej może być często na wagę życia i śmierci. Otrzymana rekurencja pozwala na szybkie skonstruowanie tabeli małych wartości. Być może pozwoli nam to uchwycić regułę i w rezultacie zgadnąć odpowiedź. n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 Voila\ Wygląda na to, że możemy zgrupować wartości według kolejnych potęg dwójki (zaznaczonych pionowymi przegrodami w tabeli). J(n) jest zawsze jedynką na początku grupy, a wewnątrz grupy zwiększa się o 2. Jeśli więc przedstawimy n w postaci n = 2m + l, gdzie 2m jest największą potęgą dwójki nie przekraczającą n, a l jest tym co zostaje, to rozwiązaniem naszej rekurencji będzie J(2n + 1) = 2J(n) + 1 , dla u ^ 1. 1(1) = 1 ; J(2tl) = 2 J(n) —1 , dla n ^ 1; J(2n + 1) = 2J(n) + 1 , d l a r i ^ l . (1.8) J(2m + 1) = 21 + 1 ,