Tytuł oryginału

HOW TO CUT A CAKE

and other mathematical conundrums

Copyright © Joat Enterprises 2006

All rights reserved

Projekt okładki

© Spike Gerrell

Redaktor prowadzący

Adrian Markowski

Redakcja

Ewa Koszur-Kościelska

Korekta

Andrzej Massé

ISBN 978-83-7961-826-2

Warszawa 2012

Wydawca

Prószyński Media Sp. z o.o.

ul. Rzymowskiego 28

02-697 Warszawa

www.proszynski.pl

Wstęp

Czasami, kiedy czuję się wyjątkowo zrelaksowany i zaczynam błądzić gdzieś myślami, zastanawiam się, jak wyglądałby świat, gdyby wszyscy lubili matematykę tak bardzo jak ja. W wiadomościach telewizyjnych na pierwszym miejscu pojawiałyby się najnowsze twierdzenia z topologii algebraicznej zamiast żałosnych skandali politycznych, nastolatki ściągałyby sobie na iPody matematyczną listę przebojów, a piosenkarze calypso (pamiętacie takich?) przygrywaliby na gitarach w rytm melodii Lemat trzeci… Co mi przypomina, że muzyk folkowy Stan Kelly (dziś Stan Kelly-Bootle, sprawdźcie go sobie w Google’u) faktycznie napisał taką piosenkę, pod koniec lat sześćdziesiątych, kiedy studiował matematykę na Uniwersytecie Warwick. Zaczynała się tak:

„Lemat trzeci, bardzo piękny, i odwrotność piękna też,

Lecz wie tylko Bóg i Fermat, które z nich prawdziwe jest”.

W każdym razie ja zawsze traktowałem matematykę jako źródło inspiracji i przyjemności. Zdaję sobie sprawę, że u większości ludzi budzi ona grozę, nie radość, ale nie potrafię podzielać tego poglądu. Na poziomie racjonalnym rozumiem niektóre z powodów powszechnego strachu przed matematyką: nie ma nic gorszego niż przedmiot, który bezwzględnie wymaga dokładności i precyzji, kiedy masz nadzieję wywinąć się paroma zgrabnymi słówkami i sporą dozą tupetu. Ale na poziomie emocjonalnym trudno mi zrozumieć, jak to możliwe, aby dyscyplina mająca tak istotne znaczenie dla świata, w którym żyjemy, z tak długą i pasjonującą historią, pełna najbardziej błyskotliwych odkryć, jakich udało się dokonać człowiekowi, nie intrygowała i nie fascynowała.

Z drugiej strony ornitologom amatorom także trudno jest zrozumieć, dlaczego reszta ludzkości nie podziela pasji, z jaką odhaczają pozycje na listach. „Mój Boże, czy to upierzenie godowe głuptaka czubatego? Ostatniego osobnika odnotowanego w Wielkiej Brytanii widziano na wyspie Skye w 1843 roku, w dodatku był częściowo schowany za… o, nie, to tylko szpak z ubłoconym ogonem”. Nie chcę tu nikogo urazić – sam zbieram skały. „O rany! Prawdziwy granit asuański!” Nasz dom zapełnia się powoli kawałkami planety.

Nie pomaga też zapewne to, że pod słowem „matematyka” większość ludzi rozumie zwykłą arytmetykę, która może być fajna, na swój specyficzny sposób, jeśli sobie z nią dobrze radzisz. Jeśli nie, jest straszna. Poza tym bardzo trudno czerpać z czegoś przyjemność – czy to z obserwacji ptaków, czy z matematyki – jeśli ktoś stoi nad tobą z długopisem w dłoni, tylko czekając, aż zrobisz jakiś drobny błąd, na który natychmiast się rzuci, żeby zabazgrać go na czerwono. (To przenośnia, chociaż kiedyś tak było, w sensie dosłownym). A przecież co znaczy jedno czy dwa miejsca po przecinku między przyjaciółmi? Ale gdzieś pomiędzy programem nauczania a tym, co zrozumie z niego młody Jaś, znaczna część związanej z matematyką zabawy i przyjemności wyparowała. A szkoda.

