Процедура Брамса – Тейлора – Цвикера - Википедия - Brams–Taylor–Zwicker procedure
В Процедура Брамса – Тейлора – Цвикера это протокол для резка торта без зависти среди 4 партнеров.[1]:126–128
В процедуре используется вариант Процедура Остина для двух партнеров и общих дробей. Эта процедура позволяет двум партнерам разделить весь торт на штук, каждая из которых стоит ровно для них обоих.
Основная процедура работает следующим образом.
А. Используйте процедуру Остина с и партнеры №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]
Рекомендации
- ^ Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Честное разделение: от нарезки торта до разрешения споров. Издательство Кембриджского университета. ISBN 0-521-55644-9.
- ^ Брамс, Стивен Дж .; Тейлор, Алан Д.; Цвикер, Уильям С. (1997). «Решение с движущимся ножом для отдела тортов без зависти из четырех человек». Труды Американского математического общества. 125 (2): 547–554. CiteSeerX 10.1.1.104.3390. Дои:10.1090 / s0002-9939-97-03614-9.