Процедура перемещения ножей Стромквиста

Процедура «Движущиеся ножи» Стромквиста — это процедура разрезания торта между тремя игроками без зависти . Он назван в честь Уолтера Стромквиста , представившего его в 1980 году. ^[1]

Эта процедура была первой процедурой перемещения ножа, не вызывающей зависти, разработанной для трех игроков. Для этого требуется четыре ножа, но только два разреза, поэтому каждый игрок получает одну соединенную деталь. Не существует естественного обобщения для более чем трех игроков, которое делило бы торт без дополнительных разрезов. Полученное в результате разделение не обязательно будет эффективным . ^[2]^{: 120–121}

Процедура

Судья водит мечом слева направо по торту, гипотетически разделяя его на маленький левый кусок и большой правый кусок. Каждый игрок перемещает нож по правой фигуре, всегда держа его параллельно мечу. Игроки должны двигать ножами непрерывно, не совершая «прыжков». ^[3] Когда любой игрок кричит «разрезай», торт разрезается мечом и тем ножом игроков, который окажется центральным из трех (то есть вторым по порядку от меча). Затем торт делится следующим образом:

Часть слева от меча, которую мы обозначаем Left , отдается игроку, который первым крикнул «режь». Мы называем этого игрока «крикуном», а двух других игроков — «тише».
Фигура между мечом и центральным ножом, которую мы обозначаем Middle , отдается оставшемуся игроку, чей нож находится ближе всего к мечу.
Оставшаяся часть Right отдается третьему игроку.

Стратегия

Каждый игрок может действовать таким образом, чтобы гарантировать, что — по его собственным меркам — ни один другой игрок не получит больше, чем он:

Всегда держите нож так, чтобы он делил часть справа от меча на две равные в ваших глазах части (следовательно, ваш нож сначала делит весь торт на две равные части, а затем движется вправо, когда меч движется вправо).
Крикните «разрезать», когда Левый станет равным фигуре, которую вы собираетесь получить, если вы молчите (т. е., если ваш нож крайний левый, крикните «разрезанный», если Левый = Средний; если ваш нож крайний правый, кричите, если Левый = Правый; если ваш нож находится в центре, кричите «разрезать», если Левый = Средний = Правый).

Анализ

Теперь мы докажем, что любой игрок, использующий описанную выше стратегию, получает долю без зависти.

Во-первых, рассмотрим два тише. Каждый из них получает по кусочку, в котором находится его собственный нож, поэтому они не завидуют друг другу. Кроме того, поскольку они молчали, кусок, который они получают, в их глазах больше, чем Левый, поэтому они также не завидуют кричащему.

Кричащий получает Левую, равную фигуре, которую он мог бы получить, промолчав, и большую, чем третья фигура, следовательно, кричащий не завидует никому из тише.

Следуя этой стратегии, каждый получает самую большую или одну из самых больших частей по своей собственной оценке, и поэтому разделение не вызывает зависти.

Тот же анализ показывает, что деление происходит без зависти даже в том несколько ухудшенном случае, когда кричащих два и крайняя левая фигура отдается любому из них.

Разделение «плохого» торта

Процедуру перемещения ножей можно адаптировать для разделения дел — деления торта с отрицательным значением. ^[4]^{: упражнение 5.11}

См. также

Процедура разрезания пирога Fair обеспечивает более простое решение той же проблемы с использованием всего 3 вращающихся ножей, когда торт представляет собой одномерный круг («пирог»),
Процедура с вращающимся ножом Робертсона-Уэбба обеспечивает еще более простое решение, используя только один вращающийся нож, когда пирог двухмерный.
Процедура с подвижным ножом

Ссылки

^ Стромквист, Уолтер (1980). «Как красиво разрезать торт». Американский математический ежемесячник . 87 (8): 640–644. дои : 10.2307/2320951 . JSTOR 2320951 .
^ Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. ISBN 0-521-55644-9 .
^ Важность этой преемственности объясняется здесь: «Процедура трех ножей Стромквиста» . Математическое переполнение . Проверено 14 сентября 2014 г.
^ Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .

[1] Стромквист, Уолтер (1980). «Как красиво разрезать торт». Американский математический ежемесячник . 87 (8): 640–644. дои : 10.2307/2320951 . JSTOR 2320951 .

[2] Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. ISBN 0-521-55644-9 .

[3] Важность этой преемственности объясняется здесь: «Процедура трех ножей Стромквиста» . Математическое переполнение . Проверено 14 сентября 2014 г.

[rw-4] Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .

[1]

[2]

[3]

[4]