Problém se stříháním náhrdelníku

Problém řezání náhrdelníku je název řady problémů z kombinatoriky a teorie míry . Problém formulovali a řešili matematici Noga Alon [1] a Douglas B. West [2] .

Základní podmínky definují náhrdelník s korálky různých barev. Náhrdelník by měl být rozdělen mezi více účastníků nebo zlodějů (často se předpokládá, že je náhrdelník odcizen), aby každý účastník obdržel určitý počet korálků každé barvy. Kromě toho by měl být počet řezů co nejmenší (aby se v řetězu spojujícím korálky ztratilo co nejméně kovu).

Variace

V původním článku byly vyřešeny následující varianty problému:

Diskrétní střih [3] : Náhrdelník má korálky. Korálky jsou různých barev. Jsou zde korálky každé barvy , kde je kladné celé číslo. Náhrdelník byste měli rozřezat na části (ne nutně souvislé), z nichž každá má přesně korálky barvy i . Neměly by být použity žádné další řezy. Všimněte si, že pokud jsou korálky každé barvy uspořádány na náhrdelníku souvisle, pak potřebujete alespoň řezy uvnitř každé barvy, aby byla hodnota optimální. $k\cdot n$ $t$ $k\cdot a_{i}$ $i$ $a_{i}$ $k$ $a_{i}$ $(k-1)t$ $k-1$ $(k-1)t$
Kontinuální stříhání [4] : Náhrdelník je skutečný segment . Každý bod segmentu je obarven jednou z barev. Pro jakoukoli barvu je množina bodů obarvených barvou Lebesgue měřitelná a má délku , kde je nezáporné reálné číslo. Měli byste segment rozdělit na části (ne nutně souvislé), takže v každé části je celková délka barvy přesně rovna . Nepoužívejte žádné další řezy. $[0,k\cdot n]$ $t$ $i$ $já,$ $k\cdot a_{i}$ $a_{i}$ $k$ $i$ $a_{i}$ $(k-1)t$
Rozdělení podle míry [5] : Náhrdelník je skutečný segment. Na segmentu jsou různé míry, všechny absolutně spojité délky. Míra celého náhrdelníku v míře je . Segment by měl být rozdělen na části (ne nutně spojité), takže míra každé části v míře je přesně rovna . Nepoužívejte žádné další řezy. Toto je zobecnění Hobby-Riceova teorému a používá se k získání přesného rozdělení koláče . $t$ $i$ $k\cdot a_{i}$ $k$ $i$ $a_{i}$ $(k-1)t$

Každý úkol lze vyřešit následujícím způsobem:

Diskrétní střih lze řešit průběžným střihem, protože diskrétní náhrdelník lze redukovat na skutečné zbarvení čáry , ve kterém je každý segment čáry délky 1 obarven barvou odpovídajícího korálku. V případě, že se průběžná přepážka pokouší řezat uvnitř korálku, lze řez posunout tak, aby řezy byly pouze mezi korálky [6] . $[0,k\cdot n]$
Kontinuální řezání lze provádět rozdělením podle míry, protože zbarvení segmentu v barvách lze změnit na sadu taktů, takže míra odráží délku barvy . Platí to i obráceně - přepážku podle míry lze získat kontinuálním řezáním pomocí jemnější redukce [7] . $t$ $t$ $i$ $i$

Důkaz

Případ lze dokázat Borsuk-Ulamovou větou [2] . $k=2$

Jestliže je liché prvočíslo , důkaz používá zobecnění Borsuk-Ulamovy věty [8] . $k$

