Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




13.02.2021


07.02.2021


24.01.2021


24.01.2021


24.01.2021





Яндекс.Метрика
         » » Процедура «Движущийся нож» Барбанеля — Брамса

Процедура «Движущийся нож» Барбанеля — Брамса

19.10.2021

Процедура «Движущийся нож» Барбанеля — Брамса — это процедура завистливого разрезания торта торта между тремя участниками. Процедура делает только два разреза, так что каждый участник получает один цельный кусок.

Главное преимущество процедуры перед более ранней процедурой «Движущийся нож» Стромквиста заключается в том, что требуется только два движущихся ножа вместо четырёх. Также более ранняя процедура «Движущийся нож» Робертсона — Уэбба требует всего одного ножа, но она работает только для двумерных тортов, в то время как процедура Барбанеля — Брамса работает и на одномерном торте. Предложена американскими учёными Джулиусом Барбанелем (род. 1951) и Стивеном Брамсом (род. 1940) в 2004 году.

Процедура

Первоначально каждый участник делает пометки, показывающие часть торта слева, которая (по мнению участника) оценивается ровно в 1/3. Выбирается самая левая метка. Предположим, что эту метку сделала Алиса. Алису просят сделать тогда вторую метку, так что (по её мнению) значение торта слева от пометки равно в точности 2/3. Таким образом, теперь есть две метки, которые делят торт ровно на три части (по мнению Алисы).

Боба и Карла просят оценить два куска торта справа. Есть несколько возможных случаев:

1. Боб и Карл предпочитают разные куски. В этом случае отдаём им по куску, которые они предпочитают, а Алисе отдаём крайний левый кусок, тем самым завершая делёж.

2. Боб и Карл предпочитают средний кусок. Алиса помещает два ножа по краям среднего куска и передвигает их внутрь данного куска так, чтобы два крайних куска после разрезания оставались в её глазах равными. Значение среднего куска уменьшается до тех пор, пока в некоторый момент Боб или Карл не посчитают его равным внешнему куску. Первый, кто так считает, должен воскликнуть «стоп» и получает внешний (равный по его мнению) кусок. Алиса получает второй внешний кусок, а промолчавший участник получает средний кусок.

2. Боб и Карл предпочитают крайний справа кусок. Алиса помещает ножи по краям среднего куска и передвигает их вправо одновременно так, что два куска слева после разрезания в её глазах будут одинаковыми. Значение правого куска уменьшается до тех пор, пока кто-нибудь, Боб или Карл, не посчитают, что значение этого куска равно значению одного из левых кусков. Первый, кто так считает, восклицает «стоп» и получает самый левый кусок. Алиса получает второй из левых кусков, а промолчавший получает правый кусок.

Делёж «плохого» торта

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