Процедура «Движущийся нож» Левмора — Кук — это процедура завистливого разрезания торта на трёх участников. Она названа именами Сола Левмора и Элизабет Кук, предложивших её в 1981 году. Процедура предполагает, что торт двумерен, требует два ножа и четыре разреза, так что некоторые участники могут получить несвязные куски.
Процедура
Назовём участников именами Алиса, Боб и Карл.
Сначала Алиса разрезает торт на три равные (по её мнению) куска. Боб и Карл указывают на предпочтительные (для них) куски.
Простой случай: Боб и Карл указывают на различные куски. Каждый получает понравившийся кусок, а Алиса получает оставшийся.
Трудный случай: Боб и Карл указывают на тот же самый кусок. Скажем, пусть это будет кусок 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.
По мере движения ножа #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. Эта модификация даёт преимущество промолчавшему.
Левмор и Кук предложили обобщение их процедуры для четырёх участников, но позднее было показано, что их обобщение не во всех случаях работает.