Jak pokroić tort i inne zagadki matematyczne

ł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ś 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,