Problem med att klippa halsband

Halsbandsklippningsproblemet är namnet på en serie problem från kombinatorik och måttteori . Problemet formulerades och löstes av matematikerna Noga Alon [1] och Douglas B. West [2] .

Grundläggande villkor definierar ett halsband med pärlor i olika färger. Halsbandet bör delas upp på flera deltagare eller tjuvar (man antar ofta att halsbandet är stulet), så att varje deltagare skulle få ett visst antal pärlor av varje färg. Dessutom bör antalet snitt vara så få som möjligt (för att förlora så lite metall som möjligt i kedjan som förbinder pärlorna).

Variationer

Följande varianter av problemet löstes i den ursprungliga artikeln:

Diskret skärning [3] : Halsbandet har pärlor. Pärlorna är i olika färger. Det finns pärlor av varje färg , där är ett positivt heltal. Du bör skära halsbandet i delar (inte nödvändigtvis kontinuerliga), som var och en har exakt färgpärlor i . Inga fler snitt ska användas. Observera att om pärlorna i varje färg är arrangerade kontinuerligt på halsbandet, så behöver du åtminstone skärningar inuti varje färg, så att värdet blir optimalt. $k\cdot n$ $t$ ${\displaystyle k\cdot a_{i))$ $i$ $a_{i}$ $k$ $a_{i}$ $(k-1)t$ $k-1$ $(k-1)t$
Kontinuerlig skärning [4] : Halsbandet är ett riktigt segment . Varje punkt i segmentet är färgad i en av färgerna. För alla färger är uppsättningen av punkter färgade efter färg Lebesgue-mätbar och har längd , där är ett icke-negativt reellt tal. Du bör dela upp segmentet i delar (inte nödvändigtvis kontinuerliga), så att den totala längden på färgen i varje del är exakt lika med . Använd inga fler snitt. $[0,k\cdot n]$ $t$ $i$ $jag,$ ${\displaystyle k\cdot a_{i))$ $a_{i}$ $k$ $i$ $a_{i}$ $(k-1)t$
Dela efter mått [5] : Halsbandet är ett riktigt segment. Det finns olika mått på ett segment, alla absolut kontinuerliga i längd. Måttet på hela halsbandet i mått är . Segmentet bör delas upp i delar (inte nödvändigtvis kontinuerligt), så att måttet för varje del i mått är exakt lika med . Använd inga fler snitt. Detta är en generalisering av Hobby-Rice-satsen och används för att få en exakt uppdelning av kakan . $t$ $i$ ${\displaystyle k\cdot a_{i))$ $k$ $i$ $a_{i}$ $(k-1)t$

Varje uppgift kan lösas på följande sätt:

Ett diskret snitt kan lösas genom ett kontinuerligt snitt, eftersom ett diskret halsband kan reduceras till en riktig linjefärgning där varje linjesegment av längd 1 färgas av färgen på motsvarande pärla. I fallet när en kontinuerlig skiljevägg försöker skära inuti en pärla, kan snittet flyttas så att snitten endast är mellan pärlorna [6] . $[0,k\cdot n]$
Kontinuerlig skärning kan göras genom att dela upp efter mått, eftersom färgningen av ett segment i färger kan omvandlas till en uppsättning mått, så att måttet återspeglar längden på färgen . Det omvända är också sant - en uppdelning efter mått kan erhållas genom kontinuerlig skärning med hjälp av finare reduktion [7] . $t$ $t$ $i$ $i$

Bevis

Fallet kan bevisas med Borsuk-Ulam-satsen [2] . $k=2$

Om är ett udda primtal , använder beviset en generalisering av Borsuk-Ulam-satsen [8] . $k$

Om är sammansatt kommer beviset att vara enligt följande (vi demonstrerar för alternativet att dela efter mått). Låt oss anta det . Det finns mått, som var och en utvärderar hela halsbandet som . Med hjälp av snitt delar vi upp halsbandet i delar, så att måttet på varje del är exakt lika med . Låt oss skära varje del i delar med hjälp , så att måttet på varje del är exakt lika med . Det finns nu delar så att måttet för varje del är exakt . Det totala antalet nedskärningar är , vilket är exakt . $k$ $k=p\cdot q$ $t$ ${\displaystyle p\cdot q\cdot a_{i))$ $(p-1)\cdot t$ $sid$ $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$

Ytterligare resultat

