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



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

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

Вариации

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

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

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

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

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

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

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

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

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

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

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

    если бусы на ожерелье расположены так, что возможно t-разрезание, то для двух подмножеств D1 и D2 набора { 1 , 2 , … , t } {displaystyle {1,2,dots ,t}} , из которых не оба пусты, таких что D 1 ∩ D 2 = ∅ {displaystyle D_{1}cap D_{2}=varnothing } , существует ( t − 1 ) {displaystyle (t-1)} -разрезание, такое что:

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

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

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

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

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

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

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

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

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