Brams – Taylorův postup - Brams–Taylor procedure

The Brams – Taylorův postup (BTP) je postup pro řezání dortů bez závisti. Vysvětlil první konečný postup, který vytvořil závistivé rozdělení dortu mezi jakýkoli kladný celočíselný počet hráčů.^[1]

Dějiny

V roce 1988, před objevením BTP, Sol Garfunkel tvrdil, že problém vyřešený teorémem, jmenovitě řezání dortu bez závisti bez osob, byl jedním z nejdůležitějších problémů v matematice 20. století.^[2]

BTP byl objeven uživatelem Steven Brams a Alan D. Taylor. Poprvé byla zveřejněna v lednu 1995 ve vydání Americký matematický měsíčník,^[3] a později v roce 1996 v knize autorů.^[4]

Brams a Taylor drží kloub Americký patent z roku 1999 související s BTP.^[5]

Popis

BTP rozděluje dort po částech. Typický přechodný stav BTP je následující:

• Část dortu, řekněme ${ displaystyle X}$, je bez závisti rozdělena mezi všechny partnery.
• Zbytek dortu, řekněme ${ displaystyle Y}$, zůstává nerozdělen, ale -
• Jeden partner, řekněme Alice, má Neodvolatelná výhoda (IA) nad jiným partnerem, řekněme Bob, s ohledem na ${ displaystyle Y}$. To znamená, že bez ohledu na to, jak ${ displaystyle Y}$ je rozdělena, i když dáváme ${ displaystyle Y}$ úplně Bobovi, Alice stále Bobovi nezávidí.

Jako příklad toho, jak lze vygenerovat IA, zvažte první fázi Diskrétní postup Selfridge – Conway:

• Alice rozdělí dort na 3 části, které považuje za rovnocenné; zavoláme části ${ displaystyle A, B, C}$.
• Bob ořezává kus, který považuje za největší (řekněme, ${ displaystyle A}$) aby se rovnal druhému největšímu; řekněme ozdoby ${ displaystyle Y}$ a ořezaný kus ${ displaystyle A setminus Y}$.
• Charlie si vybere kousek z ${ displaystyle (A setminus Y), B, C}$; pak si Bob vybere (musí si vzít ${ displaystyle (A setminus Y)}$ pokud je k dispozici); a nakonec Alice.

Po dokončení této fáze, všechny dort kromě ${ displaystyle Y}$ je rozdělena způsobem bez závisti. Navíc má Alice nyní IA přes kohokoli převzal ${ displaystyle (A setminus Y)}$. Proč? protože Alice vzala buď ${ displaystyle B}$ nebo ${ displaystyle C}$, a oba jsou si rovni ${ displaystyle A}$ podle jejího názoru. Podle Alice tedy kdokoli vzal ${ displaystyle (A setminus Y)}$ může také mít ${ displaystyle Y}$ - to jí nebude závidět.

Pokud se chceme ujistit, že Alice dostane IA nad konkrétním hráčem (např. Bobem), je zapotřebí mnohem složitější postup. Postupně rozděluje dort na menší a menší kousky, vždy dává Alice kousek, který si cení více než Bobův, takže je zachována IA. To může trvat neomezeně dlouho - v závislosti na přesném ocenění Alice a Boba.

Pomocí postupu IA vytvoří hlavní postup BTP IA pro všechny objednané páry partnerů. Pokud jsou například 4 partneři, existuje 12 seřazených párů partnerů. U každého takového páru (X, Y) spustíme dílčí postup, který zaručuje, že partner X má IA nad partnerem Y. Poté, co každý partner má IA nad každým jiným partnerem, můžeme zbývající část dát libovolnému partnerovi a výsledkem je nezáviděníhodné rozdělení celého dortu.

Viz také

• Brams – Taylor – Zwickerův postup - postup s pohyblivým nožem pro 4 partnery, který využívá konečný počet řezů.
• Řezání dortů bez závisti - starší a novější postupy pro stejný problém.

Reference