Brams – Taylor – Zwickerův postup - Brams–Taylor–Zwicker procedure - Wikipedia
The Brams – Taylor – Zwickerův postup je protokol pro řezání dortů bez závisti mezi 4 partnery.[1]:126–128
Postup používá variantu Austinův postup pro dva partnery a obecné zlomky. Tento postup umožňuje dvěma partnerům rozdělit celý dort kousky, z nichž každý má přesnou hodnotu pro oba.
Hlavní postup funguje následovně.
A. Použijte Austinův postup s a partneři # 1 a # 2. Máme tedy 4 kusy, o nichž první dva partneři věří, že mají přesně stejnou hodnotu 1/4.
B. Partner # 3 ořezává jeden kus a vytváří oboustrannou kravatu pro největší; partneři nyní vybírají kusy v obráceném pořadí (# 4, # 3, # 2, # 1). Ořezaný kus musí vzít buď č. 4 nebo č. 3. Tím se vytvoří rozdělení bez závisti na celý dort bez ořezů (to je podobné jako u Diskrétní postup Selfridge – Conway ).
C. Nyní jsou ozdoby rozděleny. Předpokládejme, že w.l.o.g. ten # 3 vzal ořezaný kus. Použijeme Austinovu proceduru znovu s ořezy a partnery # 4 a # 1, abychom vytvořili 4 kusy, z nichž každý se rovná přesně 1/4 pro oba. Vzhledem k tomu, že partneři č. 1 a č. 2 mají neodvolatelnou výhodu oproti kterémukoli partnerovi, který si vzal ořezaný kousek, můžeme nechat číslo 3 jako první vybrat kousek z ořezu, pak # 2, pak # 4 a # 1.
Účinnost
Doba trvání postupu je technicky nekonečná, protože Austinův postup zahrnuje dva nože pohybující se nepřetržitě a tento postup nelze diskriminovat.
Počet řezů je však omezený. Austinův postup vyžaduje 2 řezy k rozdělení dortu mezi 2 lidi s přesnou hodnotou 1/2; každý z těchto kusů by měl být rozdělen 2 dalšími řezy, aby se vytvořily 4 kusy s přesnou hodnotou 1/4. Celkově je tedy pro krok A potřeba 6 řezů. V kroku B se provede jediný řez a v kroku C dalších 6 řezů, celkem tedy 13 řezů.
Pokročilá varianta postupu Brams – Taylor – Zwicker používá pouze 11 řezů.[2]
Reference
- ^ Brams, Steven J .; Taylor, Alan D. (1996). Spravedlivé rozdělení: od krájení dortů po řešení sporů. Cambridge University Press. ISBN 0-521-55644-9.
- ^ Brams, Steven J .; Taylor, Alan D .; Zwicker, William S. (1997). „Řešení pohyblivého nože divizi dortů bez závisti čtyřčlennou“. Proceedings of the American Mathematical Society. 125 (2): 547–554. CiteSeerX 10.1.1.104.3390. doi:10.1090 / s0002-9939-97-03614-9.