Pokud je kompozit , bude důkaz následující (demonstrujeme pro možnost rozdělení podle míry). Předpokládejme, že . Jsou míry, z nichž každá hodnotí celý náhrdelník jako . Pomocí střihů rozdělíme náhrdelník na díly tak, aby se míra každého dílu přesně rovnala . Každou část nařežeme s pomocí , tak, aby se míra každé části přesně rovnala . Nyní jsou části takové, že míra každé části je přesně . Celkový počet řezů je , což je přesně . $k$ $k=p\cdot q$ $t$ ${\displaystyle p\cdot q\cdot a_{i))$ $(p-1)\cdot t$ $p$ $i$ ${\displaystyle 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$

Další výsledky

O jeden řez méně, než je nutné

V případě dvou zlodějů [tj. k = 2] a t barev by spravedlivý řez vyžadoval maximálně t řezů. Pokud jsou však povoleny pouze škrty, maďarský matematik Gábor Szymonyi [9] ukázal, že dva zloději mohou dosáhnout téměř spravedlivého rozdělení v následujícím smyslu: $t-1$

pokud jsou korálky na náhrdelníku uspořádány tak, že je možný t -řez, pak pro dvě podskupiny D 1 a D 2 sad , z nichž obě nejsou prázdné , takže existuje střih takový, že: $\{1,2,\tečky ,t\}$ $D_{1}\cap D_{2}=\varnothing$ $(t-1)$

Pokud je barva , pak část 1 má více korálků barvy i než část 2; $i\in D_{1}$
Pokud je barva , pak část 2 má více korálků barvy i než část 1; $i\in D_{2}$
Nepatří -li barva i k žádnému dílu a oba díly mají stejný počet korálků barvy i . $D_{1}$ $D_{2}$

To znamená, že pokud mají zloději preference ve formě dvou sad „předvoleb“ D 1 a D 2 , z nichž alespoň jedna je neprázdná, existuje -oddíl, takže zloděj 1 získá více korálků ze své preferenční sady D 1 než zloděj 2 , zloděj 2 získá více korálků ze své preferenční sady D 2 než zloděj 1 a zbytek bude stejný. $(t-1)$

Simony připisuje Gaboru Tardosovi poznámku, že výše uvedený výsledek je přímým zobecněním Alonova původního teorému o náhrdelníku v případě k = 2. Buď má náhrdelník -cut, nebo nemá. V případě, že ano, není co dokazovat. Pokud ne, můžeme k náhrdelníku přidat jeden korálek fiktivní barvy a vytvořit dvě sady, sada D 1 se skládá z této fiktivní barvy a sada D 2 je prázdná. Simonyho výsledek ukazuje, že existuje t -cut se stejným počtem barev každé skutečné barvy. $(t-1)$

Negativní výsledek

Pro všechny existuje měřitelné zbarvení v barvách skutečné čáry, takže žádný interval nelze spravedlivě rozdělit nanejvýš řezy [10] . $k\geqslant 1$ $(k+3)$ $k$

Řezání multidimenzionálního náhrdelníku

Výsledek lze rozšířit na pravděpodobnostní míry n definované na d - rozměrné krychli s libovolnou kombinací nadrovin rovnoběžných se stranami pro k zlodějů [11] . $n(k-1)$

Aproximační algoritmus

Z algoritmu pro konzistentní půlení lze odvodit aproximační algoritmus pro řezání náhrdelníku [12] .

Viz také

Poznámky

↑ Sám, 1987 , str. 247-253.
↑ 1 2 Alon, West, 1986 , str. 623-628.
↑ Sám, 1987 , str. 247–253 Čt 1.1.
↑ Sám, 1987 , str. 247–253 Čt 2.1.
↑ Sám, 1987 , str. 247–253 Čt 1.2.
↑ Sám, 1987 , str. 249.
↑ Sám, 1987 , str. 252-253.
↑ Barany, Shlosman, Szucs, 1981 , str. 158–164.
↑ Simonyi, 2008 .
↑ Sám, 2008 , str. 1593–1599
↑ de Longueville, Živaljević, 2008 , str. 926-939.
↑ Simmons, Su, 2003 , str. 15–25.

Literatura

Noga Alon. Dělící náhrdelníky // Pokroky v matematice. - 1987. - T. 63 , no. 3 . - doi : 10.1016/0001-8708(87)90055-7 .
Noga Alon, West DB Borsuk-Ulamova věta a půlení náhrdelníků // Proceedings of the American Mathematical Society. - 1986. - prosinec ( ročník 98 , číslo 4 ). - doi : 10.1090/s0002-9939-1986-0861764-9 .
I. Barany, S. B. Shlosman, A. Szucs. K topologickému zobecnění Tverbergovy věty // Journal of the London Mathematical Society. - 1981. - Vol. 2 , vydání. 23 . - doi : 10.1112/jlms/s2-23.1.158 .
Gabor Simonyi. Náhrdelník půlení s jedním řezem méně, než je potřeba // Electronic Journal of Combinatorics. - 2008. - T. 15 , no. N16 .
Noga Alon. Štípací náhrdelníky a měřitelné zbarvení skutečné linie // Proceedings of the American Mathematical Society. - 2008. - Listopad ( roč. 137 , číslo 5 ). — ISSN 1088-6826 . - doi : 10.1090/s0002-9939-08-09699-8 . - arXiv : 1412,7996 .
Mark de Longueville, Rade T. Zivaljević. Dělení vícerozměrných náhrdelníků // Pokroky v matematice. - 2008. - T. 218 , č. 3 . - doi : 10.1016/j.aim.2008.02.003 . - arXiv : math/0610800 .
Forest W. Simmons, Francis Edward Su. Rozpůlení konsensu pomocí teorémů Borsuk-Ulama a Tuckera // Matematické sociální vědy. - 2003. - únor ( díl 45 , číslo 1 ). - doi : 10.1016/s0165-4896(02)00087-2 .

Odkazy

"Záludná topologie" na YouTube .