Brahms-Taylor-Zwickerova procedura

Postup Brahms-Taylor-Zwicker  je protokol pro závistivé krájení dortu na 4 účastníky [1] .

Procedura využívá variantu procedury Austin pro dva účastníky a společné dělení . Tento postup umožňuje dvěma účastníkům rozdělit celý dort na kousky, z nichž každý je přesně ohodnocen u obou účastníků.

Hlavní postup funguje takto:

A. Použijte proceduru Austin s účastníky #1 a #2. Vzniknou nám 4 kusy, které oba první účastníci odhadují přesně na 1/4.

B. Účastník č. 3 zkrátí jeden kus. Nyní si účastníci vybírají figurky v opačném pořadí (#4, #3, #2, #1). Jeden z účastníků - # 4 nebo # 3 - musí vzít odříznutý podíl z oříznutého kusu. Díky tomu dělení projde bez závisti na celý kus bez zkrácení (Toto je podrobně rozebráno v postupu Selfridge-Conway ).

C. Nyní odříznutý kus rozdělíme. Bez ztráty obecnosti předpokládejme, že odříznutý díl připadne účastníkovi č. 3. Použijeme Austinův postup k rozdělení tohoto nakrájeného dílku účastníky #4 a #1, abychom dostali 4 kusy, z nichž každý má hodnotu přesně 1/4. Protože soutěžící č. 1 a č. 2 mají jasnou výhodu, můžeme nechat soutěžícího č. 3, aby si nejprve vybral vystřižený díl, poté č. 2, poté č. 4 a č. 1.

Účinnost

Doba trvání procedury je z technického hlediska nekonečná, protože procedura Austin využívá nepřetržitý pohyb nožů a tento postup nemůže být diskrétní.

Počet řezů je však omezen. Postup Austin vyžaduje 2 řezy k rozdělení dortu mezi dva účastníky s přesnou hodnotou 1/4. Každý z těchto kusů musí být řezán dvěma dalšími řezy, aby se vytvořily 4 kusy s přesnou 1/4 hodnotou. Celkový počet řezů potřebných pro krok A je tedy 6. Jeden řez se provede v kroku B a 6 dalších řezů v kroku C, celkem tedy 13 řezů.

Vylepšená verze postupu Brahms-Taylor-Zwicker využívá pouze 11 řezů [2] .

Poznámky

  1. ↑ Brams a Taylor 1996 , str. 126–128.
  2. ↑ BRAMS, TAYLOR, ZWICKE, 1997 , s. 547–554.

Literatura