Nie twierdzę, że książka Jak pokroić tort będzie miała zasadniczy wpływ na matematyczne zdolności ogółu społeczeństwa, chociaż sądzę, że mogłoby się tak stać. (Czy byłby to wpływ pozytywny, to już inna sprawa). Staram się tutaj przede wszystkim głosić słowo do tych już nawróconych. To książka dla fanów, entuzjastów, dla ludzi, którzy naprawdę lubią matematykę i mają na tyle młody umysł, że potrafią czerpać mnóstwo przyjemności z zabaw i gier. Tę frywolną atmosferę podkreślają cudowne rysunki Spike’a Gerrella, które doskonale oddają ducha przedstawianych tutaj wywodów.

Moje intencje są jednak śmiertelnie poważne.

Chciałem zatytułować tę książkę Weapons of Math Distraction (Broń matematycznego rażenia[1]), co w moim odczuciu odzwierciedlało połączenie powagi i frywolności, więc pewnie powinienem być wdzięczny działowi marketingu za weto. Ale z tym praktycznym, „cukierniczym” tytułem, na który się zdecydowaliśmy, wiąże się pewne niebezpieczeństwo: niektórzy z was mogą myśleć o kupieniu tej książki w celu uzyskania poważnych porad kulinarnych. Stąd sprostowanie: to książka o zagadkach i grach matematycznych, nie o wypiekach. Tort to w istocie przestrzeń z miarą borelowską.

Ukryta głęboko pod postacią… tortu właśnie. A matematyka uczy nas nie jak go upiec, ale jak go równo podzielić między dowolną liczbę osób. W dodatku – co o wiele trudniejsze – bez powodowania zazdrości. Krojenie tortu stanowi proste wprowadzenie do matematycznych teorii podziału zasobów. Specjaliści nazywają wstępne rozważania tego typu „modelem zabawkowym”, drastycznie uproszczonym w stosunku do tego, co można spotkać w rzeczywistości. Ale skłania on do zastanowienia się nad pewnymi istotnymi kwestiami. Na przykład pokazuje, że łatwiej jest podzielić zasoby między kilka rywalizujących ze sobą grup w sposób, jaki wszystkie uznają za sprawiedliwy, jeśli każda grupa przypisuje tym zasobom inną wartość.

Podobnie jak jego poprzednicy, Game, Set and Math, Another Fine Math You’ve Got Me Into oraz Histerie matematyczne (wydane, tak jak ta książka, przez Oxford University Press), niniejszy tom powstał na podstawie serii felietonów o łamigłówkach matematycznych, które napisałem dla „Scientific American” i obcojęzycznych wersji tego czasopisma w latach 1987–2001. Felietony lekko przeredagowano, wszystkie dostrzeżone błędy poprawiono, wprowadzono nieznaną liczbę nowych błędów, a także dodano w odpowiednich miejscach komentarze czytelników, pod nagłówkiem „Uwagi”. Przywróciłem część materiałów, która nie ukazała się na łamach magazynów ze względu na ograniczoną ilość miejsca, więc można powiedzieć, że jest to swego rodzaju „wersja reżyserska”. Książka obejmuje różnorodne tematy, od teorii grafów do rachunku prawdopodobieństwa, od logiki do powierzchni minimalnych, od topologii do kwazikryształów. I dzielenia tortu, oczywiście. Zostały wybrane głównie ze względu na wartość rozrywkową, nie wagę naukową, proszę więc nie wyobrażać sobie, że treść w pełni oddaje obecny stan wiedzy w zakresie pionierskich matematycznych badań.

