5.5: Останній зменшувач

Last updated
Save as PDF

Page ID: 66213

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Метод останнього зменшувача - це ще один підхід до поділу між 3 або більше партіями.

Останній метод зменшення

При цьому способі сторонам випадковим чином присвоюється замовлення, можливо, шляхом витягування імен з капелюха. Далі метод протікає наступним чином:

1) Перша особа вирізає шматочок, який вони цінують як справедливу частку.

2) Друга людина розглядає шматок

а Якщо вони думають, що це коштує менше, ніж справедлива частка, вони потім передають шматок без змін.

б Якщо вони думають, що шматок коштує більше, ніж справедлива частка, вони обрізають надлишок і пред'являють претензії на шматок. Обрізки додаються назад у купу, яку потрібно розділити.

3) Кожна людина, що залишилася, в свою чергу, може або передати, або обрізати шматок

4) Після того, як остання людина прийняла своє рішення, остання людина, яка обрізала зріз, отримує його. Якщо скибочку ніхто не видозмінював, то людина, яка його розрізала, отримує його.

5) Той, хто отримує шматок, залишає зі своїм шматком, і процес повторюється з людьми, що залишилися. Продовжуйте до тих пір, поки не залишаться лише 2 людини; вони можуть розділити те, що залишилося за допомогою методу дільника-вибору.

Приклад 8

Припустимо, що чотири продавця поділяють штат Вашингтон на регіони продажів; кожен отримає один регіон для роботи. Вони витягують імена з капелюха, щоб вирішити порядок гри.

Рішення

$Картина штату Вашингтон з великою територією навколо Сіетла пофарбована в жовтий колір.$ Раунд 1. Перший продавець, Боб, малює регіон навколо Сіетла, найбільш густонаселеного району штату. Шматок Боб вирізає і автоматично претендує на показаний жовтим кольором.

$Картина штату Вашингтон з великою територією навколо Сіетла пофарбована в жовтий колір, а менша ділянка всередині нього пофарбована в рожевий колір.$ Другий продавець, Генрі, вважав, що цей регіон коштує більше 25%, справедлива частка кожного гравця. Через це Генрі вирішує обрізати цей шматок. Новий шматок зображений у рожевому кольорі. Обрізки (жовтим кольором) повертаються до розділеної частини стану. Генрі автоматично претендує на цей менший шматок, оскільки він його обрізав.

Третя продавщиця, Марджо, вважає, що цей шматок коштує менше 25% і проходить, як і четверта продавщиця, Бет. Оскільки обидва проходять, остання людина, яка її обрізала, Генрі, отримує шматок.

$Картина штату Вашингтон з невеликою територією навколо Сіетла пофарбована в рожевий колір, а нова більша область навколо нього пофарбована в жовтий колір.$ Раунд 2. Другий раунд починається з укладання Боба претензії на шматок, знову показаний жовтим кольором. У Генрі вже є шматок, так що зараз поза процесом. Марджо передає цей твір, відчуваючи, що він коштує менше, ніж справедлива частка.

$Зображення штату Вашингтон з невеликою територією навколо Сіетла пофарбоване в рожевий колір, більша область навколо нього пофарбована в жовтий колір, а область ледь менша за жовтий колір у синій колір.$ Бет, з іншого боку, відчуває, що шматок, як в даний час намальований коштує 35%. Бет знаходиться в вигідному становищі, будучи останньою, хто приймає рішення. Незважаючи на те, що Бет оцінює цей шматок на 35%, вона може скоротити дуже невелику суму і все одно претендувати на нього. Так Бет ледве вирізає шматок, в результаті чого шматок (синій), який по суті коштує 35% для неї. Так як вона в останню чергу обрізається, вона отримує шматок.

$Картинка штату Вашингтон з невеликою площею навколо Сіетла пофарбована в рожевий колір, більша область навколо нього пофарбована в синій колір, при цьому решта штату розділена посередині вертикальною лінією, ліва затінена помаранчевим кольором, права затінена жовтим кольором.$ Раунд 3. На даний момент Боб і Марджо є єдиними гравцями без шматка. Так як їх дві, вони можуть закінчити поділ методом дільника-селектора. Вони перевертають монету і визначають, що Марджо буде дільником. Марджо малює лінію, що розділяє залишок стану на дві частини. Боб вибирає східний шматок, залишаючи Марджо із західною половиною.

Зверніть увагу, що в цьому дивізіоні Генрі і Марджо закінчилися шматочками, які, на їхню думку, коштують рівно 25% - справедливу частку. Бет змогла отримати шматок, який вона цінує як більше, ніж справедливу частку, і Боб може відчувати, що шматок, який він отримав, коштує більше 25%.

