REKREACJE MATEMATYCZNE

Ian Stewart

W

zesz∏ym miesiàcu rozwa˝ali-
Êmy problemy matematyczne,
b´dàce implikacjà zwodniczo

prostego zadania sprawiedliwego podzie-
lenia tortu – tzn. takiego, aby ka˝da z n
osób uczestniczàcych w przyj´ciu by∏a
przekonana, ˝e otrzyma∏a co najmniej

1

/

n

ca∏oÊci. Teraz rozwa˝ymy kilka podob-
nych pytaƒ, które zapoczàtkowa∏y roz-
wój nowoczesnych elementów tej teorii.

Zacznijmy od krótkiego przypomnie-

nia. W przypadku dwóch osób do spra-
wiedliwego podzia∏u prowadzi trady-
cyjne „ja dziel´, ty wybierasz”. Dla
trzech lub wi´cej mamy kilka sposobów.
W metodzie „przycinania” pozwala si´
kolejnym uczestnikom podzia∏u zmniej-
szaç wielkoÊç odci´tej cz´Êci tortu z za-
strze˝eniem, ˝e dany kawa∏ek dostaje
osoba, która kroi∏a go ostatnia. W algo-
rytmie „kolejnych par” dwie osoby dzie-
là tort na po∏owy, a trzecia otrzymuje
od nich w drodze osobnych negocjacji
takie dwie cz´Êci, które uwa˝a przynaj-
mniej za jednà trzecià ich kawa∏ków.
Natomiast w metodzie „dziel i rzàdê”
uczestnicy próbujà podzieliç tort na po-
∏ówki jednym ci´ciem, tak aby mniej
wi´cej po∏owa osób uzna∏a ka˝dà z tych

cz´Êci za co najmniej po∏ow´. Podobnie
post´puje si´ z ka˝dà z cz´Êci otrzyma-
nych w pierwszym kroku itd.

Wszystkie wymienione algorytmy

prowadzà do sprawiedliwego podzia-
∏u, ale wyst´puje tu jeszcze bardziej sub-
telne zagadnienie. Nawet je˝eli ka˝da
z osób jest przekonana, ˝e otrzyma∏a
przynajmniej

1

/

n

ca∏oÊci, ktoÊ mo˝e czuç

si´ oszukany, a to z powodu Êmiertel-
nego grzechu zazdroÊci. Na przyk∏ad
Tomek, Piotr i Krzysztof b´dà uwa˝aç,
˝e dostali co najmniej po jednej trzeciej
tortu, Tomek jednak˝e mo˝e sàdziç, ˝e
Piotr dosta∏ wi´kszy kawa∏ek. Tomek
zosta∏ obdarowany „sprawiedliwie”,
a mimo to nie jest zadowolony. Powie-
my, ˝e podzia∏ tortu jest „bezzawistny”,
gdy nikt nie uwa˝a cudzych kawa∏ków
za wi´ksze od swojego. Podzia∏ bezza-
wistny jest zawsze sprawiedliwy, ale
nie ka˝dy podzia∏ sprawiedliwy jest
bezzawistny. Trudniej zatem znaleêç al-
gorytm podzia∏u bezzawistnego ni˝
sprawiedliwego.

OczywiÊcie jeÊli uczestników podzia-

∏u jest dwóch, sposób „ja dziel´, ty wybie-
rasz” jest bezzawistny, ale ˝aden z in-
nych wspomnianych algorytmów ju˝ nie.

Bezzawistny algorytm dla trzech osób

znaleêli na poczàtku lat szeÊçdziesià-
tych John Selfridge i John H. Conway.

KROK 1: Tomek kroi tort na takie trzy

cz´Êci, które uwa˝a za jednakowe.

KROK 2: Piotr mo˝e albo (a) nie robiç

nic, gdy uwa˝a, ˝e co najmniej dwie cz´-
Êci sà równe i nie mniejsze ni˝ trzecia, al-
bo (b) przyciàç najwi´kszà cz´Êç w taki
sposób, by uzyskaç równoÊç dwu naj-
wi´kszych cz´Êci okreÊlonà w punkcie
(a). Od∏ó˝my na bok wszystko, co zosta-
∏o odci´te, i nazwijmy „pozosta∏oÊcià”.

KROK 3: Krzysztof, Piotr i Tomek,

