199902 twoja polowa jest wieksz

background image

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

background image

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


Wyszukiwarka

Podobne podstrony:
Bóg jest większy, S E N T E N C J E, E- MAILE OD PANA BOGA
Chemia labolatorium, refraktometria, Jeśli kąt załamania jest większy od kąta padania to promień świ
Twoja przestrze ä jest poza éa äcuchami mi¦Ödzy 1998 a 2000 rokiem
Twoja przyjaźń jest
Twoja przesyłka jest gotowa do odebrania w Paczkomacie uwaga na kolejne SMS owe oszustwa
Czy wszechświat jest częścią większej całości, W ஜ DZIEJE ZIEMI I ŚWIATA, ●txt RZECZY DZIWNE
009, Większość elektronicznego sprzętu powszechnego użytku wyposażona jest dzisiaj w nadajniki zdal-
Art DLACZEGO WIĘKSZOŚĆ RELIGII JEST SZKODLIWA
Opracowania różnych tematów, Jakaż jest przeciw włóczni złego Twoja tarcza, Jakaż jest przeciw włócz
Większość blaszanych pokryć?chowych jest ze stali walcowanej na zimno
Podpis jest twoją wizytówką - Grafologia była częścią wiedzy tajemnej, Grafologia
Psychologi V, Większość myśli, emocji jest wywoływane przez inne osoby
Rynek eurokredytowy jest rynkiem zorientowanym na większe firmy
ściągi i egzaminy, Koagulacja, Koagulacja- jest to proces łączenia cząstek koloidowych w większe pro
NERW UDOWY , NERW UDOWY - powstaje między powierzchowną a głęboką warstwą mięśnia lędźwiowego większ
Jednym z czułych podzespołów montowanych w większości współczesnych dużych diesli jest dwumasowe koł
O niewiasto wielka jest twoja wiara

więcej podobnych podstron