Problemă de tăiere a colierului

Problema tăierii colierului este numele unei serii de probleme din combinatorică și teoria măsurării . Problema a fost formulată și rezolvată de matematicienii Noga Alon [1] și Douglas B. West [2] .

Condițiile de bază definesc un colier cu margele de diferite culori. Colierul trebuie împărțit între mai mulți participanți sau hoți (se presupune adesea că colierul este furat), astfel încât fiecare participant să primească un anumit număr de margele de fiecare culoare. Mai mult decât atât, numărul de tăieturi ar trebui să fie cât mai puțin posibil (pentru a pierde cât mai puțin metal în lanțul care leagă margelele).

Variante

Următoarele variante ale problemei au fost rezolvate în articolul original:

Tăiere discretă [3] : Colierul are margele. Mărgelele sunt de diferite culori. Există margele de fiecare culoare , unde este un număr întreg pozitiv. Ar trebui să tăiați colierul în părți (nu neapărat continue), fiecare având exact margele de culoare i . Nu mai trebuie folosite tăieturi. Rețineți că dacă margelele fiecărei culori sunt aranjate continuu pe colier, atunci aveți nevoie de cel puțin tăieturi în interiorul fiecărei culori, pentru ca valoarea să fie optimă. $k\cdot n$ $t$ $k\cdot a_{i}$ $i$ $a_{i}$ $k$ $a_{i}$ $(k-1)t$ $k-1$ $(k-1)t$
Tăiere continuă [4] : Colierul este un adevărat segment . Fiecare punct al segmentului este colorat într-una dintre culori. Pentru orice culoare, setul de puncte colorate după culoare este măsurabil Lebesgue și are lungimea , unde este un număr real nenegativ. Ar trebui să împărțiți segmentul în părți (nu neapărat continue), astfel încât în fiecare parte lungimea totală a culorii să fie exact egală cu . Nu mai folosiți tăieturi. $[0,k\cdot n]$ $t$ $i$ $eu,$ $k\cdot a_{i}$ $a_{i}$ $k$ $i$ $a_{i}$ $(k-1)t$
Despicare dupa masura [5] : Colierul este un adevarat segment. Sunt diverse masuri pe un segment, toate absolut continue ca lungime. Masura intregului colier in masura este de . Segmentul trebuie împărțit în părți (nu neapărat continue), astfel încât măsura fiecărei părți în măsură să fie exact egală cu . Nu mai folosiți tăieturi. Aceasta este o generalizare a teoremei Hobby-Rice și este folosită pentru a obține o împărțire exactă a prăjiturii . $t$ $i$ $k\cdot a_{i}$ $k$ $i$ $a_{i}$ $(k-1)t$

Fiecare sarcină poate fi rezolvată în felul următor:

O tăietură discretă poate fi rezolvată printr-o tăietură continuă, deoarece un colier discret poate fi redus la o linie de colorare reală în care fiecare segment de linie de lungime 1 este colorat după culoarea mărgelei corespunzătoare. În cazul în care un despărțitor continuu încearcă să taie în interiorul unei margele, tăietura poate fi deplasată astfel încât tăieturile să fie doar între margele [6] . $[0,k\cdot n]$
Tăierea continuă se poate face prin împărțire după măsură, deoarece colorarea unui segment în culori poate fi transformată într-un set de măsuri, astfel încât măsura să reflecte lungimea culorii . Este adevărat și invers - o despărțire pe măsură se poate obține prin tăiere continuă cu ajutorul unei reduceri mai fine [7] . $t$ $t$ $i$ $i$

Dovada

Cazul poate fi demonstrat prin teorema Borsuk-Ulam [2] . $k=2$

Dacă este un prim impar , demonstrația folosește o generalizare a teoremei Borsuk-Ulam [8] . $k$

Dacă este compus , demonstrația va fi următoarea (demonstrăm opțiunea de împărțire după măsură). Să presupunem că . Există măsuri, fiecare dintre ele evaluând întregul colier ca . Folosind tăieturi, împărțim colierul în părți, astfel încât măsura fiecărei părți să fie exact egală cu . Să tăiem fiecare parte în părți cu ajutorul , astfel încât măsura fiecărei părți să fie exact egală cu . Există acum părți astfel încât măsura fiecărei părți este exact . Numărul total de tăieturi este , care este exact . $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$

Rezultate suplimentare

O tăietură mai puțin decât este necesar