w tej kolejnoÊci, wybierajà po kawa∏ku
– takim, który uwa˝ajà albo za najwi´k-
szy, albo za nie mniejszy od najwi´k-
szego. JeÊli Piotr przycina∏ jakiÊ kawa∏ek
w kroku 2, to musi go wziàç, oczywi-
Êcie pod warunkiem, ˝e Krzysztof nie
zrobi∏ tego wczeÊniej.

W tym momencie cz´Êç tortu zosta∏a

ju˝ podzielona w bezzawistny sposób.
Pozostaje zatem podzieliç tak samo po-
zosta∏oÊç.

KROK 4: JeÊli Piotr nie robi∏ nic w kro-

ku 2, to nie ma pozosta∏oÊci i ca∏y tort jest
ju˝ podzielony. JeÊli przycina∏, to któryÊ
z dwójki – Piotr lub Krzysztof – wzià∏ ten
przyci´ty kawa∏ek. PrzypuÊçmy, ˝e by∏
to Piotr (je˝eli natomiast Krzysztof, to za-

mieƒmy ich rolami). Teraz Piotr dzieli
resztk´ na takie trzy cz´Êci, które uwa˝a
za równe.

KROK 5: Krzysztof, Piotr i Tomek,

znów zachowujàc t´ kolejnoÊç, wybiera-
jà po kawa∏ku. Krzysztof wybiera
pierwszy i nie ma powodu zazdroÊciç
innym. Tomek nie b´dzie zazdroÊciç
Krzysztofowi, niezale˝nie od podzia∏u
resztki, poniewa˝ Krzysztof mo˝e do-

staç co najwy˝ej t´ cz´Êç, którà Tomek

Podzia∏ posiad∏oÊci nad jeziorem

dokonany przez jednà osob´

Trzy osoby zadowolone,

zosta∏a reszta

Pi´ç osób zadowolonych, zosta∏a reszta

MATT COLLINS

JEZIORO

DROGA

Jak dzieliç, nie wzbudzajàc zazdroÊci?

TOMEK
PIOTR
KRZYSZTOF
KRYSTYNA
BARBARA

Â

WIAT

N

AUKI

Marzec 1999 87

w pierwszym kroku uzna∏ za jednà trze-
cià. Nie b´dzie tak˝e zazdroÊci∏ Piotro-
wi, bo wybiera przed nim. Piotr nie ma
podstaw do uskar˝ania si´, bo to on
dzieli∏ pozosta∏oÊç.

W tym punkcie teoria utkn´∏a na 30

lat. Czy istnieje bezzawistny sposób po-
dzia∏u tortu pomi´dzy n osób? W roku
1995 Steven J. Brams z New York Uni-
versity i Alan D. Taylor z Union College
odkryli zadziwiajàcà metod´ takiego
podzia∏u dla dowolnej ich liczby. Jest ona
naprawd´ skomplikowana i tutaj jej nie
przytocz´; polecam zajrzenie albo do ar-
tyku∏u „An Envy-Free Cake Division
Protocol” (Sposób bezzawistnego podzia-
∏u tortu) w American Mathematical Month-
ly (vol. 102, styczeƒ 1995), albo do cu-
downej ksià˝ki Jacka Robertsona i Wil-
liama Webba Cake Cutting Algorithms (Al-
gorytmy podzia∏u tortu) (A. K. Peters;
Natick, Massachusetts 1998).

Jednym z najbardziej interesujàcych

elementów teorii podzia∏u tortu jest to,
co Robertson i Webb nazywajà „szcz´-
Êliwym trafem wystàpienia niezgodno-
Êci”. Na pierwszy rzut oka mog∏oby si´
wydawaç, ˝e podzia∏ sprawiedliwy jest
naj∏atwiejszy, gdy wszyscy w nim
uczestniczàcy sà zgodni co do wartoÊci
ka˝dego kawa∏ka – przynajmniej nie ma
wtedy sporów o to, jak cenna jest ka˝da
porcja. W rzeczywistoÊci jest odwrot-
nie: najproÊciej jest zadowoliç uczestni-
ków niezgodnych w ocenach.

PrzypuÊçmy, ˝e na przyk∏ad Tomek

i Piotr stosujà metod´ „ja dziel´, ty wy-
bierasz”. Tomek kroi tort na dwa ka-
wa∏ki, które uwa˝a za po∏owy. JeÊli Piotr
jest usatysfakcjonowany, nie trzeba ro-
biç nic wi´cej. Ale przypuÊçmy, ˝e Piotr
uzna∏ te cz´Êci za

3

/

5

i

2

/

5

ca∏oÊci. Wów-

