Перегляд вихідного коду сторінки Задача про розрізання намиста

[[Файл:Collier-de-perles-rouge-vert.svg|альт=Стилізований малюнок [[Намисто (комбінаторика)|намиста]] з 8 червоними і 6 зеленими перлинами. Перлини насаджені на неповну еліптичну чорну криву, яка представляє нитку. Розрив у кривій представляє застібку (відкриту на діаграмі), яку можна закрити, коли намисто поміщається на шию. Є дві короткі жирні рисочки на нитці намиста. Починаючи зліва, намисто має вигляд: RRRGRBRRGRRGGBGG, де «R» означає «червону перлину», «G» означає «зелену перлину»|міні| Приклад намиста, розділеного на ''k'' = 2 (тобто між двома учасниками поділу) і ''t'' = 2 (тобто два типи намистин, є 8 червоних і 6 зелених). Показані 2 розрізи&nbsp;— один з учасників отримує більшу частину, а другий отримує два інші шматки.]]
'''Задача про розрізання намиста'''&nbsp;— це назва серії задач з [[Комбінаторика|комбінаторики]] і [[Міра множини|теорії міри]]. Задачу сформулювали й розв'язали математики [[Нога Алон]]{{Sfn|Alon|1987|с=247-253}} і {{Нп|Дуглас Вест|Дуглас Б. Вест|en|Douglas West (mathematician)}}{{Sfn|Alon, West|1986|с=623-628}}.