Z pewnością jednak go odzwierciedla. Paląca kwestia krojenia tortu to część długiej tradycji w matematyce – sięgającej co najmniej 3500 lat wstecz, do starożytnego Babilonu – stawiania poważnych pytań w niepoważny sposób. Kiedy więc czytasz, tak jak tutaj, o tym, „dlaczego kable telefoniczne się plączą”, ten temat przyda się nie tylko do uporządkowania gmatwaniny przewodów, jaka zazwyczaj łączy telefon ze słuchawką. Najbardziej interesujące zagadnienia w matematyce odznaczają się ciekawą uniwersalnością – okazuje się, że koncepcje wywodzące się z jakiegoś prostego problemu rzucają światło na wiele innych kwestii. W otaczającym nas świecie dużo różnych rzeczy skręca się i wije: kable telefoniczne, wąsy czepne roślin pnących, cząsteczki DNA, podwodne przewody telekomunikacyjne. Te cztery przykłady zastosowania matematyki opisującej skręty i zwoje znacznie się między sobą różnią pod wieloma istotnymi względami: okazałbyś zrozumiałe wzburzenie, gdyby inżynier telekomunikacji zabrał ci kabel od telefonu i zastąpił go kawałkiem powoju. Ale jednocześnie pod pewnym użytecznym względem te zagadnienia łączą się ze sobą: ten sam prosty model matematyczny rzuca światło na każde z nich. Może nie odpowie na wszystkie pytania, jakie chciałbyś zadać, i pominie pewne ważne kwestie praktyczne, ale kiedy uproszczony model otworzy drzwi do analizy matematycznej, wtedy na tej podstawie można tworzyć bardziej złożone, bardziej szczegółowe modele.

Moim celem jest tutaj połączenie abstrakcyjnego myślenia ze sprawami znanymi z codziennego życia, tak aby ta mieszanka doprowadziła do powstania nowych matematycznych koncepcji. Zysk, dla mnie, nie polega na otrzymaniu praktycznych rozwiązań rzeczywistych problemów. Głównym zyskiem jest nowa matematyka. Nie da się na kilku stronach opracować istotnego zastosowania matematyki, ale można, przy wystarczającej dozie wyobraźni, zrozumieć, jak matematyczna idea zaczerpnięta z jednego kontekstu może niespodziewanie znaleźć zastosowanie w innym. Być może najlepszym tego przykładem w mojej książce jest związek między zagadką zwaną Imperiami a obwodami elektronicznymi. Dziwna, wymyślna łamigłówka dotycząca kolorowania map terytoriów na Ziemi i Księżycu (rozdział 9) daje pewne praktyczne wskazówki, które przydają się w istotnej kwestii sprawdzania płytek obwodów drukowanych pod kątem wad (rozdział 10). Matematycy po raz pierwszy natknęli się na kluczową koncepcję w niepoważnym kontekście (chociaż nie aż tak frywolnym jak wersja tu przedstawiona) i dopiero wtedy okazało się, że ma ona całkiem poważne zastosowanie.

Może to działać także odwrotnie. Inspiracją do rozdziału 15. było niezwykłe zachowanie pewnego gatunku azjatyckich świetlików, którego samce synchronizują wysyłane przez siebie błyski – prawdopodobnie aby podnieść zbiorową zdolność wabienia samic, chociaż nie polepsza to zdolności indywidualnych. Jak dochodzi do synchronizacji świetlnych sygnałów? Tu najpierw pojawił się problem poważny, matematyka wzięła go na warsztat i rozwiązała przynajmniej częściowo, a dopiero później okazało się, że te same matematyczne operacje można wykorzystać w wielu innych kwestiach związanych z synchronizacją. W moim ujęciu cała sprawa zmienia się w grę planszową. Co ciekawe: kilka pozornie tylko prostych pytań dotyczących tej gry pozostaje bez odpowiedzi. W pewnym sensie rzeczywiste zastosowanie rozumiemy lepiej niż prosty model.

Każdy rozdział tworzy samodzielną całość – z nielicznymi wyjątkami. Możesz zacząć w dowolnym miejscu, a jeśli z jakiegoś powodu utkniesz, możesz porzucić dany rozdział i spróbować z innym. Lektura zaowocuje – śmiem twierdzić – lepszym zrozumieniem tego, jak wiele tematów obejmuje matematyka, jak daleko wykracza poza to, czego uczą nas w szkole, i jak zdumiewająco różnorodne ma zastosowania, a także odkryciem zaskakujących powiązań, spajających ten przedmiot w całość o niesamowitej sile oddziaływania. A wszystko to osiągniesz dzięki grom i rozwiązywaniu zagadek.

I, przede wszystkim, dzięki gimnastykowaniu umysłu.

Nigdy nie lekceważ potęgi zabawy.

Ian Stewart

Coventry, kwiecień 2006

