Jak rozdělit dort

Matematika | 06.01.2010

Jestliže se chtějí dva lidé podělit o dort a nepohádat se při tom, pak nejlepší metodou je postup „já krájím, ty si vyber“. Problém se ovšem stává pozoruhodně obtížným, pokud se dort dělí mezi více než dvě osoby, a čím je jich více, tím je úloha náročnější.

Sdílet

Nejjednodušší příklad zahrnuje pouze dvě osoby, které si mají rozdělit dort tak, aby oběma připadal jejich díl spravedlivý. Slovo „spravedlivý“ zde chápeme ve smyslu „podle mého soudu alespoň poloviční“, přičemž hlediska mohou být různá a účastníci nemusí jednotlivé díly hodnotit stejně. Kupříkladu Adélka může dávat přednost třešničkám a Terezka má zase ráda marcipán. Jeden z nejpozoruhodnějších poznatků vzniklých v souvislosti s dělením dortů je fakt, že je snazší rozdělit dort v případě, kdy účastníci nemají stejné preference stran jednotlivých dílů. Z uvedeného příkladu vidíme, že to vcelku dává smysl, neboť můžeme dát Adélce třešničku a Terezku obdařit marcipánem, a budou obě spokojené. Hůř by se nám dělilo, kdyby obě milovaly marcipán.

Máme-li jen dva hráče, pak se o nic obtížného nejedná. Řešení „Adélka dělí, Terezka vybírá“ je staré přes 2 800 let! Oběma budou tato pravidla připadat spravedlivá, protože ani jedna nemá žádný důvod ke stížnostem ohledně výsledného rozdělení. Jestliže se Adélce nelíbí kousek, který jí Terezka nechala, může si za to sama, protože při krájení dostatečně nedohlédla na to, aby byly oba kousky rovnocenné (tedy podle jejího názoru na věc). Pokud se dělba nelíbí Terezce, měla si vzít druhý kousek.

Problém začíná být zajímavý v okamžiku, kdy do hry vpustíme třetího žrouta. Řekněme, že se Jirka, Mirek a Vašek (podobnost s politickou scénou je samozřejmě čistě náhodná) sejdou, aby naporcovali medvěda pokud možno takovým způsobem, aby každý z nich dostal ze svého hlediska alespoň třetinu. Mimochodem, ve všech podobných úlohách předpokládáme, že medvěd je nekonečně dělitelný, i když většina teoretických postupů funguje i v případě, kdy se medvěd skládá z „atomů“, tedy nedělitelných jednotlivých částeček, kterým jednotliví hráči přiřazují určité hodnoty. Pro jednoduchost budeme nicméně předpokládat, že brtník žádné atomy nemá. Robertson a Webb pro tuto variantu analyzují na první pohled věrohodné, ale ve skutečnosti nesprávné řešení (opouštím medvěda a vracím se k dortu, bude to jednodušší):

KROK 1: Jirka rozdělí dort na dvě části X a W tak, aby podle jeho úsudku X představovalo třetinu a W dvě třetiny dortu.

KROK 2: Mirek rozdělí W na dvě části Y a Z tak, aby podle něj každá z nich tvořila polovinu W.

KROK 3: Vašek si vybere kterýkoli z dílů X, Y, Z. Ze zbylých dvou dílů si pak vybere Jirka a na Mirka zbude poslední díl.

Je tento algoritmus spravedlivý?

Je jasné, že Vašek bude spokojen, protože má právo první volby. Rovněž Jirka bude v pohodě, vysvětlení je ale trochu složitější. Jestliže si Vašek vezme X, pak si Jirka může vybrat kterýkoli z dílů Y a Z. Protože podle něj má W hodnotu dvou třetin celého dortu, alespoň jeden z nabídnutých dílů musí nutně mít hodnotu alespoň jedné třetiny. Obdobně, pokud si Vašek vybere Y nebo Z, Jirka si může vzít X.

Jenomže je tu ještě Mirek, a ten nemusí být výsledkem zrovna nadšen. Může se totiž stát, že nebude souhlasit s Vaškem, že první řez byl spravedlivý a že odhadne hodnotu W na méně než dvě třetiny. V takovém případě by jej uspokojil pouze díl X. Jenomže se může stát, že Vašek si vybere Y, Jirka X a na Mirka zbude díl Z, o který nestojí.

Takže výše uvedený algoritmus není spravedlivý. První správné řešení problému pro tři osoby podal v roce 1944 Hugo Steinhaus, člen proslulé skupiny polských matematiků, která se scházela v jedné lvovské kavárně. Jeho řešení je založeno na technice zvané „ořízka“.

KROK 1: Jirka rozdělí dort na dva díly X a W, přičemž X má podle něj hodnotu jedné třetiny a W dvou třetin.

KROK 2: Jirka podá X Mirkovi a požádá jej, aby díl posoudil. Pokud se Mirek domnívá, že X má hodnotu vyšší než 1/3, má nyní možnost oříznout jej tak, aby tuto hodnotu získal. Má-li Mirek jiný názor, nechť laskavě nechá dort na pokoji. Nově vzniklý díl nazveme X*; ten může být buď stejný jako X, nebo menší.

KROK 3: Mirek podá X* Vaškovi, který si jej buď vezme, nebo nikoli.

KROK 4: (a) Jestliže Vašek přijme X*, Jirka a Mirek uhňácají ze zbytků, tedy z W a z odřezků, nový (nechutný) celek a zahrají si o něj podle pravidla „krájím–vybírej“.

(b) Pokud Vašek odmítne X* a Mirek ve druhém kroku byl ořezal X, pak si X* vezme Mirek a Jirka s Vaškem si zahrají o zbytek.

(c) Pokud Vašek nechce X* a Mirek ve druhém kroku nechal X Xem, pak si X vezme Jirka a o zbytek si zahrají Mirek s Vaškem.

To je samozřejmě jen jedno z možných řešení. Ověření logické správnosti ponechám na vás. Obecně řečeno platí toto: kdokoli by snad nebyl spokojen se svým dílem, nechť z toho viní jen sám sebe, neboť při dělení musel buď nesprávně volit, nebo křivě krájet.

obalka-knihy