Приклад 9

Маркус, Еббі, Джуліан і Бен розщеплюють піцу, яка є 4 скибочки сиру і 4 скибочки овочів загальною вартістю $12. Маркус і Бен люблять обидва смаки однаково, Еббі любить лише сир, а Джуліан любить овочі вдвічі більше, ніж сир. Вони ділять піцу останнім методом зменшення, граючи в порядку Маркус, Еббі, Бен, потім Джуліан.

Рішення

Зверніть увагу, Бен і Маркус обидва цінують будь-який шматочок піци в $1.50.

Еббі оцінює кожен шматочок сиру в 3 долари, а овочі - 0 доларів.

Джуліан оцінює кожен шматочок сиру в 1 долар, а кожен шматочок овоча - 2 долари. (див. Приклад 2)

Справедлива частка для будь-якого гравця становить 3 долари.

У першому раунді припустимо, що Маркус вирізає 2 скибочки сиру, які він оцінює в 3 долари.

Еббі любить лише сир, тому оцінить цей зріз у 6 доларів. Вона обріже його до 1 скибочки сиру, який вона цінує як свою справедливу частку в 3 долари.

Бен буде розглядати цей шматок як менше справедливої частки, і пройде.

Джуліан розгляне цей твір як меншу, ніж справедливу частку, і пройде.

Еббі отримує шматок.

У другому раунді, припустимо, Маркус вирізає шматочок, який є 2 скибочками овочів.

Еббі вже отримала скибочку так виходить.

Бен буде розглядати цей шматок як має значення $3. Він ледве може обрізати його і пред'явити на нього претензії.

Джуліан буде цінувати цей шматок як має значення $4, так що ледве обрізати його і претендувати на нього.

Маркус і Бен можуть потім розділити залишилися 3 скибочки сиру і 2 скибочки овочів за допомогою методу дільника-селектора.

У другому раунді і Бен, і Джуліан зроблять крихітні обрізки (відтягуючи маленьку крихту), щоб відкласти претензію на шматок, практично не зменшуючи значення. Шматок, який отримує Джуліан, все ще по суті коштує йому 4 долари; ми не турбуємося про вартість цієї крихти.

Спробуйте зараз 5

П'ять гравців ділять $20 торт. У першому раунді гравець 1 робить початковий розріз і претендує на шматок. Для кожного з гравців, що залишилися, значення поточного фрагмента (який, можливо, був урізаний) на момент його ходу показано нижче. Опишіть результат першого раунду.

\ (\ почати {масив} {|l|l|l|l|l|}
\ hline &\ mathbf {P} _ {2} &\ mathbf {P} _ {3} &\ mathbf {P} _ {4} &\ mathbf {P} _ {5}\
\ hline\ почати {масив} {l}
\ текст {Значення}\
\ текст {поточний шматок}
\ кінець {масив} &\ $3 &\ $5 &\ $ 3.50 &\ $3\\
\ hline
\ кінець {масив}\)

У другому раунді гравець 1 знову робить початковий розріз і претендує на шматок, а поточні значення відображаються знову. Опишіть результат другого туру.

\ (\ почати {масив} {|l|l|l|}
\ hline &\ mathbf {P} _ {2} &\ mathbf {P} _ {4} &\ mathbf {P} _ {5}\\ hline
\ begin {масив} {л}
\ текст {Значення}\
\ текст {поточний шматок}
\ кінець {масив}\ $7 &\ $3 &\ $5\\
\ hline
\ end {масив}\)

Відповідь

У першому раунді гравець 1 виріже шматок, який він оцінює як справедливу частку $4. Гравець 2 оцінює шматок як $3, тому буде проходити. Гравець 3 цінує шматок як $5, тому буде вимагати його і обрізати його до того, що вона цінує як $4. Гравець 4 отримує цей шматок і оцінює його як $3.50, тому буде проходити. Гравець 5 оцінює шматок в 3 долари і також буде проходити. Гравець 3 отримує обрізаний шматок, який вона оцінює в 4 долари.

У другому раунді гравець 1 знову виріже шматок, який він оцінює як справедливу частку $4. Гравець 2 цінує шматок як $7, тому буде вимагати його і обрізати його до того, що він цінує як $4. Гравець 4 оцінює обрізаний шматок в 3 долари і проходить. Гравець 5 оцінює шматок в $5, тому буде претендувати на це. Оскільки гравець 5 є останнім гравцем, вона має перевагу і може стверджувати, що потім ледве обрізати шматок. Гравець 5 отримує шматок, який вона оцінює в $5.