WikiDer > Процедура перемещения ножей Левмора – Кука - Википедия

Levmore–Cook moving-knives procedure - Wikipedia

В Процедура с движущимися ножами Левмора – Кука это процедура для резка торта без зависти среди трех партнеров. Он назван в честь Саул X. Левмор и Элизабет Ранний Кук, которая представила его в 1981 году.[1]Предполагается, что торт является двумерный. Требуется два ножи и четыре разреза, поэтому некоторые партнеры могут получить отсоединенные части.

Процедура

Назовем партнеров Алисой, Бобом и Карлом.

Вначале Алиса разрезает торт на три равных на ее глазах части. Боб и Карл указывают на свои любимые произведения.

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

Трудный случай: Боб и Карл указывают на одно и то же. Скажем, это фигура X, а другие фигуры - Y и Z. Теперь Алиса берет два ножа и перемещает их одновременно над фигурой X:

    • Нож №1 перемещен по горизонтали слева от части X справа от нее. Он делит деталь X на две части: левую деталь XL и правую деталь XR.
    • Нож №2 перемещен вертикально, слева от Ножа №1, так что XL делится в ее глазах на две равные части: левый верхний XLT и левый нижний XLB.

Первоначально XR = X, поэтому для Боба и Карла он больше, чем Y и Z. Более того, изначально XLT и XLB пусты, поэтому XR больше, чем две пары: Y + XLT и Z + XLB.

По мере того, как Knife # 1 движется вправо, XR уменьшается, а XLT и XLB растут. В какой-то момент Боб или Карл думают, что XR равен одной из двух пар. Первый, кто думает, что есть равенствокричит "стоп!" и получает свою выбранную пару. Алиса получает вторую пару, а тот, кто не кричит, получает XR.

Анализ

Разбираем случай, когда Боб крикнул "стоп!" и выбрал пару Y + XLT. Алиса получает Z + XLB, а Карл получает XR. Разделение не вызывает зависти, потому что:

  • Для Алисы Z> X> XR, поэтому Алиса не завидует Карлу. Более того, Z = Y и XLB = XLT, поэтому Алиса не завидует Бобу.
  • Для Боба Y + XLT = XR> Z + XLB, поэтому Боб не завидует.
  • Для Карла XR больше обеих пар (так как он не кричал), поэтому он не завидует.

Остальные случаи аналогичный.

Варианты

Можно позволить крикуну выбрать одну из четырех пар: Y + XLT, Y + XLB, Z + XLT, Z + XLB. Эта модификация благоприятствует тому, кто не кричит, поскольку кричащий обычно кричит «Стоп» раньше.[2]

Левмор и Кук представили обобщение их процедуры для 4 партнеров. Однако позже было показано, что это обобщение работает не во всех случаях.[3]:122–124

Смотрите также

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

Рекомендации

  1. ^ Сол X. Левмор и Элизабет Ранний Кук (1981). Супер стратегии для головоломок и игр. Гарден-Сити, Нюрл =https://catalog.lib.uchicago.edu/vufind/Record/4476190: Doubleday.CS1 maint: использует параметр авторов (связь) CS1 maint: location (связь)
  2. ^ Цитрон, Рон (2012). «Алгоритмы резки торта - Лекция 8» (PDF). Получено 27 августа 2016.
  3. ^ Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Честное разделение: от нарезки торта до разрешения споров. Издательство Кембриджского университета. ISBN 0-521-55644-9.