În cazul a doi hoți [adică k = 2] și t culori, o tăietură corectă ar necesita cel mult t tăieturi. Dacă, totuși, sunt permise doar tăierile, matematicianul maghiar Gábor Szymonyi [9] a arătat că doi hoți pot realiza o împărțire aproape corectă în următorul sens: $t-1$

dacă margelele de pe colier sunt aranjate în așa fel încât să fie posibilă o tăietură în T , atunci pentru două subseturi D 1 și D 2 din seturi , ambele nu sunt goale astfel încât , există o tăietură astfel încât: $\{1,2,\dots ,t\}$ $D_{1}\cap D_{2}=\varnothing$ $(t-1)$

Dacă culoarea este , atunci partea 1 are mai multe margele de culoare i decât partea 2; $i\in D_{1}$
Dacă culoarea este , atunci partea 2 are mai multe margele de culoare i decât partea 1; $i\in D_{2}$
Dacă culoarea i nu aparține niciunei părți și , ambele părți au același număr de margele de culoare i . $D_{1}$ $D_{2}$

Aceasta înseamnă că, dacă hoții au preferințe sub forma a două seturi de „preferințe” D 1 și D 2 , dintre care cel puțin unul nu este gol, există o partiție astfel încât hoțul 1 primește mai multe margele din setul de preferințe D. 1 decât hoțul 2, hoțul 2 va primi mai multe margele din setul de preferințe D 2 decât hoțul 1, iar restul va fi același. $(t-1)$

Simony îi atribuie lui Gabor Tardos remarca că rezultatul de mai sus este o generalizare directă a teoremei originale a lui Alon a colierului în cazul k = 2. Fie colierul are o tăietură, fie nu. În cazul în care a fost, nu este nimic de demonstrat. Dacă nu, putem adăuga o mărgele de culoare fictivă la colier și putem forma două seturi, setul D 1 este format din această culoare fictivă, iar setul D 2 este gol. Rezultatul lui Simony arată că există o tăietură t cu un număr egal de culori pentru fiecare culoare reală. $(t-1)$

Rezultat negativ

Pentru orice , există o colorare măsurabilă în culorile liniei reale, astfel încât niciun interval nu poate fi subdivizat în mod corect la cel mult tăieturi [10] . $k\geqslant 1$ $(k+3)$ $k$

Tăierea colierului multidimensional

Rezultatul poate fi extins la măsurile de probabilitate n definite pe un cub d - dimensional cu orice combinație de hiperplanuri paralele cu laturile pentru k hoți [11] . $n(k-1)$

Algoritm de aproximare

Un algoritm de aproximare pentru tăierea colierului poate fi derivat din algoritmul de înjumătățire consistentă [12] .

Vezi și

Note

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

Literatură

Noga Alon. Despărțirea colierelor // Progrese în matematică. - 1987. - T. 63 , nr. 3 . - doi : 10.1016/0001-8708(87)90055-7 .
Noga Alon, West DB Teorema Borsuk-Ulam și bisecția colierelor // Proceedings of the American Mathematical Society. - 1986. - Decembrie ( vol. 98 , numărul 4 ). - doi : 10.1090/s0002-9939-1986-0861764-9 .
I. Barany, S. B. Shlosman, A. Szucs. Despre o generalizare topologică a unei teoreme a lui Tverberg // Journal of the London Mathematical Society. - 1981. - Vol. 2 , numărul. 23 . - doi : 10.1112/jlms/s2-23.1.158 .
Gabor Simonyi. Bisecție colier cu o tăietură mai puțin decât este necesar // Electronic Journal of Combinatorics. - 2008. - T. 15 , nr. N16 .
Noga Alon. Despicarea colierelor și colorațiile măsurabile ale liniei reale // Proceedings of the American Mathematical Society. - 2008. - noiembrie ( vol. 137 , numărul 5 ). — ISSN 1088-6826 . - doi : 10.1090/s0002-9939-08-09699-8 . - arXiv : 1412,7996 .
Mark de Longueville, Rade T. Zivaljević. Împărțirea colierelor multidimensionale // Progrese în matematică. - 2008. - T. 218 , nr. 3 . - doi : 10.1016/j.aim.2008.02.003 . - arXiv : math/0610800 .
Forest W. Simmons, Francis Edward Su. Înjumătățirea consensului prin teoremele lui Borsuk-Ulam și Tucker // Științe sociale matematice. - 2003. - Februarie ( vol. 45 , numărul 1 ). - doi : 10.1016/s0165-4896(02)00087-2 .

Link -uri

„Sneaky Topology” pe YouTube .