목걸이 쪼개기 문제

a stylized picture of a necklace, with 8 red and 6 green pearls. The pearls are threaded on to an incomplete elliptical black curve that represents the string. The gap in the curve represents the clasp (open in the diagram) which may be closed when the necklace is placed around the neck. There are two short heavy lines marking breaks in the necklace string. Starting from the left, the necklace is: RRRGRBRRGRRGGBGG, where "R" means "red pearl", "G" means "green pearl", and "B" means "break". The breaks correspond to those in the text

k = 2(즉, 파트너 두 개) 및 t = 2(즉, 구슬 두 종류, 여기에 빨간색 8개와 녹색 6개)로 분할된 목걸이 예.한 파트너는 가장 큰 구간을 받고, 다른 파트너는 나머지 두 구간을 받는 2-분할이 표시된다.

목걸이 갈라짐은 결합 이론과 측량 이론에서 몇 가지 관련된 문제들에 붙여진 그림 같은 이름이다.이것의 이름과 해결책은 수학자 노가 알론과^[1] 더글러스 B 때문이다. 서쪽.^[2]

기본 세팅은 다양한 색깔의 구슬이 달린 목걸이를 포함한다.목걸이는 여러 파트너(예: 도둑)로 나누어 각 파트너가 모든 색상의 동일한 양을 받도록 해야 한다.더욱이 절단 횟수는 ( 구슬 사이의 연결에서 금속을 가능한 한 적게 낭비하기 위해) 가능한 한 적어야 한다.

변형

이 문제의 변형들은 원문에서 다음과 같이 해결되었다.

