Процедура Брамса – Тейлора – Цвикера - Brams–Taylor–Zwicker procedure

В Процедура Брамса – Тейлора – Цвикера это протокол для резка торта без зависти среди 4 партнеров.^{[1]:126–128}

В процедуре используется вариант Процедура Остина для двух партнеров и общих дробей. Эта процедура позволяет двум партнерам разделить весь торт на ${\displaystyle k}$ штук, каждая из которых стоит ровно ${\displaystyle 1/k}$ для них обоих.

Основная процедура работает следующим образом.

А. Используйте процедуру Остина с ${\displaystyle k=4}$ и партнеры №1 и №2. Итак, у нас есть 4 штуки, которые, по мнению первых двух партнеров, имеют одинаковую стоимость - 1/4.

Б. Партнер № 3 обрезает одну деталь, чтобы создать двусторонний галстук для самого большого; партнеры теперь выбирают фишки в обратном порядке (№4, №3, №2, №1). Обрезанный кусок должен взять №4 или №3. Это создает незавидное разделение всего торта без обрезков (это похоже на Дискретная процедура Селфриджа-Конвея ).

С. Теперь обрезки разделены. Предположим, что w.l.o.g. тот №3 взял обрезанный кусок. Мы снова используем процедуру Остина с обрезками и партнерами # 4 и # 1, чтобы создать 4 части, каждая из которых равна ровно 1/4 для них обоих. Поскольку партнеры №1 и №2 имеют неоспоримое преимущество перед любым партнером, который взял обрезанный кусок, мы можем позволить №3 быть первым, кто выберет кусок из обрезки, затем №2, затем №4 и №1.

Эффективность

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

Однако количество разрезов ограничено. Процедура Остина требует 2 надрезов, чтобы разделить торт между двумя людьми с точной стоимостью 1/2; каждую из этих частей следует разделить еще на 2 разреза, чтобы получить 4 части с точным значением 1/4. Таким образом, в общей сложности для этапа A требуется 6 разрезов. Один разрез выполняется на этапе B, а еще 6 разрезов - на этапе C, всего 13 разрезов.

В усовершенствованном варианте процедуры Брамса – Тейлора – Цвикера используется всего 11 разрезов.^[2]

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

1. Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Честное разделение: от нарезки торта до разрешения споров. Издательство Кембриджского университета. ISBN  0-521-55644-9.
2. Брамс, Стивен Дж .; Тейлор, Алан Д.; Цвикер, Уильям С. (1997). «Решение с движущимся ножом для отдела тортов без зависти из четырех человек». Труды Американского математического общества. 125 (2): 547–554. CiteSeerX  10.1.1.104.3390. Дои:10.1090 / s0002-9939-97-03614-9.