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

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

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

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

Варианты [ править ]

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

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

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

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

Доказательство [ править ]

Дело $k=2$ можно доказать с помощью теоремы Борсука-Улама . ^[2]

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

Когда $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$ .

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

Разделение случайных ожерелий [ править ]

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

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

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

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

Наконец, когда $t$ это странно и $s=(t+1)/2$

\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 }, не обоих пустых , таких, что $D_{1}\cap D_{2}=\varnothing$ , существует ( t − 1)-разбиение такое, что:

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

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

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

Отрицательный результат [ править ]

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

Разделение многомерных ожерелий [ править ]

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

Алгоритм аппроксимации [ править ]

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

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[Alon_1987-1] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж Алон, Нога (1987). «Раскалывание ожерелья» . Достижения в математике . 63 (3): 247–253. дои : 10.1016/0001-8708(87)90055-7 .

[Alon_1986-2] Перейти обратно: Перейти обратно: ^а ^б Алон, Нога; Уэст, Дуглас Б. (декабрь 1986 г.). «Теорема Борсука-Улама и деление ожерелья пополам» . Труды Американского математического общества . 98 (4): 623–628. дои : 10.1090/s0002-9939-1986-0861764-9 .

[BSS-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 ].

[Simonyi_2008-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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]