Postup s pohyblivým nožem Robertson-Webb

Postup Robertson-Webb „Moving Knife“ je postup, jak závistivě rozřezat dvourozměrný dort na tři účastníky [1] . Postup dělá pouze dva střihy, takže každý účastník obdrží jeden celý kus.

Hlavní výhodou postupu oproti dřívějšímu Stromqvistově postupu „Moving Knife“ a pozdějšímu postupu Barbanel-Brahms „Moving Knife“ použití pouze jednoho pohyblivého nože. K tomu se využívá dvourozměrnost dortu.

Postup

Zpočátku každý účastník provede svislý řez, takže účastník odhadne dort vlevo přesně na 1/3. Je vybrán řez zcela vlevo. Předpokládejme, že Alice udělala tento řez. Poté Alice získá levou figurku, kterou ohodnotí přesně na 1/3. Zbytek by měl být rozdělen mezi zbývající členy (Bob a Carl).

Všimněte si, že podíl Alice je odhadován na ne více než 1/3 a zbytek alespoň na 2/3 jak Bobem, tak Carlem. Pokud tedy Bob a Carl získají alespoň polovinu zůstatku, nemají důvod žárlit. Problém je v Alice, jak přimět ji, aby nežárlila.

Řešení je založeno na následujícím pozorování: protože každá Alice může umístit nůž pod takovým úhlem a zbývající kus rozříznout v očích na dvě stejné poloviny . To znamená, že Alice může otáčet nožem přes zbytek dortu, takže na obou stranách nože v jejích očích budou kousky stejné.

Když je nůž na 0, Bob (slabě) preferuje buď kus nad nožem, nebo kus pod nožem (slabě znamená, že se mu kusy mohou jevit jako stejné a preferuje oba kusy stejně). Když je nůž pod úhlem , kusy se obrátí. Proto podle věty o střední hodnotě musí existovat úhel, ve kterém si Bob myslí, že kousky na obou stranách nože jsou stejné. Když nůž zaujme tento úhel, Bob zvolá "stop!". Dort je nakrájen a Carl si vybere kousek a Bob si vezme zbývající kousek.

Analýza

Alice nežárlí, protože pro ni mají všechny tři kousky hodnotu přesně 1/3.

Bob a Carl Alici nezávidí, protože její figurka je hodnocena nejvýše na 1/3 a jeho figurka nejméně na (1/2)*(2/3) = 1/3.

Bob na Carla nežárlí, protože jejich kousky jsou (v jeho očích) stejné. Carl na Boba nežárlí, protože si vybral ty nejlepší kousky.

Dělení "špatného" dortu

Postup „pohyblivého nože“ lze upravit pro rozdělení povinností , tedy dort s celkovým záporným skóre [2] . V tomto případě v počáteční fázi není vybrán levý kus, ale ten pravý.

Viz také

Poznámky

  1. ↑ Robertson, Webb, 1998 , str. 77–78.
  2. ↑ Robertson, Webb, 1998 , str. cvičení 5.10.

Literatura