Введение
Процедура движущихся ножей Стромквиста - это процедура резки торта без зависти между тремя игроками. Он назван в честь Уолтера Стромквиста, который представил его в 1980 году. Эта процедура была первой процедурой свободного движения ножа, разработанной для трех игроков. Для этого требуется четыре ножа, но только два разреза, так что каждый игрок получает одну соединенную фигуру. Нет естественного обобщения более чем на трех игроков, которое разделяет торт без дополнительных разрезов. Полученное разделение не обязательно эффективно.
Процедура
Судья перемещает меч слева направо над тортом, гипотетически разделяя его на маленький левый кусок и большой правый кусок. Каждый игрок перемещает нож над правильной фигурой, всегда держа ее параллельно мечу. Игроки должны двигать ножами непрерывно, не совершая никаких "прыжков". Когда любой игрок кричит "режь", торт разрезается мечом и ножом любого из игроков, который оказывается центральным из трех (то есть вторым по порядку от меча). Затем пирог делится следующим образом: кусочек слева от меча, который мы обозначаем левым, дается игроку, который первым крикнул "резать". Мы называем этого игрока "кричащим", а двух других - "тихими". Кусочек между мечом и центральным ножом, который мы обозначаем как Средний, дается оставшемуся игроку, чьи ножи ближе всего к мечу. Остальная фигура, Правая, передается третьему игроку.
The piece to the left of the sword, which we denote Left, is given to the player who first shouted "cut". We call this player the "shouter" and the other two players the "quieters". The piece between the sword and the central knife, which we denote Middle, is given to the remaining player whose knife is closest to the sword. The remaining piece, Right, is given to the third player.
Анализ
Теперь мы докажем, что любой игрок, использующий вышеуказанную стратегию, получает долю без зависти. Во-первых, рассмотрим два приглушателя. Каждому из них дается кусок, в котором находится его собственный нож, чтобы они не завидовали друг другу. Кроме того, из-за того, что они молчали, кусок, который они получают, в их глазах больше, чем у Левого, поэтому они также не завидуют кричащему. Кричащий получает левую, которая равна фигуре, которую они могли бы получить, оставаясь молчаливыми и больше, чем третья фигура, поэтому кричащий не завидует никому из тишины. Следуя этой стратегии, каждый человек получает самую большую или одну из самых больших частей по своей собственной оценке, и поэтому разделение не влечет зависти. Тот же анализ показывает, что разделение свободно от зависти даже в несколько вырожденном случае, когда есть два крика, и самая левая часть дается любому из них.
Разделяем "плохой" торт
Процедура движущихся ножей может быть адаптирована для разделения работы, разделяя торт с отрицательным значением.