1 Tytuł zaproponowany przez autora jest jeszcze dowcipniejszy, bo „math distraction” to „matematyczne rozrywki”, a całość brzmi bardzo podobnie do angielskiego określenia weapons of mass destruction, które oznacza broń masowego rażenia (przyp. tłum.).

Rysunki – podziękowanie i prawa autorskie

Rys. 11–14 Przedruk za zgodą. © Hans Melissen, Packing and Covering with Circles, praca doktorska, Uniwersytet w Utrechcie, 1997.

Rys. 34a, b Przedruk za zgodą. © John M. Sullivan, 1995, 1999.

Rys. 48, 52 Przedruk z DNA Structure and Function, Richard B. Sinden, Academic Press, San Diego, © 1994, za zgodą Elsevier.

Rys. 49 Przedruk za zgodą. © Matt Collins, 1999.

Rys. 51 Przedruk za zgodą Zhifenga Shao, Uniwersytet Wirginii.

Rozdział 1

Twoja połowa jest większa od mojej!

Jeśli dwie osoby chcą podzielić się tortem i obyć się przy tym bez kłótni, uświęcone tradycją rozwiązanie opiera się na zasadzie „ja kroję, ty wybierasz”. Zadanie staje się zaskakująco trudne już przy trzech osobach, a im więcej amatorów tortu, tym sprawa bardziej się komplikuje. Chyba że użyjemy przesuwającego się powoli noża, by rozprawić się z trudnościami… i z tortem.

Dwaj panowie, duży i mały, siedzieli w wagonie restauracyjnym pociągu i obaj zamówili rybę. Kiedy kelner przyniósł jedzenie, na jednym talerzu leżała duża ryba, a na drugim – mała. Potężny mężczyzna, obsługiwany w pierwszej kolejności, czym prędzej wziął tę dużą. Jego drobny sąsiad poskarżył się, że to wyjątkowo niegrzeczne.

– W takim razie co pan by zrobił, gdyby to pan miał wybierać pierwszy? – zapytał duży poirytowanym tonem.

– Byłbym uprzejmy i wziąłbym mniejszą rybę – odparł mały triumfująco.

– No i ma pan mniejszą! – rzekł na to duży.

Jak pokazuje ten przedpotopowy dowcip, różni ludzie przypisują rzeczom różną wartość w różnych okolicznościach, a niektórych bardzo trudno zadowolić. Przez ostatnie pięćdziesiąt lat matematycy zmagali się z problemem sprawiedliwego podziału – zazwyczaj formułowanego na przykładzie tortu, nie ryb – a dziś mamy obszerną i zaskakująco głęboką teorię na ten temat. Fascynująca książka Jacka Robertsona i Williama Webba, Cake Cutting Algorithms („Algorytmy krojenia tortu” – zob. „Bibliografia”), stanowi przegląd całego zagadnienia. W tym rozdziale oraz w rozdziale 14. przyjrzymy się pewnym koncepcjom, które wyłoniły się z pozornie tylko prostego pytania: jak podzielić tort, tak aby wszyscy byli zadowoleni z otrzymanego kawałka.

Najprostszy przypadek dotyczy dwóch osób, które – powtórzmy – chcą podzielić się tortem tak, by każda z nich była usatysfakcjonowana i uważała, że dostała tyle, ile jej się należało. Co w tym wypadku oznacza „więcej niż połowę według mojej oceny”, a zainteresowani mogą się nie zgadzać co do wartości danego kawałka. Na przykład: Alice lubi wisienki, zaś Bob woli lukier. Jeden z ciekawych wniosków, jaki wyłonił się z teorii krojenia tortu, mówi, że jest go łatwiej podzielić, kiedy zachodzi taka rozbieżność zdań co do tego, ile warte są jego części. Widać tutaj, że ma to sens, bo możemy dać Bobowi lukier, a Alice wisienki i już jesteśmy na dobrej drodze do zadowolenia ich obojga. Gdyby oboje chcieli dostać lukier, problem byłby trudniejszy.

