Процедура с движущимися ножами Стромквиста - Stromquist moving-knives procedure
В Процедура с движущимися ножами Стромквиста это процедура для резка торта без зависти среди трех игроков. Он назван в честь Уолтер Стромквист который представил его в 1980 году.[1]
Эта процедура была первой свободной от зависти процедурой с перемещением ножа, разработанной для трех игроков. Для этого требуется четыре ножа, но только два разреза, поэтому каждый игрок получает одну соединенную деталь. Не существует естественного обобщения на более чем трех игроков, которое делит торт без дополнительных разрезов. Полученный раздел не обязательно эффективный.[2]:120–121
Процедура
А рефери перемещает меч слева направо по торту, гипотетически разделяя его на маленький левый кусок и большой правый кусок. Каждый игрок перемещает нож по правой части, всегда держа его параллельно мечу. Игроки должны двигать ножами непрерывно, без «прыжков».[3] Когда любой игрок кричит «разрезать», пирог разрезается мечом и тем, какой из ножей игроков оказывается центральным из трех (то есть вторым по порядку от меча). Затем торт делится следующим образом:
- Кусок слева от меча, который мы обозначаем Оставили, дается игроку, который первым крикнул «вырезать». Мы называем этого игрока «крикуном», а двух других игроков «тише».
- Кусок между мечом и центральным ножом, который мы обозначаем Середина, дается оставшемуся игроку, нож которого ближе всего к мечу.
- Оставшийся кусок, Правильно, передается третьему игроку.
Стратегия
Каждый игрок может действовать таким образом, чтобы гарантировать, что - в соответствии с его собственной мерой - ни один другой игрок не получит больше, чем он:
- Всегда держите нож так, чтобы он разделил часть справа от меча на две части, которые в ваших глазах равны (следовательно, ваш нож сначала делит весь торт на две равные части, а затем перемещается вправо, когда меч движется вправо).
- Кричите «разрезать», когда Left становится равным части, которую вы собираетесь получить, если вы сохраняете спокойствие (например, если ваш нож крайний левый, кричите «разрезать», если Left = Middle; если ваш нож самый правый, кричите, если Left = Right; если ваш нож находится в центре, кричите «разрезать», если левый = средний = правый).
Анализ
Теперь мы докажем, что любой игрок, использующий вышеуказанную стратегию, получает долю без зависти.
Сначала рассмотрим два более тихих. Каждый из них получает кусок, в котором находится их собственный нож, поэтому они не завидуют друг другу. Кроме того, поскольку они оставались тихими, фигура, которую они получают, в их глазах больше, чем Левая, поэтому они также не завидуют крикунам.
Кричащий получает левую часть, которая равна той фигуре, которую они могли получить, оставаясь безмолвной, и большей, чем третья фигура, поэтому крикун не завидует никому из более тихих.
Следуя этой стратегии, каждый получает самую большую или одну из самых больших частей по своей собственной оценке, и поэтому разделение не вызывает зависти.
Тот же анализ показывает, что деление не вызывает зависти даже в несколько вырожденном случае, когда есть два крикуна и крайняя левая фигура достается любому из них.
Делить плохой торт
Процедура движущихся ножей может быть адаптирована для деление по дому - разделение торта на отрицательное значение.[4]:упражнение 5.11
Смотрите также
- В Честная нарезка пирогов процедура обеспечивает более простое решение той же проблемы, используя только 3 вращающихся ножа, когда торт представляет собой одномерный круг ("пирог"),
- В Процедура с вращающимся ножом Робертсона-Уэбба предлагает еще более простое решение, используя только 1 вращающийся нож, когда торт двухмерный.
- Процедура с подвижным ножом
Рекомендации
- ^ Стромквист, Уолтер (1980). «Как правильно разрезать торт». Американский математический ежемесячник. 87 (8): 640. Дои:10.2307/2320951. JSTOR 2320951.
- ^ Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Честное разделение: от нарезки торта до разрешения споров. Издательство Кембриджского университета. ISBN 0-521-55644-9.
- ^ Важность этой преемственности объясняется здесь: «Процедура 3 ножей Стромквиста». Математическое переполнение. Получено 14 сентября 2014.
- ^ Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы резки торта: будьте честны, если можете. Натик, Массачусетс: А. К. Петерс. ISBN 978-1-56881-076-8. LCCN 97041258. ПР 2730675W.