Задача про розрізання намиста

Приклад намиста, розділеного на 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 (11 травня). — 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 (December). — 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 (11 травня). — 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 (11 травня).
• Noga Alon. Splitting necklaces and measurable colorings of the real line // Proceedings of the American Mathematical Society. — 2008. — Т. 137, вип. 5 (November). — ISSN 1088-6826. — arXiv:1412.7996. — DOI:10.1090/s0002-9939-08-09699-8.
• Mark de Longueville, Rade T. Živaljević. Splitting multidimensional necklaces // Advances in Mathematics. — 2008. — Т. 218, вип. 3 (11 травня). — arXiv:math/0610800. — DOI:10.1016/j.aim.2008.02.003.
• Forest W. Simmons, Francis Edward Su. Consensus-halving via theorems of Borsuk-Ulam and Tucker // Mathematical Social Sciences. — 2003. — Т. 45, вип. 1 (February). — DOI:10.1016/s0165-4896(02)00087-2.

Посилання

• "Sneaky Topology" на YouTube, вступне відео, яке подає задачу з її топологічним розв'язанням.