Przy dwóch graczach nie jest on jednak nigdy szczególnie trudny. Rozwiązanie „Alice kroi, Bob wybiera” było znane już 2800 lat temu! Oboje zainteresowani uznają takie wyjście za sprawiedliwe w tym sensie, że nie mają prawa skarżyć się na końcowy rezultat. Jeśli Alice nie podoba się kawałek, który zostawił Bob, sama jest sobie winna, że nie postarała się bardziej, aby pokroić tort na równe części (według jej subiektywnej oceny). Jeśli Bob nie jest zadowolony ze swojego kawałka, dokonał złego wyboru.

Całe zagadnienie zaczęło się robić ciekawe, kiedy zbadano, co się dzieje przy trójce graczy. Tom, Dick i Harry chcą podzielić tort w taki sposób, aby każdy z nich miał satysfakcję, że dostał co najmniej jedną trzecią, według swojej prywatnej oceny wartości. Zawsze w takich sprawach, nawiasem mówiąc, zakłada się, że tort jest nieskończenie podzielny, chociaż teoria w znacznej części sprawdza się także, jeśli tort ma cenne „atomy” – pojedyncze punkty, którym co najmniej jeden gracz przypisuje wartość niezerową. Dla uproszczenia jednak założę, że nie ma takich atomów. Robertson i Webb przedstawiają ten wariant, analizując prawdopodobną, ale nieprawidłową odpowiedź, która wygląda następująco:

KROK 1: Tom kroi tort na dwie części X i W, gdzie jego zdaniem X ma wartość 1/3, a W – 2/3.

KROK 2: Dick przekraja W na dwa kawałki Y i Z, każdy o wartości – jak uważa Dick – 1/2 W.

KROK 3: Harry wybiera ten z kawałków X, Y i Z, który woli. Następnie Tom decyduje się na któryś z dwóch pozostałych. Dick dostaje ostatni kawałek.

Czy ten algorytm jest sprawiedliwy?

Na pewno Harry będzie zadowolony, bo wybiera pierwszy. Tom też nie będzie narzekać, z nieco bardziej złożonych powodów. Jeśli Harry wybierze X, Tom może wziąć ten z dwóch pozostałych kawałków, który uzna za cenniejszy (lub dowolny, jeśli są w jego oczach równe). Ponieważ uważa, że Y i Z mają razem wartość 2/3, musi sądzić, że przynajmniej jeden z nich jest wart 1/3. A jeśli Harry wybierze Y lub Z, Tom może wziąć X.

Jednak Dick może nie być szczególnie zachwycony rezultatem podziału. Jeśli nie zgadza się z Tomem co do pierwszego cięcia, może uważać, że W ma wartość mniejszą niż 2/3, co oznacza, że usatysfakcjonuje go tylko kawałek X. Ale powiedzmy, że Harry wybierze Y, a Tom X – wtedy Dick musi wziąć Z, którego nie chce.

A zatem powyższy algorytm nie jest sprawiedliwy. Pierwsze prawidłowe rozwiązanie problemu sprawiedliwego podziału tortu pomiędzy trzy osoby podał w 1944 roku Hugo Steinhaus, należący do grupy polskich matematyków, którzy spotykali się regularnie w pewnej lwowskiej kawiarni. Jego metoda wiąże się z zastosowaniem techniki „obkrajania”.

KROK 1: Tom kroi tort na dwa kawałki X i W; w jego ocenie X ma wartość 1/3, a W – 2/3.

KROK 2: Podaje Dickowi kawałek X i prosi, żeby go obkroił, tak aby jego, Dicka, zdaniem stanowił 1/3 całości, jeśli sądzi, że teraz jest większy, a jeśli nie – aby zostawił go tak, jak jest. Nazwijmy kawałek po tej obróbce X*: jest on równy X lub mniejszy.

KROK 3: Dick podaje X* Harry’emu, który może go przyjąć albo nie.

KROK 4: (a) Jeśli Harry zgodził się wziąć kawałek X*, Tom i Dick zbierają resztę wypieku – kawałek W oraz to, co Dick odkroił z X – do kupy i traktują jako jeden (nieco rozbabrany) tort. Po czym dzielą go zgodnie z zasadą „ja kroję, ty wybierasz”. (b) Jeśli Harry nie przyjął kawałka X* i jeśli Dick obkroił X, to Dick bierze X*, a Tom i Harry dzielą resztę na zasadzie „ja kroję, ty wybierasz”. (c) Jeśli Harry nie przyjął kawałka X* i Dick nie obkroił X, to Tom bierze X, a Dick i Harry dzielą się resztą na zasadzie „ja kroję, ty wybierasz”.