Ett snitt mindre än nödvändigt

I fallet med två tjuvar [d.v.s. k = 2] och t- färger, skulle ett rättvist snitt kräva högst t snitt. Om dock bara nedskärningar är tillåtna visade den ungerske matematikern Gábor Szymonyi [9] att två tjuvar kan uppnå en nästan rättvis uppdelning i följande mening: $t-1$

om pärlorna på halsbandet är arrangerade på ett sådant sätt att ett t -snitt är möjligt, då för två underuppsättningar D 1 och D 2 av uppsättningarna , som båda inte är tomma så att , det finns ett -snitt så att: $\{1,2,\dots ,t\}$ $D_{1}\cap D_{2}=\varnothing$ $(t-1)$

Om färg är har del 1 fler färgpärlor i än del 2; $i\in D_{1}$
Om färg är har del 2 fler färgpärlor i än del 1; $i\in D_{2}$
Om färg i inte hör till någon av delarna och har båda delarna samma antal färgpärlor i . $D_{1}$ $D_{2}$

Detta betyder att om tjuvar har preferenser i form av två uppsättningar "preferenser" D 1 och D 2 , av vilka minst en är icke-tom, så finns det en -partition så att tjuven 1 får fler pärlor från sin preferensuppsättning D 1 än tjuv 2, tjuv 2 kommer att få fler pärlor från sin preferensuppsättning D 2 än tjuv 1, och resten blir densamma. $(t-1)$

Simony tillskriver Gabor Tardos anmärkningen att ovanstående resultat är en direkt generalisering av Alons ursprungliga halsbandssats i fallet k = 2. Antingen har halsbandet ett -snitt eller så har det inte. Om det är så finns det inget att bevisa. Om inte, kan vi lägga till en fiktiv färgpärla till halsbandet och bilda två set, setet D 1 består av denna fiktiva färg och setet D 2 är tomt. Simonys resultat visar att det finns ett t -snitt med lika många färger av varje riktig färg. $(t-1)$

Negativt resultat

För alla finns det en mätbar färgning i färgerna på den verkliga linjen så att inget intervall kan delas upp rättvist med högst snitt [10] . $k\geqslant 1$ $(k+3)$ $k$

Klippning av det flerdimensionella halsbandet

Resultatet kan utökas till sannolikhetsmått n definierade på en d - dimensionell kub med valfri kombination av hyperplan parallella med sidorna för k tjuvar [11] . $n(k-1)$

Approximationsalgoritm

En approximationsalgoritm för att klippa halsbandet kan härledas från algoritmen för konsekvent halvering [12] .

Se även

Anteckningar

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

Litteratur

Noga Alon. Dela halsband // Framsteg i matematik. - 1987. - T. 63 , nr. 3 . - doi : 10.1016/0001-8708(87)90055-7 .
Noga Alon, West DB Borsuk-Ulams teorem och halvering av halsband // Proceedings of the American Mathematical Society. - 1986. - December ( vol. 98 , nummer 4 ). - doi : 10.1090/s0002-9939-1986-0861764-9 .
I. Barany, S.B. Shlosman, A. Szucs. Om en topologisk generalisering av en teorem från Tverberg // Journal of the London Mathematical Society. - 1981. - Vol. 2 , nummer. 23 . - doi : 10.1112/jlms/s2-23.1.158 .
Gabor Simonyi. Halsbandshalvering med ett snitt mindre än vad som behövs // Electronic Journal of Combinatorics. - 2008. - T. 15 , nr. N16 .
Noga Alon. Delade halsband och mätbara färger av den verkliga linjen // Proceedings of the American Mathematical Society. - 2008. - November ( vol. 137 , nummer 5 ). — ISSN 1088-6826 . - doi : 10.1090/s0002-9939-08-09699-8 . - arXiv : 1412.7996 .
Mark de Longueville, Rade T. Zivaljević. Dela flerdimensionella halsband // Framsteg i matematik. - 2008. - T. 218 , nr. 3 . - doi : 10.1016/j.aim.2008.02.003 . - arXiv : math/0610800 .
Forest W. Simmons, Francis Edward Su. Konsensushalvering via Borsuk-Ulams och Tuckers satser // Mathematical Social Sciences. - 2003. - Februari ( vol. 45 , nummer 1 ). - doi : 10.1016/s0165-4896(02)00087-2 .

Länkar

"Sneaky Topology" på YouTube .