czas mo˝e z jakichÊ altruistycznych
powodów oddaç Tomkowi

1

/

12

tego

kawa∏ka, który uwa˝a za wi´kszy
(oceniajàc jà jako

1

/

20

ca∏oÊci). Zgodnie

z jego szacunkiem zostanie mu wtedy

3

/

5

–

1

/

20

=

11

/

20

tortu. Jeden ze sposo-

bów, w jaki mo˝e to zrobiç, polega na
pokrojeniu wi´kszej cz´Êci na 12 rów-
nych (wed∏ug niego) kawa∏ków i zapro-
ponowaniu Tomkowi wybrania dowol-
nego z nich.

Niezale˝nie od tego, który kawa∏ek To-

mek wybierze, zdaniem Piotra dostanie
∏àcznie

11

/

20

ca∏oÊci. Tomek natomiast

stoi przed wyborem jednej z 12 cz´Êci,
których ∏àcznà wartoÊç ocenia jako

1

/

2

.

A zatem któràÊ z tych porcji musi uznaç
za co najmniej

1

/

24

ca∏oÊci. Gdy jà wybie-

rze, ∏àcznie otrzyma

13

/

24

tortu. Tak wi´c

zarówno Tomek, jak i Piotr b´dà przeko-
nani, ˝e dostali wi´cej ni˝ po po∏owie.

1

W tym przypadku nie wydaje si´, ˝e

niezgodnoÊç co do wartoÊci poszczegól-

nych cz´Êci musi prowadziç do sporów
o to, jaki podzia∏ jest sprawiedliwy. Sy-
tuacja mog∏aby wyglàdaç inaczej, gdy-
by tort podzieli∏ trzeci uczestnik i nale-
ga∏, by Tomek i Piotr zaakceptowali te
z góry ustalone cz´Êci.

Z innym przyk∏adem zastosowania

tej zasady mamy do czynienia podczas
podzia∏u kawa∏ka ziemi przylegajàcej
do jeziora. PrzypuÊçmy, ˝e nad jezio-
rem prosta droga prowadzi ze wscho-
du na zachód, a kawa∏ek gruntu pomi´-
dzy drogà a jeziorem ma byç podzielony
liniami biegnàcymi z pó∏nocy na po∏u-
dnie. Zadanie polega na takim podzia-
le tego kawa∏ka pomi´dzy n osób, aby
ka˝da otrzyma∏a cz´Êç pomi´dzy jezio-
rem a drogà i by∏a przekonana, ˝e jest
to co najmniej

1

/

n

ca∏oÊci.

Rozwiàzanie jest dziecinnie proste.

Trzeba zrobiç zdj´cie lotnicze tego obsza-
ru i poprosiç ka˝dego z zainteresowanych
o narysowanie linii z pó∏nocy na po∏u-
dnie w taki sposób, aby w jego ocenie po-
dzieli∏y one grunt na n parceli równej war-
toÊci [górna ilustracja z lewej na poprzedniej
stronie]. JeÊli wszyscy narysujà linie w tych
samych miejscach, to b´dà zadowoleni
z dowolnej cz´Êci. JeÊli wystàpià niezgod-
noÊci co do przebiegu granic, mo˝na tak
podzieliç ca∏y obszar, by wszyscy byli za-
dowoleni i zosta∏a jeszcze resztka. Na
poprzedniej stronie na rysunku z prawej
u góry pokazano typowà sytuacj´ – To-
mek, Piotr i Krzysztof poprowadzili swo-
je linie. OczywiÊcie mo˝emy pozwoliç
Tomkowi wziàç pierwszà parcel´ z jego

podzia∏u, Piotrowi – drugà z podzia∏u
Piotra, a Krzysztofowi trzecià z jego w∏a-
snego podzia∏u – i jeszcze zostanie kilka
kawa∏ków.

Na du˝ym rysunku pokazano sytuacj´

bardziej skomplikowanà, kiedy ka˝da
z pi´ciu osób: Tomek, Piotr, Krzysztof,
Krystyna i Barbara, stara si´ o

1

/

5

ca∏oÊci.

W roku 1969 Hugo Steinhaus udowod-
ni∏, ˝e to samo dzieje si´ w przypadku do-
wolnego wyboru linii dzielàcych, kiedy
wyst´puje choçby najmniejsza niezgod-
noÊç ocen. W dowodzie wykorzystuje si´
indukcj´ matematycznà, a mo˝na go zna-
leêç w ksià˝ce Robertsona i Webba.