To jedna z odpowiedzi – sprawdzenie jej logiki zostawiam czytelnikowi. Zasadniczo uczestnik, który nie jest zadowolony z otrzymanego kawałka, musiał dokonać wcześniej złego wyboru albo źle wymierzył przy krojeniu, a w takim razie może winić tylko siebie.

W 1961 roku Leonard Dubins i Edwin Spanier zaproponowali zupełnie inne rozwiązanie, z wykorzystaniem przesuwającego się noża. Postawmy tort na stole i przesuwajmy nad nim płynnie, stopniowo nóż, od lewej do prawej, zaczynając od samego brzegu. Niech L oznacza część znajdującą się na lewo od noża w danym momencie. Tom, Dick i Harry mają zawołać „Stop!”, kiedy tylko wartość L wyniesie, ich zdaniem, 1/3. Ten, kto krzyknie pierwszy, dostaje L, a pozostali dwaj dzielą się resztą albo zgodnie z zasadą „ja kroję, ty wybierasz”, albo ponownie przesuwając nóż nad tortem i wołając „Stop!”, kiedy tylko wartość w ich subiektywnej ocenie dojdzie do 1/2. (Co powinni zrobić, jeśli obaj krzykną równocześnie? Pomyśl).

Dużą zaletą tej metody jest to, że można ją wykorzystać przy n uczestnikach. Przesuwaj nóż na torcie i każ wszystkim krzyczeć „Stop!”, kiedy tylko L, ich zdaniem, wyniesie 1/n. Osoba, która krzyknie pierwsza, dostaje L, a pozostałych n – 1 graczy powtarza całą procedurę z pozostałą częścią tortu, tyle że oczywiście teraz mają wołać „Stop!”, kiedy uważają, że wartość L wynosi 1/(n – 1)… itd.

Algorytmy z przesuwającym się nożem nigdy mi się szczególnie nie podobały – chyba dlatego, że z reakcjami graczy zawsze wiąże się pewne opóźnienie w czasie. Może najlepiej obejść to zastrzeżenie, przesuwając nóż powoli. Bardzo powoli. Albo założyć, że wszyscy uczestnicy mają superszybki refleks.

Nazwijmy pierwszy typ rozwiązania algorytmem „nieruchomego noża”, a drugi – algorytmem „przesuwającego się noża”. Istnieje algorytm nieruchomego noża dla podziału między trzech uczestników, który także można łatwo rozszerzyć na n graczy. Tom siedzi sobie sam, gapiąc się na „swój” tort, kiedy wpada Dick i prosi o kawałek. Tom kroi więc tort na pół (w swoim mniemaniu), a Dick wybiera jedną z połówek. Zanim zdążą zabrać się do jedzenia, przychodzi Harry i też żąda sprawiedliwego przydziału ciasta. Tom i Dick kroją swoje kawałki na trzy części, które uważają za równe. Harry wybiera jedną cząstkę od Toma i jedną od Dicka. Nietrudno zrozumieć, dlaczego ten algorytm „kolejnych par” się sprawdza, a zastosowanie go przy dowolnej liczbie uczestników jest stosunkowo proste. Metodę okrajania także można rozszerzyć na n graczy, dając każdemu szansę przykrojenia danego kawałka, jeśli są skłonni zaakceptować rezultat; jeśli nikt nie chce go już okroić, kawałek należy uznać za możliwy do przyjęcia przez wszystkich.

Jeśli liczba uczestników jest duża, algorytm kolejnych par wymaga bardzo wielu cięć. W której metodzie potrzeba ich najmniej? Posługując się metodą przesuwającego się noża wykonamy n – 1 cięć, aby uzyskać n kawałków i to najmniej, na ile możemy liczyć. Ale metody nieruchomego noża tak łatwo się nie poddają. Przy n uczestnikach, algorytm okrajania wymaga (n^2 – n)/2 cięć. W przypadku algorytmu kolejnych par liczba cięć wyniesie n! – 1, gdzie n! = n(n – 1)(n – 2)… 3·2·1 to n silnia. To więcej niż przy algorytmie obkrajania (z wyjątkiem przypadku, gdy n = 2).

