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