Autor: Gendzo macher
Kategória: Logické
Publikovaný: 30.11.2007 / Počet zobrazení: 20941

Dvaja robotníci pracujúci na stavbe išli na obed. Keďže nemali pri sebe veľa peňazí, objednali si iba jednu pizzu. Pizzu si dali zabaliť do krabice a odniesli si ju späť na stavbu. Tam jeden murár chytil nožík a chcel pizzu rozkrojiť.

Riešenie pre dve osoby:
Prvý murár pizzu len rozkrojí, pričom ten druhý murár si môže vybrať ako prvý, ktorý kúsok pizze chce. Tak je zabezpečené, že prvý murár nerozdelí pizzu na nerovnaké časti, lebo jeho kolega by mu aj tak ten väčší kus uchmatol.

Riešenie pre N osôb:
Najprv malá definícia – spravodlivé delenie, pri ktorom sú všetci hladoši spokojní je, že pizza bude rozkrájaná na N častí, každá s veľkosťou 1/N celej pizze.

A TERAZ POSTUP:
N osôb musíme najprv zoradiť. Je jedno, kto bude prvý krájač, kto druhý atď, dôležité však je, že poradie sa už následne nesmie meniť.

Prvý človek zoberie nožík a odkrojí z pizze časť o veľkosti presne 1/N celej pizze.

Následne zoberie nožík druhý človek a odkrojí zo zvyšku pizze (z tej väčšej časti) kúsok o veľkosti 1/(N-1) = 1/N celej pizze.

Ak zoberie do ruky nožík osoba označená v poradí ako K, vždy musí zo zvyšku pizze (z tej väčšej časti) odkrojiť kúsok o veľkosti 1/(N-K+1).

Posledný človek (podľa vopred určeného poradia) už nebude pizzu krájať, ale bude si vyberať z nakrájaných kúskov.

Následne si bude vyberať svoj kúsok pizze predposledný krájač, atď, až tomu, kto krájal ako prvý ostane na tanieri posledný kúsok pizze.

Prečo bude tento postup fungovať?

Vieme, že všetci sú logicky uvažujúci. To znamená, že prvý človek vie, že ak z pizze odkrojí kúsok o veľkosti väčšej ako je 1/N celej pizze, tento kus sa môže stať najväčším odkrojeným kusom a posledný človek v poradí, ktorý už nekrája ale si rovno vyberá, si ho hneď aj vyberie. Každý sa predsa zaujíma, či niekto iný nemá väčší kus ako on sám.
Rovnako však, ak by odkrojil kúsok menší ako je 1/N celej pizze, tento sa môže stať najmenším z celého delenia a keďže on si bude brať svoj kúsok ako posledný, mohol by ostať jemu. Takže ak logicky uvažuje, musí odkrojiť presne 1/N.

Ak druhý krájač odkrojí časť väčšiu ako je 1/N celej pizze, znovu riskuje situáciu, že mu ho vezme nasledujúci záujemca o večeru. Ak by naproti tomu odkrojil kúsok menší ako 1/N celej pizze, môže sa síce spoliehať na to, že on si ho pri výbere nezoberie, a nechá ho prvému krájačovi. No ak neodkrojí z pizze presne 1/N, vo zvyšku pizze, ktorý ide na ďalšie delenie, bude ostávať viac pizze ako je násobok 1/N x počet zostávajúcich krájačov. A tak sa určite nájde niekto z nasledovných krájačov, ktorý bude mať kus väčší ako je 1/N celej pizze. Každý sa zaujíma o to, či niekto nemá väčší kus ako on sám. Takže aj druhý krájač v poradí odkrojí kúsok o veľkosti presne 1/N celej pizze.

A takto to postupuje až dokonca.