Jednak okrajanie nie jest najlepszą metodą. Bardziej efektywny algorytm „dziel i zwyciężaj” wygląda następująco: spróbuj przekroić tort jednym cięciem, tak aby mniej więcej połowa uczestników chętnie dostała kawałek z jednej części, a reszta nie miała nic przeciwko uczciwemu podzieleniu się drugą. Powtórz tę samą operację na dwóch uzyskanych „podtortach”. Liczba potrzebnych cięć wynosi tu około n log_2n. Dokładny wzór to nk – 2k + 1, gdzie k to ta unikalna liczba całkowita spełniająca nierówność: 2k–1 < n ≤ 2k. Przypuszczalnie poniżej takiej liczby cięć zejść już się nie da.

Te pomysły mogą w końcu wyjść poza sferę czysto rekreacyjną. W życiu zdarza się wiele sytuacji, w których podział dóbr w sposób, jaki wszyscy zainteresowani uznają za sprawiedliwy, ma istotne znaczenie. Przykładem mogą być negocjacje dotyczące terytoriów i umów handlowych. W zasadzie można w takich sytuacjach zastosować te same metody, co przy rozwiązywaniu problemu krojenia tortu. W rzeczy samej, kiedy po drugiej wojnie światowej podzielono Niemcy w celach administracyjnych pomiędzy aliantów (Stany Zjednoczone, Wielką Brytanię, Francję) oraz Rosję, po pierwszej próbie zostały „resztki” w postaci Berlina, który następnie trzeba było podzielić w odrębnym etapie, więc negocjatorzy intuicyjnie zastosowali zbliżone metody. Podobna kwestia powoduje w tej chwili problemy w stosunkach izraelsko-palestyńskich – rolę głównych „resztek” pełni Jerozolima, a Zachodni Brzeg stanowi kolejną kość niezgody. Czy matematycy zajmujący się problematyką sprawiedliwego podziału mogliby pomóc w negocjacjach? Miło byłoby myśleć, że świat, w którym żyjemy, jest na tyle racjonalny, by dopuścić taką możliwość, ale polityka rzadko działa w ten sposób. Przede wszystkim to, jak ludzie oceniają wartość danej rzeczy, często zmienia się już po dojściu do wstępnego porozumienia, a wtedy omówione tu strategie się nie sprawdzają.

Mimo wszystko może warto byłoby dać szansę racjonalnym metodom.

Uwagi

Dostałem mnóstwo listów dotyczących algorytmów krojenia tortu, od uproszczeń metod omawianych przeze mnie do poważnych artykułów naukowych z nowymi badaniami. Niektórzy czytelnicy próbowali rozwiać moje niejasne poczucie niepokoju w związku z algorytmami „przesuwającego się noża”. Moje wątpliwości budził czas reakcji uczestników. Aby uniknąć tego problemu, proponowano – a propozycje te nieco doszlifowaliśmy w wymienianej korespondencji – by zamiast przesuwać nóż nad tortem gracze powinni zaznaczać na nim (lub na modelu w mniejszej skali) słuszne ich zdaniem linie podziału. Najpierw należy wybrać kierunek (na przykład północ-południe), a potem poprosić kolejno każdego z n graczy, by zaznaczył na torcie linię północ–południe w najbardziej na zachód wysuniętym miejscu, dla którego jest gotowy przyjąć kawałek znajdujący się na zachód od wyznaczonej linii. (Czyli powinien wyznaczyć kawałek, którego „wartość” będzie wynosić 1/n). Osoba, która zaznaczyła linię leżącą najdalej na zachód, odkrawa sobie część po lewej stronie tej linii i kończy grę. Dalej postępujemy w ten sam sposób. Szybkość reakcji zostaje zastąpiona kolejnością cięć, licząc od zachodu na wschód. Tę samą koncepcję można wykorzystać we wszystkich metodach przesuwającego się noża.

