88 Â
WIAT
N
AUKI
Luty 1999
W
wagonie restauracyjnym sie-
dzieli dwaj m´˝czyêni, du˝y
i ma∏y, i obaj zamówili ryb´.
Gdy kelner przyniós∏ obiad, du˝y bez
wahania si´gnà∏ po wi´kszà porcj´.
Ma∏y zwróci∏ mu uwag´, ˝e by∏o to wy-
jàtkowo niegrzeczne.
– A co by pan zrobi∏, gdyby to pan
wybiera∏ pierwszy? – zapyta∏ rozdra˝-
niony du˝y.
– By∏bym uprzejmy i wybra∏bym
mniejszà ryb´ – odpar∏ ma∏y tonem
pe∏nym wy˝szoÊci.
– Ale˝ w∏aÊnie jà pan dosta∏!
Ten stary dowcip Êwiadczy, ˝e nie-
których ludzi trudno zadowoliç.
Przez ostatnich 50 lat matematycy
zmagajà si´ z zagadnieniem sprawiedli-
wego podzia∏u, formu∏owanym zwykle
w odniesieniu do tortu, a nie ryby. Jack
Robertson i William Webb opublikowa-
li ostatnio fascynujàcà ksià˝k´ na ten te-
mat – Cake Cutting Algorithms (Algoryt-
my dzielenia tortu; A. K. Peters, Natick,
Massachusetts, 1998).
W tym oraz w nast´pnym numerze
przyjrzymy si´ kilku rozwiàzaniom
tego zwodniczo prostego zadania: po-
krojenia tortu tak, aby wszyscy byli
zadowoleni.
Najprostszy przypadek dotyczy
dwóch osób, które chcà tak podzieliç si´
specja∏em, aby ka˝da z nich czu∏a si´
potraktowana sprawiedliwie. „Sprawie-
dliwie” oznacza w tym przypadku, ˝e
dosta∏a ,,pó∏ lub wi´cej wed∏ug swojej
oceny”, a obdarowani mogà ró˝nie oce-
niaç wartoÊç poszczególnych kawa∏ków.
Na przyk∏ad Alicja woli wisienki, a Bo-
lek lukier. Co ciekawe, proÊciej jest po-
dzieliç tort pomi´dzy osoby, które ró˝-
nie oceniajà wartoÊç tych samych porcji.
¸atwo zauwa˝yç, ˝e jest tak napraw-
d´ – Bolkowi mo˝na daç bowiem wtedy
lukier, a Alicji wiÊnie; to krok na dro-
dze do usatysfakcjonowania obojga.
Gdyby oboje woleli lukier, podzia∏ by∏-
by trudniejszy.
Zagadnienie jest jednak niezbyt
skomplikowane, gdy chodzi o dwie oso-
by. Rozwiàzanie ,,Alicja dzieli, Bolek wy-
biera” ludzkoÊç zna od ponad 2800 lat!
Jest ono sprawiedliwe w tym sensie, ˝e
ani Alicja, ani Bolek nie mogà uskar˝aç
si´ na wynik. JeÊli Alicji nie podoba si´
kawa∏ek, który zostawi jej Bolek, mo˝e
mieç pretensje tylko do siebie – nie po-
dzieli∏a tortu na dwie równe, zgodnie
ze swojà ocenà, cz´Êci. Je˝eli Bolek nie
jest zadowolony ze swego kawa∏ka –
dokona∏ z∏ego wyboru.
Problem staje si´ interesujàcy dopiero
w przypadku trzech osób. Na poczàtek
Robertson i Webb analizujà rozwiàza-
nia pozornie s∏uszne, ale niepoprawne.
Tomek, Piotr i Krzysztof chcà pokroiç
tort w taki sposób, aby ka˝dy z nich by∏
przekonany, ˝e otrzyma∏ przynajmniej
jednà trzecià. Nawiasem mówiàc, za-
k∏ada si´, ˝e tort jest nieskoƒczenie
podzielny (jakkolwiek du˝a cz´Êç tej
teorii dotyczy przypadku, gdy tort ma
wartoÊciowe ,,atomy” – pojedyncze
punkty, którym przynajmniej jedna
z osób przypisuje niezerowà wartoÊç).
Algorytm wyglàda nast´pujàco:
KROK 1: Tomek kroi tort na dwie cz´-
Êci x i w, b´dàc przekonany, ˝e x jest
1
/
3
,
a w
2
/
3
ca∏oÊci.
KROK 2: Piotr kroi w na takie dwie
cz´Êci y oraz z, które uwa˝a za po∏owy w.
KROK 3: Krzysztof wybiera spomi´-
dzy x, y i z. Nast´pnie Tomek wybiera
jeden z dwóch pozosta∏ych kawa∏ków.
Piotrowi przypada w udziale ostatni.
Jasne, ˝e Krzysztof b´dzie zadowolo-
ny, bo wybiera pierwszy. Tomek jest tak-
˝e zadowolony, choç z bardziej z∏o˝onych
powodów. JeÊli Krzysztof wybierze cz´Êç
x, Tomek mo˝e wybraç t´ spoÊród y i z,
którà uwa˝a za cenniejszà. Poniewa˝ jest
przekonany, ˝e obie sà w sumie warte
2
/
3
,
musi wi´c jednà z nich oceniaç jako przy-
najmniej
1
/
3
. Je˝eli zaÊ Krzysztof wybie-
rze y lub z, Tomek mo˝e wziàç x.
Jednak˝e Piotr nie musi byç zadowo-
lony. Je˝eli nie zgadza si´ z Tomkiem
co do pierwszego podzia∏u, mo˝e sà-
dziç, ˝e w jest warte mniej ni˝
2
/
3
, czyli
satysfakcjonowa∏by go tylko kawa∏ek x.
Ale Krzysztof móg∏ wybraç, powiedz-
my, y, a Tomek x, Piotr musi wi´c wziàç
z – kawa∏ek, którego nie chce.
Pierwszy sposób sprawiedliwego
podzia∏u znalaz∏ w 1944 roku Hugo
Steinhaus*, jeden z cz∏onków grupy
polskich matematyków, którzy przed
wojnà regularnie spotykali si´ w kawiar-
ni ,,Szkockiej” we Lwowie. W swej me-
todzie korzysta z techniki nazwanej
,,przycinaniem”.
KROK 1: Tomek kroi tort na dwie cz´-
Êci x i w, uwa˝ajàc, ˝e x jest
1
/
3
, a w
stanowi
2
/
3
ca∏oÊci.
REKREACJE MATEMATYCZNE
Ian Stewart
Twoja po∏owa jest wi´ksza!
PODZIA¸ TORTU pomi´dzy kilka osób w taki sposób, by ka˝dy by∏ zadowolony,
wymaga skomplikowanego algorytmu.
MATT COLLINS
KROK 2: Przekazuje cz´Êç x Piotrowi
i prosi o takie jej przyci´cie, aby wed∏ug
Piotra stanowi∏a
1
/
3
tortu, je˝eli jest war-
ta wi´cej, lub pozostawienie jej, jeÊli jest
warta mniej. Nazwijmy t´ cz´Êç x’; jest
ona równa x lub od niej mniejsza.
KROK 3: Piotr przekazuje porcj´ x’
Krzysztofowi, który mo˝e jà wziàç albo
z niej zrezygnowaç.
KROK 4: (a) JeÊli Krzysztof weêmie
x’, to Tomek i Piotr ∏àczà wszystko, co
zosta∏o – w oraz odci´tà cz´Êç x – i trak-
tujàc to jako nowà ca∏oÊç, stosujà meto-
d´ „ja dziel´, ty wybierasz”.
(b) JeÊli Krzysztof nie weêmie x’,
a Piotr przycina∏ x, to Piotr bierze x’,
a Tomek i Krzysztof dzielà reszt´ me-
todà ,,ja dziel´, ty wybierasz”.
(c) JeÊli Krzysztof nie weêmie x’,
a Piotr jej nie przycina∏, to Tomek bie-
rze x, a Piotr i Krzysztof dzielà reszt´
metodà ,,ja dziel´, ty wybierasz”.
To jedno z rozwiàzaƒ – pozostawiam
czytelnikom sprawdzenie jego popraw-
noÊci. Podstawà jest fakt, ˝e ka˝dy, kto
nie jest zadowolony ze swojej cz´Êci,
musia∏ albo êle wybraç, albo êle przy-
ciàç w którymÊ z poprzednich kroków,
mo˝e wi´c winiç tylko siebie.
W 1961 roku Lester E. Dubins i Edwin
H. Spanier przedstawili rozwiàzanie
wykorzystujàce przesuwanie no˝a.
Zróbmy tak, aby nó˝ przesuwa∏ si´ jed-
nostajnie nad tortem, poczàwszy od le-
wej strony. Niech l oznacza zawsze
cz´Êç tortu na lewo od no˝a.
Ka˝dy z uczestników podzia∏u mo˝e
zawo∏aç ,,stop!” w momencie, w którym
wed∏ug niego cz´Êç l osiàgnie
1
/
3
. Pierw-
szy z wo∏ajàcych dostaje l, pozostali
dzielà reszt´ albo metodà ,,ja dziel´, ty
wybierasz”, albo znowu przesuwajàc
nó˝ do momentu, w którym jeden z nich
krzyknie ,,stop!”, bo wydaje mu si´, ˝e
na lewo od no˝a jest ju˝
1
/
2
. (Co powin-
ni zrobiç, gdy powiedzà ,,stop” równo-
czeÊnie? PrzemyÊl to.)
T´ metod´ ∏atwo uogólniç na przy-
padek n osób. Przesuwajmy nó˝ nad
tortem i powiedzmy wszystkim, ˝e majà
zawo∏aç, gdy tylko l osiàgnie wed∏ug
ich szacunku
1
/
n
. Pierwsza osoba, któ-
ra to zrobi, dostaje l, a pozosta∏e n – 1
osób powtarza t´ procedur´ z resztà tor-
tu, przy czym oczywiÊcie teraz wo∏ajà,
gdy ocenià, ˝e cz´Êç l osiàgn´∏a wiel-
koÊç
1
/
(n – 1)
itd.
Musz´ przyznaç, ˝e opóêniona reak-
cja biesiadników sprawia, i˝ algorytmy,
w których korzysta si´ z przesuwania
no˝a, nie bardzo mi si´ podobajà. Naj-
lepszym sposobem omini´cia tej trud-
noÊci jest powolne przesuwanie no˝a.
Bardzo powolne.
Pierwsze z opisanych sposobów na-
zwijmy algorytmami nieruchomego no-
˝a, drugie natomiast algorytmami prze-
suwajàcego si´ no˝a. Istnieje algorytm
nieruchomego no˝a dzielàcy tort pomi´-
dzy trzy osoby, ale dajàcy si´ ∏atwo
uogólniç na n osób. Tomek siedzi sam,
gapiàc si´ na ,,swój” tort, gdy nagle zja-
wia si´ Piotr i prosi o nale˝nà porcj´.
Tomek kroi zatem tort na cz´Êci, które
uwa˝a za po∏owy, a Piotr wybiera. Za-
nim zacznà jeÊç, zjawia si´ Krzysztof
i domaga si´ swojego kawa∏ka. Tomek
i Piotr niezale˝nie dzielà swoje porcje
na trzy cz´Êci, które uwa˝ajà za jednako-
wo wartoÊciowe. Krzysztof bierze sobie
jednà od Tomka i jednà od Piotra.
Nietrudno zauwa˝yç, dlaczego ten
algorytm kolejnych par dzia∏a, a jego
uogólnienie na przypadek dowolnej
liczby osób jest stosunkowo proste. Me-
tod´ przycinania tak˝e mo˝na rozsze-
rzyç na przypadek n osób, pozwalajàc
na przyci´cie kawa∏ka ka˝demu, kto
zgodzi si´ go potem wziàç.
Który sposób wymaga mniejszej licz-
by ci´ç? W metodzie poruszajàcego si´
no˝a, by otrzymaç n kawa∏ków, wyko-
nuje si´ n – 1 ci´ç, i jest to w ogóle naj-
mniejsza mo˝liwa ich liczba. Metody
nieruchomego no˝a wymagajà wi´kszej
liczby ci´ç. Dla n osób uogólniony algo-
rytm przycinania wymaga (n
2
+ n)/2
ci´ç, a algorytm kolejnych par n! – 1 ci´ç,
gdzie n! = n(n – 1)(n – 2)...3 x 2 x 1 jest
symbolem silni. Liczba ta jest wi´ksza
od liczby ci´ç w algorytmie przycina-
nia – oprócz przypadku n = 2.
Bardziej efektywnà metodà nierucho-
mego no˝a jest algorytm „dziel i rzàdê”,
który dzia∏a mniej wi´cej tak: dzielimy tort
jednym ci´ciem w taki sposób, aby mniej
wi´cej po∏owa osób uzna∏a jednà z cz´Êci
za lepszà, po∏owa natomiast – drugà. Na-
st´pnie post´pujemy tak samo z oby-
dwoma kawa∏kami tortu. W tym przy-
padku potrzeba oko∏o n log
2
n ci´ç. Do-
k∏adnie potrzeba ich nk – 2k + 1, gdzie
k jest jedynà liczbà ca∏kowità spe∏niajà-
cà nierównoÊç 2
k – 1
< n ≤ 2
k
. Jest to naj-
mniejsza liczba ci´ç w metodzie nieru-
chomego no˝a.
W zasadzie podobne metody podzia-
∏u mo˝na tak˝e stosowaç w pewnych sy-
tuacjach ˝yciowych. Gdy Niemcy by∏y
dzielone na strefy okupacyjne pomi´dzy
aliantów i Rosj´, pierwsza próba podzia-
∏u pozostawi∏a resztk´ – Berlin – którà
trzeba by∏o si´ zajàç w oddzielnym po-
st´powaniu. I wtedy uk∏adajàce si´ stro-
ny podÊwiadomie zastosowa∏y metod´
podzia∏u tortu. Obecnie podobny pro-
blem powoduje napi´cie w stosunkach
izraelsko-palestyƒskich. Jerozolima jest
g∏ównà ,,pozosta∏oÊcià”, a Zachodni
Brzeg stanowi osobnà koÊç niezgody.
Czy matematyka sprawiedliwego po-
dzia∏u pomaga w negocjacjach? Przy-
jemna by∏aby ÊwiadomoÊç, ˝e ˝yjemy
w Êwiecie, w którym ludzie majà dosta-
tecznie du˝o rozsàdku, ˝eby stosowaç
takie podejÊcie.
T∏umaczy∏
Tomasz ˚ak
* Hugo Steinhaus nie tylko rozwiàza∏, ale i postawi∏
ten problem. Podany przez niego sposób, zamiesz-
czony w ksià˝ce Kalejdoskop matematyczny (WSiP,
Warszawa 1989, ss. 73–74 i przypis na s. 292) ró˝ni
si´ od opisanego w tekÊcie. Gdy Steinhaus przed-
stawi∏ zagadnienie dwóm innym polskim mate-
matykom, Bronis∏awowi Knasterowi i Stefanowi
Banachowi, wymyÊlili oni „przycinanie” i rozwià-
zali zadanie dla dowolnej liczby osób – to w∏aÊnie
ich metoda (tam˝e, 69–70 i 292) opisana jest powy-
˝ej. Knaster zauwa˝y∏ te˝, ˝e jeÊli uczestnicy po-
dzia∏u ró˝nià si´ w ocenach, to wówczas ∏atwiej
jest ich zadowoliç. Wyniki te zosta∏y opublikowa-
ne po wojnie w szwedzkim czasopiÊmie Econome-
trica (nr 16, ss. 101–104, 1948). Ju˝ wtedy Steinhaus
wyra˝a∏ przekonanie, ˝e podzia∏ sprawiedliwy (na-
zwany przez niego „pragmatycznym”) nadaje si´
do rozstrzygania niektórych mi´dzynarodowych
sporów terytorialnych (przyp. t∏um.).
Â
WIAT
N
AUKI
Luty 1999 89
R
obert L. Henrickson z Billings w
Montanie napisa∏ do mnie o artykule
,,Szklana butelka Kleina” (z maja ub. r.),
podajàc kilka fascynujàcych informacji
o podobnych butelkach wykonanych
przez garncarzy. Ksià˝ka Herber-
ta C. Andersona, Jr., The Life,
the Times, and the Art of Bran-
son Graves Stevenson
(˚y-
cie, czasy i sztuka Branso-
na Gravesa Stevensona;
Janher Publishing,1979) do-
nosi, ˝e ,,w odpowiedzi na
wyzwanie swego syna May-
narda, matematyka, Bran-
son sporzàdzi∏ swà pierwszà
butelk´ Kleina, wykorzystujàc
sugestie topologiczne [sic!] nie-
mieckiego matematyka Kleina.
Pierwsze próby by∏y nieudane. A˝ kiedyÊ
Bransonowi przyÊni∏ si´ s∏ynny angiel-
ski ceramik Wedgwood, który mu poka-
za∏, jak zrobiç butelk´ Kleina.” To by∏o
oko∏o 50 lat temu. Studia Bransona nad
rzeêbà w glinie i garncarstwem do-
prowadzi∏y ostatecznie do
utworzenia Archie Bray Foun-
dation w miejscowoÊci He-
lena (Montana).
Ludzie wytwarzajà butelki
Kleina z wszelkich materia-
∏ów. Mo˝na zrobiç we∏nianà
butelk´ na drutach; istnieje
nawet papierowa butelka Kle-
ina z otworem (z lewej), na-
des∏ana przez Phillipa
A. M. Hawleya z Paonii
(Kolorado).
SPRZ¢˚ENIE ZWROTNE
IAN WORPOLE