Задача о разрезании ожерелья

(перенаправлено с «Задача дележа ожерелья»)

Задача о разрезании ожерелья — это название серии задач из комбинаторики и теории меры. Задачу сформулировали и решили математики Нога Алон[1] и Дуглас Б. Вест[2].

Стилизованный рисунок ожерелья с 8 красными и 6 зелёными жемчужинами. Жемчужины насажены на неполную эллиптическую чёрную кривую, которая представляет нитку. Разрыв в кривой представляет застёжку (открытую на диаграмме), которая может быть закрыта, когда ожерелье помещается на шее. Имеются две короткие жирные чёрточки на нитке ожерелья. Начиная слева ожерелье имеет вид: RRRGRBRRGRRGGBGG, где «R» означает «красную жемчужину», «G» означает «зелёную жемчужину»
Пример ожерелья, разделённого на k = 2 (то есть между двумя участниками дележа) и t = 2 (то есть два типа бусин, имеется 8 красных и 6 зелёных). Показаны 2 разреза — один из участников получает большую секцию, а другой получает оставшиеся два куска.

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

Вариации

править

Следующие варианты задачи были решены в оригинальной статье:

  1. Дискретное разрезание[3]: Ожерелье имеет   бусин. Бусины имеют   различных цветов. Имеется   бусин каждого цвета  , где   является положительным целым числом. Следует разрезать ожерелье на   долей (не обязательно непрерывных), каждая из которых имеет ровно   бусин цвета i. Следует использовать не более   разрезов. Заметим, что если бусины каждого цвета располагаются на ожерелье непрерывно, то нужно по меньшей мере   разрезов внутри каждого цвета, так что значение   оптимально.
  2. Непрерывное разрезание[4]: Ожерелье является вещественным отрезком  . Каждая точка отрезка выкрашена в один из   цветов. Для любого цвета   множество точек, выкрашенных цветом   измеримо по Лебегу и имеет длину  , где   неотрицательное вещественное число. Следует разбить отрезок на   частей (не обязательно непрерывных), так что в каждой части полная длина цвета   в точности равна  . Использовать не более   разрезов.
  3. Разбиение по мере[5]: Ожерелье является вещественным отрезком. Существует   различных мер на отрезке, все абсолютно непрерывны по длине. Мера всего ожерелья по мере   равна  . Следует разбить отрезок на   частей (не обязательно непрерывных), так что мера каждой части по мере   в точности равна  . Использовать не более   разрезов. Это обобщение теоремы Хобби — Райса и используется для получения точного дележа торта.

Каждая задача может быть решена следующим образом:

  • Дискретное разрезание может быть решено непрерывным разрезанием, поскольку дискретное ожерелье может быть сведено к раскраске вещественного отрезка  , в котором каждый отрезок длины 1 раскрашен цветом соответствующей бусины. В случае, когда непрерывное разбиение пытается разрезать внутри бусины, разрез может быть смещён так, что разрезы окажутся только между бусинами[6].
  • Непрерывное разрезание может быть осуществлено разбиением по мере, поскольку раскраска отрезка в   цветов может быть превращена в набор   мер, так что мера   отражает длину цвета  . Обратное тоже верно — разбиение по мере можно получить путём непрерывного разрезания с помощью более тонкого сведения[7].

Доказательство

править

Случай   может быть доказан по теореме Борсука — Улама[2].

Если   является нечётным простым числом, доказательство использует обобщение теоремы Борсука — Улама[8].

Если   является составным, доказательство будет следующим (демонстрируем для варианта разбиения по мере). Предположим, что  . Имеется   мер, каждая из которых оценивает всё ожерелье как  . С помощью   разрезов разобьём ожерелье на   частей, так что мера   каждой части в точности равна  . С помощью   разрежем каждую часть на   частей, так что мера   каждой части равна в точности  . Имеется теперь   частей, таких что мера   каждой части равна в точности  . Общее число разрезов равно  , что в точности равно  .

Дальнейшие результаты

править

На один разрез меньше, чем необходимо

править

В случае двух воров [то есть k = 2] и t цветов, справедливое разрезание потребует не более t разрезов. Если, однако, только   разрезов допустимо, венгерский математик Габор Шимоньи[9] показал, что два вора могут достичь почти справедливого дележа в следующем смысле:

если бусы на ожерелье расположены так, что возможно t-разрезание, то для двух подмножеств D1 и D2 набора  , из которых не оба пусты, таких что  , существует  -разрезание, такое что:

  • Если цвет  , то часть 1 имеет больше бусин цвета i чем часть 2;
  • Если цвет  , то часть 2 имеет больше бусин цвета i чем часть 1;
  • Если цвет i не принадлежит ни одной из частей   и  , обе части имеют одинаковое число бусинок цвета i.

Это означает, что если воры имеют предпочтения в форме двух множеств «предпочтений» D1 и D2, из которых хотя бы одно не пусто, существует  -разбиение, такое что вор 1 получит больше бусин из его множества предпочтения D1, чем вор 2, вор 2 получит больше бусин из его множества предпочтения D2, чем вор 1, а остаток будет одинаков.

Симоний приписывает Габору Тардошу замечание, что вышеприведённый результат является прямым обобщение исходной теоремы Алона об ожерелье в случае k = 2. Либо ожерелье имеет  -разрезание, либо нет. В случае, если имеет, нечего и доказывать. Если же не имеет, мы можем добавить одну фиктивного цвета бусинку в ожерелье и образовать два множества, множество D1, состоит из этого фиктивного цвета, а множество D2 пусто. Результат Симония показывает, что имеется t-разрезание с равным числом цветов каждого реального цвета.

Отрицательный результат

править

Для любого   существует измеримая раскраска в   цвета вещественной прямой, такая что никакой интервал не может быть справедливо разбит с помощью не более чем   разрезов[10].

Разрезание многомерного ожерелья

править

Результат может быть распространён на вероятностных мер n, определённых на d-мерном кубе с любыми комбинациями   гиперплоскостей, параллельных сторонам для k воров[11].

Аппроксимационный алгоритм

править

Аппроксимационный алгоритм разрезания ожерелья может быть получен из алгоритма для согласованного уполовинивания[12].

См. также

править

Примечания

править
  1. Alon, 1987, с. 247—253.
  2. 1 2 Alon, West, 1986, с. 623—628.
  3. Alon, 1987, с. 247—253 Th 1.1.
  4. Alon, 1987, с. 247—253 Th 2.1.
  5. Alon, 1987, с. 247—253 Th 1.2.
  6. Alon, 1987, с. 249.
  7. Alon, 1987, с. 252—253.
  8. Barany, Shlosman, Szucs, 1981, с. 158–164.
  9. Simonyi, 2008.
  10. Alon, 2008, с. 1593–1599.
  11. de Longueville, Živaljević, 2008, с. 926—939.
  12. Simmons, Su, 2003, с. 15–25.

Литература

править

Ссылки

править