Wydawało się, że moje zastrzeżenia dotyczące algorytmów tego typu były nieuzasadnione. Ale niedługo potem napisał do mnie Steven Brams z Uniwersytetu Nowojorskiego, ekspert od takich spraw, pokazując, że nie można tak łatwo odrzucić moich pierwotnych wątpliwości. Brams, Alan D. Taylor i William S. Zwicker analizują procedury przesuwającego się noża w dwóch artykułach, wymienionych w „Bibliografii”. W drugim przedstawiają procedurę tego typu dla niewywołującego zazdrości (ang. envy-free) podziału pomiędzy czterech graczy, do którego potrzeba najwyżej 11 cięć.

Nie jest jednak znana żadna procedura dyskretna, czyli nieciągła, z ograniczoną liczbą cięć (chociażby bardzo dużą) dla czterech graczy i prawdopodobnie taka metoda nie istnieje. Z pewnością procedura nie stanie się dyskretna, jeśli zamiast przesuwania noża zastosujemy zaznaczanie linii na torcie. Zatem redukowanie metod przesuwającego się noża do stawiania znaczników sprawdza się w niektórych przypadkach – ale nie we wszystkich.

Rozdział 2

Uchylanie prawa średnich

dostępne w pełnej wersji

Rozdział 3

Arytmetyka i stare sznurówki

dostępne w pełnej wersji

Rozdział 4

Paradoks utracony

dostępne w pełnej wersji

Rozdział 5

Okrągłe sardynki w ciasnej puszce

dostępne w pełnej wersji

Rozdział 6

Niekończąca się partia szachów

dostępne w pełnej wersji

Rozdział 7

Quody i kwazary

dostępne w pełnej wersji

Rozdział 8

Protokoły wiedzy zerowej

dostępne w pełnej wersji

Rozdział 9

Imperia na Księżycu

dostępne w pełnej wersji

Rozdział 10

Imperia i elektronika

dostępne w pełnej wersji

Rozdział 11

Porządkujące tasowanie

dostępne w pełnej wersji

Rozdział 12

Bańki dmuchaj, bulgocz ogniu, kotle buchaj

dostępne w pełnej wersji

Rozdział 13

Przecinające się tory w fabryce cegieł

dostępne w pełnej wersji

Rozdział 14

Podział bez zazdrości

dostępne w pełnej wersji

Rozdział 15

Wściekle świecące świetliki

dostępne w pełnej wersji

Rozdział 16

Dlaczego kable telefoniczne się plączą?

dostępne w pełnej wersji

Rozdział 17

Wszechobecna uszczelka Sierpińskiego

dostępne w pełnej wersji

Rozdział 18

Broń Cesarstwa Rzymskiego!

dostępne w pełnej wersji

Rozdział 19

Triangulacja na wynos

dostępne w pełnej wersji

Rozdział 20

Wielkanoc jest kwazikryształem

dostępne w pełnej wersji

Bibliografia

dostępne w pełnej wersji

Spis treści

Wstęp

Rysunki – podziękowanie i prawa autorskie

Rozdział 1. Twoja połowa jest większa od mojej!

Rozdział 2. Uchylanie prawa średnich

Rozdział 3. Arytmetyka i stare sznurówki

Rozdział 4. Paradoks utracony

Rozdział 5. Okrągłe sardynki w ciasnej puszce

Rozdział 6. Niekończąca się partia szachów

Rozdział 7. Quody i kwazary

Rozdział 8. Protokoły wiedzy zerowej

Rozdział 9. Imperia na Księżycu

Rozdział 10. Imperia i elektronika

Rozdział 11. Porządkujące tasowanie

Rozdział 12. Bańki dmuchaj, bulgocz ogniu, kotle buchaj

Rozdział 13. Przecinające się tory w fabryce cegieł

Rozdział 14. Podział bez zazdrości

Rozdział 15. Wściekle świecące świetliki

Rozdział 16. Dlaczego kable telefoniczne się plączą?

Rozdział 17. Wszechobecna uszczelka Sierpińskiego

Rozdział 18. Broń Cesarstwa Rzymskiego!

Rozdział 19. Triangulacja na wynos

Rozdział 20. Wielkanoc jest kwazikryształem

Bibliografia