Postup pohyblivých nožů Levmore – Cook - Levmore–Cook moving-knives procedure - Wikipedia

The Postup pohyblivých nožů Levmore – Cook je postup pro řezání dortů bez závisti mezi třemi partnery. Je pojmenován po Saul X. Levmore a Elizabeth Early Cook, kteří ji představili v roce 1981.[1]Předpokládá se, že dort je dvourozměrný. Vyžaduje to dva nože a čtyři kusy, takže někteří partneři mohou obdržet odpojené kousky.

Postup

Jmenujeme partnery Alice, Bob a Carl.

Alice zpočátku kráje dort na tři stejné kousky v jejích očích. Bob a Carl každý ukazují na svůj oblíbený kousek.

Snadný případ: Bob a Carl ukazují na různé kousky. Každý obdrží svůj oblíbený kousek a Alice zbývající kousek.

Tvrdé pouzdro: Bob a Carl ukazují na stejný kousek. Řekněme, že toto je kousek X a ostatní kousky jsou Y a Z. Nyní Alice vezme dva nože a pohybuje jimi současně po kousku X:

    • Nůž # 1 je přesunut horizontálně zleva od kusu X doprava. Rozděluje díl X na dva dílky: levý díl XL a pravý díl XR.
    • Nůž # 2 je přesunut vertikálně, nalevo od nože # 1, takže XL je v očích rozdělena na dva stejné kousky: XLT nahoře vlevo a XLB dole dole.

Zpočátku XR = X, takže pro Boba a Carla je větší než Y a Z. Navíc jsou původně XLT a XLB prázdné, takže XR je větší než dva páry: Y + XLT a Z + XLB.

Jak se nůž # 1 pohybuje doprava, XR se zmenšuje, zatímco XLT a XLB rostou. V určitém okamžiku si Bob nebo Carl myslí, že XR se rovná jednomu ze dvou párů. První, kdo si myslí, že existuje rovnost, křičí „přestaň!“ a obdrží svůj zvolený pár. Alice přijme druhý pár a non-shooter obdrží XR.

Analýza

Analyzujeme případ, kdy Bob křičel „přestaň!“ a vybral pár Y + XLT. Alice dostane Z + XLB a Carl dostane XR. Divize je bez závisti, protože:

  • U Alice Z> X> XR, takže Alice Carlovi nezávidí. Navíc Z = Y a XLB = XLT, takže Alice Bobovi nezávidí.
  • U Boba Y + XLT = XR> Z + XLB, takže Bob nezávidí.
  • Pro Carla je XR větší než oba páry (protože nekřičel), takže nezávidí.

Ostatní případy jsou analogický.

Varianty

Je možné nechat střelce vybrat si jeden ze čtyř párů: Y + XLT, Y + XLB, Z + XLT, Z + XLB. Tato modifikace upřednostňuje nikoho, kdo křičí, protože křičí obvykle křičí „zastavit“ dříve.[2]

Levmore a Cook představili a zobecnění jejich postupu pro 4 partnery. Později se však ukázalo, že toto zobecnění nefunguje ve všech případech.[3]:122–124

Viz také

The Postup pohyblivých nožů Stromquist používá čtyři nože, ale pouze dva z nich by měly řezat, takže každý partner obdrží spojený kus.

Reference

  1. ^ Saul X. Levmore a Elizabeth Early Cook (1981). Super strategie pro hádanky a hry. Garden City, NYhttps://catalog.lib.uchicago.edu/vufind/Record/4476190: Doubleday.CS1 maint: používá parametr autoři (odkaz) CS1 maint: umístění (odkaz)
  2. ^ Cytron, Ron (2012). „Algoritmy krájení dortu - přednáška 8“ (PDF). Citováno 27. srpna 2016.
  3. ^ 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.