Основні умови визначають [[Намисто (комбінаторика)|намисто]] з намистинами різних кольорів. Намисто слід розділити між кількома учасниками або злодіями (часто передбачається, що намисто крадене), так, щоб кожен учасник отримав би певну кількість намистин кожного кольору. При цьому, число ''розрізів'' має бути якомога меншим (щоб втратити якомога менше металу ланцюжка, що з'єднує намистинки).

== Варіації ==
В оригінальній статті розв'язано такі варіанти задачі:

# '''Дискретне розрізання'''{{Sfn|Alon|1987|с=247-253 Th 1.1}}. Намисто має <math>k\cdot n</math> намистин. Намистини мають <math>t</math> різних кольорів. Є <math>k\cdot a_i</math> намистин кожного кольору <math>i</math>, де <math>a_i</math> є додатним цілим числом. Слід розрізати намисто на <math>k</math> часток (не обов'язково неперервних), кожна з яких має рівно <math>a_i</math> намистин кольору ''i''. Слід використовувати не більше <math>(k-1)t</math> розрізів. Зауважимо, що якщо намистини кожного кольору розташовуються на намисті неперервно, то потрібно щонайменше <math>k-1</math> розрізів усередині кожного кольору, так що значення <math>(k-1)t</math> оптимальне.
# '''Неперервне розрізання'''{{Sfn|Alon|1987|с=247-253 Th 2.1}}. Намисто є дійсним відрізком <math>[0,k\cdot n]</math>. Кожна точка відрізка пофарбована в один з <math>t</math> кольорів. Для будь-якого кольору <math>i</math> множина точок, пофарбованих у колір <math>i,</math> [[Міра Лебега|вимірна за Лебегом]] і має довжину <math>k\cdot a_i</math>, де <math>a_i</math> невід'ємне дійсне число. Слід розбити відрізок на <math>k</math> частин (не обов'язково неперервних), так щоб у кожній частині повна довжина кольору <math>i</math> точно дорівнювала <math>a_i</math>. Використати не більше <math>(k-1)t</math> розрізів.
# '''Розбиття за мірою'''{{Sfn|Alon|1987|с=247-253 Th 1.2}}. Намисто є дійсним відрізком. Існує <math>t</math> різних мір на відрізку, все абсолютно неперервні за довжиною. Міра всього намиста за мірою <math>i</math> дорівнює <math>k\cdot a_i</math>. Слід розбити відрізок на <math>k</math> частин (не обов'язково неперервних), так щоб міра кожної з частин за мірою <math>i</math> точно дорівнювала <math>a_i</math>. Використати не більше <math>(k-1)t</math> розрізів. Це узагальнення {{Нп|теорема Гоббі — Райса|теореми Гоббі — Райса|ru|Теорема Хобби — Райса}} і його використовують для отримання [[Точний поділ|точного поділу]] [[Задача справедливого розрізання торта|торта]].

Кожну з задач можна розв'язати таким чином:

* Дискретне розрізання можна реалізувати як неперервне розрізання, оскільки дискретне намисто можна звести до розфарбування дійсного відрізка <math>[0,k\cdot n]</math>, в якому кожен відрізок довжини 1 розфарбовано кольором відповідної намистини. У разі, коли неперервне розбиття потребує розрізу всередині намистини, розріз можна змістити так, що розрізи виявляться тільки між намистинами{{Sfn|Alon|1987|с=249}}.
* Неперервне розрізання можна здійснити розбиттям за мірою, оскільки розфарбування відрізка в <math>t</math> кольорів можна перетворити на набір <math>t</math> мір, так що міра <math>i</math> відображає довжину кольору <math>i</math>. Обернене теж істинне&nbsp;— розбиття за мірою можна отримати неперервним розрізанням за допомогою тоншого зведення{{Sfn|Alon|1987|с=252-253}}.

== Доведення ==
Випадок <math>k=2</math> можна довести за [[Теорема Борсука — Уляма|теоремою Борсука&nbsp;— Уляма]]{{Sfn|Alon, West|1986|с=623-628}}.

Якщо <math>k</math> є непарним [[Просте число|простим числом]], доведення використовує узагальнення теореми Борсука&nbsp;— Уляма{{Sfn|Barany, Shlosman, Szucs|1981|с=158–164}}.

Якщо <math>k</math> є [[Складене число|складеним]], доведення буде таким (демонструємо для варіанту розбиття за мірою). Припустимо, що <math>k=p\cdot q</math>. Є <math>t</math> мір, кожна з яких оцінює все намисто, як <math>p\cdot q\cdot a_i</math>. За допомогою <math>(p-1)\cdot t</math> розрізів розіб'ємо намисто на <math>p</math> частин, так щоб міра <math>i</math> кожної частини точно дорівнювала <math>q\cdot a_i</math>. За допомогою <math>(q-1)\cdot t</math> розріжемо кожну частину на <math>q</math> частин, так щоб міра <math>i</math> кожної частини дорівнювала точно <math>a_i</math>. Є тепер <math>p q</math> частин, таких, що міра <math>i</math> кожної частини дорівнює точно <math>a_i</math>. Загальне число розрізів дорівнює <math>(p-1)\cdot t + p (q-1)\cdot t</math>, що точно дорівнює <math>(pq-1)\cdot t</math>.

== Подальші результати ==

=== На один розріз менше, ніж необхідно ===
У випадку двох злодіїв [тобто ''k'' = 2] і ''t'' кольорів, справедливе розрізання вимагатиме не більше, ніж ''t'' розрізів. Якщо, проте, тільки <math>t - 1</math> розрізів припустимо, угорський математик Габор Шимоньї{{Sfn|Simonyi|2008}} показав, що два злодії можуть досягти майже справедливого поділу в такому сенсі.

Якщо намистини на намисті розташовані так, що можливо ''t''-розрізання, то для двох підмножин ''D''<sub>1</sub> і ''D''<sub>2</sub> набору <math>\{1,2,\dots,t\}</math>, з яких ''не обидва порожні'', таких що <math>D_1\cap D_2=\varnothing</math>, існує <math>(t-1)</math>-розрізання, таке що:

* Якщо колір <math>i\in D_1</math>, то частина 1 має більше намистин кольору ''i'' ніж частина 2;
* Якщо колір <math>i\in D_2</math>, то частина 2 має більше намистин кольору ''i'' ніж частина 1;
* Якщо колір ''i'' не належить жодній з частин <math>D_1</math> і <math>D_2</math>, обидві частини мають однакову кількість намистин кольору ''i''.

Це означає, що якщо злодії мають переваги у формі двох множин «переваг» ''D''<sub>1</sub> і ''D''<sub>2</sub>, з яких хоча б одна не порожня, існує <math>(t-1)</math>-розбиття, таке що злодій 1 отримає більше намистин зі множини його переваги ''D''<sub>1</sub>, ніж злодій 2, злодій 2 одержить більше намистин зі множини його переваги ''D''<sub>2</sub>, ніж злодій 1, а залишок буде однаковий.

Симоній приписує Габору Тардошу зауваження, що наведений результат є прямим узагальненням вихідної теореми Алона про намисто у випадку ''k'' = 2. Або намисто має <math>(t-1)</math>-розрізання, або ні. У разі, якщо має, нічого й доводити. Якщо ж не має, ми можемо додати в намисто одну намистину фіктивного кольору й утворити дві множини: множина ''D''<sub>1</sub>, складається з цього фіктивного кольору, а множина ''D''<sub>2</sub> порожня. Результат Симонія показує, що є ''t''-розрізання з рівним числом кольорів кожного реального кольору.

=== Негативний результат ===
Для будь-якого <math>k\geqslant 1</math> існує вимірне розфарбування в <math>(k+3)</math> кольори дійсної прямої, таке що ніякого інтервалу не можна справедливо розбитий за допомогою не більше ніж <math>k</math> розрізів{{Sfn|Alon|2008|с=1593–1599}}.

=== Розрізання багатовимірного намиста ===
Результат можна узагальнити на ''n'' ймовірнісних мір, визначених на ''d''-вимірному кубі з будь-якими комбінаціями <math>n(k-1)</math> гіперплощин, паралельних сторонам для ''k'' злодіїв{{Sfn|de Longueville, Živaljević|2008|с=926-939}}.

=== Апроксимаційний алгоритм ===
Апроксимаційний алгоритм розрізання намиста можна отримати з алгоритму для [[Точний поділ|погодженого половинення]]{{Sfn|Simmons, Su|2003|с=15–25}}.

== Див. також ==
* [[Намисто (комбінаторика)]]
* [[Задача про відновлення намиста]]
* [[Точний поділ]]

== Примітки ==
{{Reflist|2}}

== Література ==
{{Refbegin|colwidth=30em}}
* {{Стаття|doi=10.1016/0001-8708(87)90055-7|ref=Alon|author=Noga Alon|title=Splitting Necklaces|видання=Advances in Mathematics|date=1987|том=63|issue=3}}
* {{Стаття|ref=Alon, West|author=Noga Alon, West D. B.|title=The Borsuk-Ulam theorem and bisection of necklaces|видання=Proceedings of the American Mathematical Society|місяць=December|date=1986|том=98|issue=4|doi=10.1090/s0002-9939-1986-0861764-9}}
* {{Стаття|url=http://jlms.oxfordjournals.org/content/s2-23/1/158.full.pdf|title=On a topological generalization of a theorem of Tverberg|author=I. Barany, S.B. Shlosman, A. Szucs|ref=Barany, Shlosman, Szucs|видання=Journal of the London Mathematical Society|date=1981|том=2|issue=23|doi=10.1112/jlms/s2-23.1.158}}
* {{Стаття|ref=Simonyi|author=Gábor Simonyi|title=Necklace bisection with one less cut than needed|видання=Electronic Journal of Combinatorics|том=15|date=2008|issue=N16}}
* {{Стаття|видання=Proceedings of the American Mathematical Society|title=Splitting necklaces and measurable colorings of the real line|місяць=November|date=2008|doi=10.1090/s0002-9939-08-09699-8|issn=1088-6826|том=137|issue=5|ref=Alon|author=Noga Alon|arxiv=1412.7996}}
* {{Стаття|doi=10.1016/j.aim.2008.02.003|author=Mark de Longueville, Rade T. Živaljević|ref=de Longueville, Živaljević|title=Splitting multidimensional necklaces|видання=Advances in Mathematics|date=2008|том=218|issue=3|arxiv=math/0610800}}
* {{Стаття|author=Forest W. Simmons, Francis Edward Su|ref=Simmons, Su|місяць=February|date=2003|видання=Mathematical Social Sciences|title=Consensus-halving via theorems of Borsuk-Ulam and Tucker|том=45|issue=1|doi=10.1016/s0165-4896(02)00087-2}}
{{Refend}}

== Посилання ==
* {{YouTube|yuVqxCSsE7c|title="Sneaky Topology"|link=no}}, вступне відео, яке подає задачу з її топологічним розв'язанням.
[[Категорія:Математичні задачі]]
[[Категорія:Дискретна геометрія]]
[[Категорія:Комбінаторика слів]]
[[Категорія:Справедливий поділ]]