WikiDer > Процедура Брамса – Тейлора – Цвикера - Википедия

В Процедура Брамса – Тейлора – Цвикера это протокол для резка торта без зависти среди 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]

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