Проблема раскола ожерелья

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

Расщепление ожерелья — живописное название, данное нескольким связанным проблемам комбинаторики и теории меры . Его название и решения принадлежат математикам Ноге Алону ^[1] и Дугласу Б. Уэсту . ^[2]

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

Варианты

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

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

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

• Дискретное расщепление можно решить путем непрерывного расщепления, поскольку дискретное ожерелье можно преобразовать к раскраске вещественного интервала, в которой каждый интервал длины 1 раскрашивается в цвет соответствующей бусины. В случае, если непрерывное расщепление пытается разрезать внутренние бусины, разрезы можно постепенно сдвигать так, чтобы они выполнялись только между бусинами. ^{[1] : 249} ${\displaystyle [0,k\cdot n]}$
• Непрерывное разделение можно решить путем разделения по мере, поскольку раскраску интервала в цвета можно преобразовать в заданные меры, например, мера измеряет общую длину цвета . Верно и обратное: разделение меры можно решить путем непрерывного разделения, используя более сложную редукцию. ^{[1] : 252–253} ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle i}$ ${\displaystyle i}$

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

Этот случай можно доказать с помощью теоремы Борсука-Улама . ^[2] ${\displaystyle k=2}$

Когда – нечетное простое число , доказательство предполагает обобщение теоремы Борсука-Улама. ^[3] ${\displaystyle k}$

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

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

Разделение случайных ожерелий

В некоторых случаях случайные ожерелья можно разделить поровну, используя меньшее количество разрезов. Математики Нога Алон, Дор Эльбойм, Габор Тардос и Янош Пах изучили типичное количество разрезов, необходимое для того, чтобы разделить случайное ожерелье между двумя ворами. ^[4] В рассмотренной ими модели ожерелье выбирается равномерно случайным образом из набора ожерелий t цветов и m бусин каждого цвета. Поскольку m стремится к бесконечности, вероятность того, что ожерелье можно разделить с помощью ⌊(t + 1)/2⌋ разрезов или меньше, стремится к нулю, а вероятность того, что ожерелье можно разделить с помощью ⌊(t + 1)/2⌋ + 1 разрезы отделены от нуля. Точнее, пусть X  =  X ( t , m ) будет минимальным количеством разрезов, необходимых для разделения ожерелья. Следующее справедливо, когда m стремится к бесконечности. Для любого ${\displaystyle s<(t+1)/2}$

${\displaystyle \mathbb {P} (X=s)=\Theta {\big (}m^{s-(t+1)/2}{\big )}.}$

Для любого ${\displaystyle (t+1)/2<s\leq t}$

${\displaystyle \mathbb {P} (X=s)=\Theta (1).}$

Наконец, когда нечетно и ${\displaystyle t}$ ${\displaystyle s=(t+1)/2}$

${\displaystyle \mathbb {P} (X=s)=\Theta {\big (}(\log m)^{-1}{\big )}.}$

Можно также рассмотреть случай, когда количество цветов стремится к бесконечности. Когда m=1 и t стремится к бесконечности, количество требуемых разрезов составляет не более 0,4t и с высокой вероятностью не менее 0,22t . Предполагается, что существует некоторое 0,22 <  c  < 0,4 такое, что X ( t ,1)/ t   сходится к c по распределению.

На один разрез меньше, чем нужно

В случае двух воров (т. е. k = 2) и t цветов для справедливого разделения потребуется не более t разрезов. Однако если  доступно только t − 1 разрезов, венгерский математик Габор Симони ^[5] показывает, что два вора могут добиться почти справедливого разделения в следующем смысле.

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

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

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

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

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

Для каждого существует измеримая -раскраска реальной линии такая, что ни один интервал не может быть справедливо разбит не более чем с помощью разрезов. ^[6] ${\displaystyle k\geq 1}$ ${\displaystyle (k+3)}$ ${\displaystyle k}$

Разделение многомерных ожерелий

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

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

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

Смотрите также

• Комбинаторное ожерелье
• Проблема с ожерельем
• Точное деление

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

1. Алон, Нога (1987). «Расщепляющиеся ожерелья». Достижения в математике . 63 (3): 247–253. дои : 10.1016/0001-8708(87)90055-7 .
2. Алон, Нога; Уэст, Дуглас Б. (декабрь 1986 г.). «Теорема Борсука-Улама и деление ожерелья пополам» . Труды Американского математического общества . 98 (4): 623–628. дои : 10.1090/s0002-9939-1986-0861764-9 .
3. И.Барани, С.Б.Шлосман и А.Щуч (1981). «О топологическом обобщении теоремы Тверберга». Журнал Лондонского математического общества . 2 (23): 158–164. CiteSeerX 10.1.1.640.1540 . дои : 10.1112/jlms/s2-23.1.158. 
4. Алон, Нога; Эльбойм, Дор; Тардос, Габор; Пах, Янош (2021). «Случайные ожерелья требуют меньше разрезов». arXiv : 2112.14488 [math.CO].
5. Симони, Габор (2008). «Ожерелье пополам, на один разрез меньше необходимого». Электронный журнал комбинаторики . 15 (Н16). дои : 10.37236/891 .
6. Алон, Нога (25 ноября 2008 г.). «Разделение ожерелья и измеримые раскраски настоящей линии». Труды Американского математического общества . 137 (5): 1593–1599. arXiv : 1412.7996 . дои : 10.1090/s0002-9939-08-09699-8 . ISSN  1088-6826.
7. де Лонгвиль, Марк; Раде Т. Живальевич (2008). «Расщепление многомерных ожерелий». Достижения в математике . 218 (3): 926–939. arXiv : math/0610800 . дои : 10.1016/j.aim.2008.02.003 .
8. Симмонс, Форест В.; Су, Фрэнсис Эдвард (февраль 2003 г.). «Разделение половины консенсуса с помощью теорем Борсука-Улама и Такера». Математические социальные науки . 45 (1): 15–25. CiteSeerX 10.1.1.203.1189 . дои : 10.1016/s0165-4896(02)00087-2. 

Внешние ссылки

• «Sneaky Topology» на YouTube, вводное видео, представляющее проблему и ее топологическое решение.