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

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

Пример ожерелья, разделённого на k = 2 (то есть между двумя участниками дележа) и t = 2 (то есть два типа бусин, имеется 8 красных и 6 зелёных). Показаны 2 разреза — один из участников получает большую секцию, а другой получает оставшиеся два куска.

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

Вариации

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

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

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

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

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

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

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

Если $k$ является составным, доказательство будет следующим (демонстрируем для варианта разбиения по мере). Предположим, что $k=p\cdot q$. Имеется $t$ мер, каждая из которых оценивает всё ожерелье как $p\cdot q\cdot a_{i}$. С помощью $(p-1)\cdot t$ разрезов разобьём ожерелье на $p$ частей, так что мера $i$ каждой части в точности равна $q\cdot a_{i}$. С помощью $(q-1)\cdot t$ разрежем каждую часть на $q$ частей, так что мера $i$ каждой части равна в точности $a_{i}$. Имеется теперь $pq$ частей, таких что мера $i$ каждой части равна в точности $a_{i}$. Общее число разрезов равно $(p-1)\cdot t+p(q-1)\cdot t$, что в точности равно $(pq-1)\cdot t$.

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

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

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

если бусы на ожерелье расположены так, что возможно t-разрезание, то для двух подмножеств D₁ и D₂ набора $\{1,2,\dots ,t\}$, из которых не оба пусты, таких что $D_{1}\cap D_{2}=\varnothing$, существует $(t-1)$-разрезание, такое что:

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

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

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

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

Для любого $k\geqslant 1$ существует измеримая раскраска в $(k+3)$ цвета вещественной прямой, такая что никакой интервал не может быть справедливо разбит с помощью не более чем $k$ разрезов.

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

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

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

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

См. также

• Комбинаторика ожерелья
• Задача о восстановлении бус
• Точный делёж

Литература

• Noga Alon. Splitting Necklaces // Advances in Mathematics. — 1987. — Т. 63, вып. 3. — doi:10.1016/0001-8708(87)90055-7.
• Noga Alon, West D. B. The Borsuk-Ulam theorem and bisection of necklaces // Proceedings of the American Mathematical Society. — 1986. — Декабрь (т. 98, вып. 4). — doi:10.1090/s0002-9939-1986-0861764-9.
• I. Barany, S.B. Shlosman, A. Szucs. On a topological generalization of a theorem of Tverberg // Journal of the London Mathematical Society. — 1981. — Т. 2, вып. 23. — doi:10.1112/jlms/s2-23.1.158.
• Gábor Simonyi. Necklace bisection with one less cut than needed // Electronic Journal of Combinatorics. — 2008. — Т. 15, вып. N16.
• Noga Alon. Splitting necklaces and measurable colorings of the real line // Proceedings of the American Mathematical Society. — 2008. — Ноябрь (т. 137, вып. 5). — ISSN 1088-6826. — doi:10.1090/s0002-9939-08-09699-8. — arXiv:1412.7996.
• Mark de Longueville, Rade T. Živaljević. Splitting multidimensional necklaces // Advances in Mathematics. — 2008. — Т. 218, вып. 3. — doi:10.1016/j.aim.2008.02.003. — arXiv:math/0610800.
• Forest W. Simmons, Francis Edward Su. Consensus-halving via theorems of Borsuk-Ulam and Tucker // Mathematical Social Sciences. — 2003. — Февраль (т. 45, вып. 1). — doi:10.1016/s0165-4896(02)00087-2.

Ссылки

• "Sneaky Topology" на YouTube.