2

Niestety, nie wszystko da si´ podzieliç

sprawiedliwie, gdy chcemy zachowaç
rozsàdne ograniczenia. Rozwa˝my na
przyk∏ad zmywanie. JeÊli ka˝dy musi
umyç i/lub wytrzeç ca∏y talerz, to w sy-
tuacjach ekstremalnych ˝aden sprawie-
dliwy podzia∏ nie jest mo˝liwy. Wyobraê-
my sobie dwóch zmywajàcych i dwa
talerze – du˝y i ma∏y. Obaj b´dà chcieli
zajàç si´ ma∏ym. A zatem nawet w do-
skona∏ym Êwiecie, w którym ka˝dy spór
jest rozwiàzywany w negocjacjach, nie-
których konfliktów nie da si´ uniknàç.

T∏umaczy∏

Tomasz ˚ak

Przypisy t∏umacza:

1

Zjawisko to zauwa˝y∏ Bronis∏aw Knaster w latach

czterdziestych – porównaj „Rekreacje matematycz-
ne” z poprzedniego miesiàca.

2

Ten sposób parcelacji mo˝na znaleêç w ksià˝ce Hu-

gona Steinhausa Kalejdoskop matematyczny (wyd. IV,
WSiP, Warszawa 1989, ss. 73-74). To w∏aÊnie on wy-
myÊli∏ podzia∏ sprawiedliwy, nazwany przez niego
pragmatycznym. Podany w tekÊcie rok 1969 to da-
ta kolejnego amerykaƒskiego wydania Kalejdoskopu.

W

odcinku z czerwca 1998 zatytu∏owanym „Zniesienie prawa Êrednich” wspomnia-
∏em, ˝e dla dwuwymiarowego spaceru losowego po kwadratowej kracie praw-

dopodobieƒstwo powrotu do punktu wyjÊcia jest równe 1, ale dla spaceru po kra-
cie szeÊciennej w trzech wymiarach jest mniejsze od 1 i wynosi oko∏o 0.35. Opar∏em
si´ na I tomie ksià˝ki Williama Fellera An Introduction to Probability Theory and Its
Applications

(edycja polska: Wst´p do rachunku prawdopodobieƒstwa, wyd. III

zmienione. PWN, Warszawa 1977). Kilku czytelników zwróci∏o uwag´, ˝e liczba
podana przez Fellera nie jest zbyt dok∏adna. David Kilbridge z San Francisco twier-
dzi, ˝e w roku 1939 angielski matematyk George N. Watson poda∏ wartoÊç

1 – 1/[3(18 + 12

Ö-

2

– 10

Ö-

3

– 7

Ö-

6

) (K(2

Ö-

3

+

Ö-

6

– 2

Ö-

2

– 3))]

2

,

gdzie K(z) jest iloczynem

2

/

p oraz pe∏nej ca∏ki eliptycznej pierwszego rodzaju z mo-

du∏em z

2

. (JeÊli nie wiesz, co to jest, prawdopodobnie nie chcesz wiedzieç! Dla

porzàdku jednak wyjaÊniam, ˝e funkcje eliptyczne sà wspania∏ym klasycznym uogól-
nieniem funkcji trygonometrycznych, takich jak sinus i cosinus; by∏y bardzo modne
sto lat temu, a i dziÊ sà obiektem zainteresowania w kilku dziedzinach matematy-
ki, rzadko jednak wspomina si´ o nich studentom.) WartoÊç liczbowa tego wyra˝e-
nia jest równa oko∏o 0.340537329551.

Kilbridge odpowiedzia∏ tak˝e na moje pytanie o prawdopodobieƒstwo ponowne-

go zrównania si´ liczb pojawieƒ poszczególnych Êcian kostki. Wynosi ono w przy-
bli˝eniu 0.022. Dla kostek o 2, 3, 4 lub 5 Êcianach prawdopodobieƒstwo to wyno-
si mniej wi´cej odpowiednio 1, 1, 0.222 oraz 0.066. Yuichi Tanaka, redaktor japoƒskiej
edycji Scientific American, na komputerze policzy∏ prawdopodobieƒstwo powrotu
do punktu wyjÊcia dla kraty czterowymiarowej. Po trzech dniach program poda∏
przybli˝ony wynik 0.193201673. (Czy istnieje wzór podobny do formu∏y Watsona?
SpecjaliÊci od funkcji eliptycznych, odezwijcie si´!)

SPRZ¢˚ENIE ZWROTNE