이산형 분할:^[1]^{: Th 1.1}그 목걸이는 $k\cdot n$ $[\displaystyle k\cdotn]$ 구슬이 $k\cdot n$ 달려 있다. $구슬$ 은 $t$ 색깔로 나온다 $.$ $k\cdot a_{i}$ 색상 $i$ ${\$ $displaystyle k\cdot a_{i$ $}$ 의 k $k\cdot a_{i}$ a {\ $displaystyle a_$ {i} 비드가 $k\cdot a_{i}$ 있으며 $i$ $a_{i}$ 서 $a_{i}$ ${\$ 는 양의 정수다 $a_{i}$ .목걸이를 $k$ $k$ 부분 $k$ (연속할 필요는 없음)으로 분할하십시오. 각 부분에는 정확히 i ${\$ 개의 비드가 $a_{i}$ 있다.최대 $(k-1)t$ - $(k-1)t$ ) $(k-1)t$ ${\displaystyle(k-1)t}$ 컷을 $(k-1)t$ 사용하십시오.각 색상의 구슬이 목걸이에 연속되어 있는 경우, 적어도 $k-1$ - 1 $k-1$ 을 $k-1$ (를) 각 색상에서 잘라내야 하므로 ( $(k-1)t$ - $(k-1)t$ ) $(k-1)t$ $(k-1)t$ 이(가) 최적이다 $(k-1)t$ .
연속 분할:^[1]^{: Th 2.1}목걸이는 실제 간격 $[0,k\cdot n]$ [ $[0,k\cdot n]$ $[0,k\cdot n]$ $[0,k\cdot n]$ n $[0,k\cdot n]$ ${\displaystyle [0,k\cdot n$ 간격의 각 점은 $t$ $t$ 개의 $t$ 다른 색 중 하나로 채색된다. $모든$ 색상 $i$ $i$ 에 대해 $i$ i $i$ 에 의해 색칠된 점 집합은 Lebesgue 측정 가능하고 $i$ $k\cdot a_{i}$ k $k\cdot a_{i}$ $k\cdot a_{i}$ ${\$ 를 가지며 $a_{i}$ 서 $k\cdot a_{i}$ i ${\$ 는 음이 $a_{i}$ 아닌 실제 수입니다. $k$ 을 k ${\displaystyle$ k $} 부분$ (연속할 필요는 없음)으로 $k$ 분할하십시오. 각 부분에서 $색상$ i ${\$ $displaystyle i}$ 의 총 길이가 $a_{i}$ $a_{i}$ {\ $displaystyle a_{i}$ 인 $i$ $a_{i}$ 경우 $(k-1)t$ 최대 ( $(k-1)t$ - $(k-1)t$ ) $(k-1)t$ t {\ $displaystyle(k-1)t}$ 컷으로 $(k-1)t$ 사용하십시오.
분할 측정:^[1]^{: Th 1.2}목걸이가 진짜 간격이네.간격마다 다른 $t$ $측정치$ {\ $displaystyle t}$ 이(가 $)$ 있으며, 모두 길이에 대해 절대적으로 연속적이다.전체 목걸이의 측정값은 $측정값$ i {\ $displaystyle$ i $}$ 에 따라 $k\cdot a_{i}$ $k\cdot a_{i}$ a ${\$ 이다 $k\cdot a_{i}$ 측정값 $i$ ${\displaysty i}$ 에 따라 $각$ 부분의 측정값이 정확하게 $a_{i}$ ${\$ $k}$ 부분(필수적으로 연속되지 않음 $i$ 으로 $k$ 분할한다. $스타일 a_{i$ $(k-1)t$ - $(k-1)t$ ) t ${\displaystyle(k-1)t$ }컷을 $(k-1)t$ 사용하십시오 $.$ 이것은 Hobby-Rice 정리를 일반화한 것으로, 케이크를 정확히 나누기 위해 사용된다.

각 문제는 다음 문제로 해결할 수 있다.

이산형 분할은 이산형 목걸이가 길이 1의 각 구간이 해당 비드의 색상으로 채색되는 $실제$ 간격 $0, k$ n $]$ 의 색상으로 변환될 수 있기 때문에 연속 분할로 해결할 수 있다.연속적인 갈라짐이 구슬 안쪽을 자르려 할 경우, 베인 상처는 구슬 사이에서만 만들어지도록 서서히 미끄러질 수 있다.^[1]^{: 249}
$t$ ${\displaystyle$ $t$ $}$ 색상의 $t$ 간격 색상은 t ${\displaystyle i$ $}$ 색상의 총 $i$ 를 측정하는 $i$ 것과 같이 설정된 $t$ ${\displaystyle$ $t}$ 측정으로 $t$ 변환될 수 있으므로 연속 분할은 측정 분할로 해결할 수 있다 $i$ 측정값 분할은 보다 정교한 감소를 사용하여 연속적인 분할을 통해 해결할 수 있다.^[1]^{: 252–253}

증명

사례 $k=2$ = $k=2$ $k=2$ 는 보르수크-울람 정리로 증명할 $k=2$ 수 있다.^[2]

$k$ $k$ 이 $k$ (가) 홀수 소수일 때, 그 증명에는 보르수크-울람 정리의 일반화가 포함된다.^[3]

$k$ $k$ 이 $k$ (가) 복합 번호일 경우, 그 증거는 다음과 같다(측정 분할 변형에 대해 입증).Suppose $k=p\cdot q$ . There are $t$ measures, each of which values the entire necklace as $p\cdot q\cdot a_{i}$ . Using $(p-1)\cdot t$ cuts, divide the necklace to $p$ parts such that measure $i$ $i$ of each part is exactly $q\cdot a_{i}$ . Using $(q-1)\cdot t$ cuts, divide each part to $q$ parts such that measure $i$ of each part is exactly $a_{i}$ . All in all, there are $i$ $p$ $q$ $i$ 을(를) 측정하는 p q ${\displaystyle$ $a_{i}$ 가 $p q$ $a_{i}$ i ${\$ a_{i}이다 $a_{i}$ 총 절단 횟수는 $(p-1)\cdot t$ ( $(pq-1)\cdot t$ $(p-1)\cdot t$ - 1 $(p-1)\cdot t$ ) $(p-1)\cdot t$ $(p-1)\cdot t$ ${\displaystyle (p-1)\$ $p(q-1)\cdot t$ t $}$ + p $(p-1)\cdot t$ $p(q-1)\cdot t$ ( $p(q-1)\cdot t$ - 1 $p(q-1)\cdot t$ ) $p(q-1)\cdot t$ $p(q-1)\cdot t$ ${\displaystyp(q-1)\cdot$ t $}$ 이며, 정확히 $p(q-1)\cdot t$ $(pq-1)\cdot t$ p Q $(pq-1)\cdot t$ - $(pq-1)\cdot t$ ) ${$ $(pq-1)\cdot t$ {\ $displaystystyle$ ( $pq-1)\cdot$ t $}$ 이다 $(pq-1)\cdot t$

추가 결과

무작위 목걸이 쪼개기

경우에 따라 무작위 목걸이는 더 적은 컷을 사용하여 균등하게 쪼개질 수 있다.수학자 노가 알론, 도르 엘보임, 가보르 타도스, 야노스 파흐는 두 도둑 사이에 무작위 목걸이를 나누는 데 필요한 전형적인 절단 횟수를 연구했다.^[4]그들이 고려한 모델에서 목걸이는 각 색상의 t 컬러와 m 구슬이 있는 목걸이 세트에서 무작위로 균일하게 선택된다.m이 무한대로 되는 경향이 있기 때문에, $+(t+$ 1)/ $2⌋$ 커트 이하로 목걸이를 분할할 수 있는 확률은 0이 되는 경향이 있는 반면, $⌊(t+1)/2⌋+1$ 컷으로 분할할 수 있는 확률은 0에서 경계한다.더 정확히 말하자면, X=X(t,m)를 목걸이를 분할하는 데 필요한 최소한의 절단 횟수가 되도록 하는 것이다.다음은 m이 무한대로 유지되는 경향이 있다. $s<(t+1)/2$ 의 $s<(t+1)/2$ < $s<(t+1)/2$ ( $s<(t+1)/2$ + 1 $s<(t+1)/2$ ) $s<(t+1)/2$ / $s<(t+1)/2$ $s<(t+1)/2$ 에 대해

\mathb {P}(X=s)=\세타 {\big (}m^{s-(t+1)/2}{\big )}.

$(t+1)/2<s\leq t$ 의 $(t+1)/2<s\leq t$ ( t $(t+1)/2<s\leq t$ + $(t+1)/2<s\leq t$ ) $(t+1)/2<s\leq t$ / $(t+1)/2<s\leq t$ < $(t+1)/2<s\leq t$ $(t+1)/2<s\leq t$ $(t+1)/2<s\leq t$ ${\displaystyle (t+1)/2<s\leq$ t $}$ 에 대해

\mathb {P}(X=s)=\세타(1)

마지막으로 $t$ $t$ 이 $t$ ( $s=(t+1)/2$ ) $s=(t+1)/2$ 이고 s $s=(t+1)/2$ = $s=(t+1)/2$ ( t $s=(t+1)/2$ + $s=(t+1)/2$ ) $s=(t+1)/2$ / $s=(t+1)/2$ $s=(t+1)/2$ 인 경우

\mathb {P}(X=s)=\Theta {\big (}(\log m)^{-1}{\big )}.

색의 수가 무한대로 되는 경우도 생각해 볼 수 있다.m=1과 t가 무한대 경향이 있을 때, 필요한 절단 횟수는 최대 0.4t, 확률 높은 0.22t이다.분포에서 X(t,1)/t가 c로 수렴하는 것과 같은 0.22(<0.4)가 존재한다고 추측된다.

필요량보다 적은 한 컷

도둑 두 명[즉, k = 2]과 t 색상의 경우, 공정한 분할은 최대 t 컷을 필요로 할 것이다.그러나 t - 1컷만 가능하다면 헝가리 수학자 가보르 시모니는^[5] 두 도둑이 다음의 의미에서 거의 공정한 분열을 이룰 수 있다는 것을 보여준다.

목걸이가 t-분할이 불가능하도록 배열된 경우, {1, 2, ..., t}의 두 하위 집합 D와₁ D에₂ 대해 모두 비어 있지 않은 경우, $D_{1}\cap D_{2}=\varnothing$ $D_{1}\cap D_{2}=\varnothing$ $D_{1}\cap D_{2}=\varnothing$ D $D_{1}\cap D_{2}=\varnothing$ = $D_{1}\cap D_{2}=\varnothing$ ${\displaystyle D_{1}\cap D_{2}=\varnothing$ $D_{1}\cap D_{2}=\varnothing$ a (t - 1)-1)-분할 수 있는 경우:

색상 $i\in D_{1}$ $i\in D_{1}$ D $i\in D_{1}$ ${\$ 파티션 1은 파티션 2보다 색상 i의 비드가 더 많다.
색상 $i\in D_{2}$ $i\in D_{2}$ $i\in D_{2}$ $i\in D_{2}$ ${\$ }}인 경우 $i\in D_{2}$ 파티션 2는 파티션 1보다 색상 i의 비드가 더 많다;
만약 컬러 i가 어느 칸막이에도 없다면, 두 칸막이 모두 동일하게 많은 컬러 i 구슬을 가지고 있다.

즉, 도둑이 둘 다 비어 있지 않고 D와₁ D의₂ 형태로 선호되는 경우, (t - 1)-분할이 존재하여, 도둑 1은 도둑 2보다 선호도 집합 D에서₁ 더 많은 구슬을 얻고, 도둑 2는 도둑 1보다 선호도₂ 집합 D에서 더 많은 구슬을 얻으며, 나머지는 같음을 의미한다.

시모니는 위의 결과가 케이스 k = 2에서 알론의 원래 목걸이 정리를 직접 일반화한 것임을 알아차리고 가보 타도스에게 크레딧을 부여한다. 목걸이에 (t - 1)-스플릿이 있거나 그렇지 않거나 둘 중 하나이다.만약 그렇다면, 증명할 것이 아무것도 없다.만약 그렇지 않다면, 우리는 목걸이에 가공의 색의 구슬을 추가하고, D를₁ 가공의 색과 D로₂ 구성하도록 할 수 있다.그리고 시모니의 결과는 각각의 실제 색상의 동일한 숫자의 t-분할이 있다는 것을 보여준다.

부정적인 결과

모든 $k\geq 1$ $k\geq 1$ $k\geq 1$ ${\displaystyle k\geq$ 1 $}$ 에 대해 측정 가능한 $(k+3)$ + 3 $(k+3)$ ) ${\displaystyle(k+3)$ - $k$ 의 k ${\displaysty k}$ 컷을 $k$ 사용하여 간격이 공정하게 분할되지 않도록 실제 라인의 색상이 $(k+3)$ 지정된다 $k\geq 1$ .^[6]

다차원 목걸이 쪼개기

결과는 k 도둑의 측면에 평행한 n(k - 1) 하이퍼플레인의 조합으로 d차원 큐브에 정의된 확률 측도로 일반화할 수 있다.^[7]

근사 알고리즘

목걸이를 분할하기 위한 근사 알고리즘은 합의 반감 알고리즘에서 도출할 수 있다.^[8]

참고 항목

참조

^ ^a ^b ^c ^d ^e ^f Alon, Noga (1987). "Splitting Necklaces". Advances in Mathematics. 63 (3): 247–253. doi:10.1016/0001-8708(87)90055-7.
^ ^a ^b Alon, Noga; West, Douglas B. (December 1986). "The Borsuk-Ulam theorem and bisection of necklaces". Proceedings of the American Mathematical Society. 98 (4): 623–628. doi:10.1090/s0002-9939-1986-0861764-9.
^ I.Barany and S.B.Shlosman and A.Szucs (1981). "On a topological generalization of a theorem of Tverberg". Journal of the London Mathematical Society. 2 (23): 158–164. CiteSeerX 10.1.1.640.1540. doi:10.1112/jlms/s2-23.1.158.
^ Alon, Noga; Elboim, Dor; Tardos, Gábor; Pach, János (2021). "Random Necklaces require fewer cuts". arXiv:2112.14488 [math.CO].
^ Simonyi, Gábor (2008). "Necklace bisection with one cut less than needed". Electronic Journal of Combinatorics. 15 (N16). doi:10.37236/891.
^ Alon, Noga (November 25, 2008). "Splitting necklaces and measurable colorings of the real line". Proceedings of the American Mathematical Society. 137 (5): 1593–1599. arXiv:1412.7996. doi:10.1090/s0002-9939-08-09699-8. ISSN 1088-6826.
^ de Longueville, Mark; Rade T. Živaljević (2008). "Splitting multidimensional necklaces". Advances in Mathematics. 218 (3): 926–939. arXiv:math/0610800. doi:10.1016/j.aim.2008.02.003.
^ Simmons, Forest W.; Su, Francis Edward (February 2003). "Consensus-halving via theorems of Borsuk-Ulam and Tucker". Mathematical Social Sciences. 45 (1): 15–25. CiteSeerX 10.1.1.203.1189. doi:10.1016/s0165-4896(02)00087-2.

외부 링크

유튜브의 "Sneeky Topology"는 위상학적 해결책의 문제점을 보여주는 소개 동영상이다.

[Alon_1987-1] ^ ^a ^b ^c ^d ^e ^f Alon, Noga (1987). "Splitting Necklaces". Advances in Mathematics. 63 (3): 247–253. doi:10.1016/0001-8708(87)90055-7.

[Alon_1986-2] Alon, Noga; West, Douglas B. (December 1986). "The Borsuk-Ulam theorem and bisection of necklaces". Proceedings of the American Mathematical Society. 98 (4): 623–628. doi:10.1090/s0002-9939-1986-0861764-9.

[BSS-3] I.Barany and S.B.Shlosman and A.Szucs (1981). "On a topological generalization of a theorem of Tverberg". Journal of the London Mathematical Society. 2 (23): 158–164. CiteSeerX 10.1.1.640.1540. doi:10.1112/jlms/s2-23.1.158.

[4] Alon, Noga; Elboim, Dor; Tardos, Gábor; Pach, János (2021). "Random Necklaces require fewer cuts". arXiv:2112.14488 [math.CO].

[Simonyi_2008-5] Simonyi, Gábor (2008). "Necklace bisection with one cut less than needed". Electronic Journal of Combinatorics. 15 (N16). doi:10.37236/891.

[6] Alon, Noga (November 25, 2008). "Splitting necklaces and measurable colorings of the real line". Proceedings of the American Mathematical Society. 137 (5): 1593–1599. arXiv:1412.7996. doi:10.1090/s0002-9939-08-09699-8. ISSN 1088-6826.

[7] Longueville, Mark; Rade T. Živaljević (2008). "Splitting multidimensional necklaces". Advances in Mathematics. 218 (3): 926–939. arXiv:math/0610800. doi:10.1016/j.aim.2008.02.003.

[8] Simmons, Forest W.; Su, Francis Edward (February 2003). "Consensus-halving via theorems of Borsuk-Ulam and Tucker". Mathematical Social Sciences. 45 (1): 15–25. CiteSeerX 10.1.1.203.1189. doi:10.1016/s0165-4896(02)00087-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search