이 게시물은 질문에 대한 답변을 제공하고 정답을 입증하기위한 부분적인 진행 상황을 간략하게 설명합니다.

---

들면 N = 1 , 대답은 사소하다 1 . 모든 큰 들어 N , 그것은 (놀랍게도) 항상 2 / 3 .$n=1$$1$$n$$2/3$

먼저 질문에 일반화 될 수 있음을 관찰, 이유를 어떤 연속 분포 F (균일 한 분포의 장소에). 프로세스는 이에 의해 N 개의 간격은 도면에 양 생성되어 2 N IID variates X 1 , X 2 , … , X 2 N 에서 F 및 형성 간격$F$$n$$2n$$X_1, X_2, \ldots, X_{2n}$$F$

[ 최소 ( X 1 , X 2 ) , 최대 ( X 1 , X 2 ) ] , … , [ 최소 ( X 2 n – 1 , X 2 n ) , 최대 ( X 2 n – 1 , X 2 n ) ] .

$$[\min(X_1,X_2), \max(X_1,X_2)], \ldots, [\min(X_{2n-1}, X_{2n}), \max(X_{2n-1}, X_{2n})].$$

X i 의 모든 2 n 은 독립적이기 때문에 서로 교환 가능합니다. 이것은 우리가 무작위로 모든 것을 순열한다면 해결책이 동일하다는 것을 의미합니다. 그러므로 X i 를 정렬하여 얻은 순서 통계를 조건으로하자 :$2n$$X_i$$X_i$

X ( 1 ) < X ( 2 ) < ⋯ < X ( 2 n )

$$X_{(1)} \lt X_{(2)} \lt \cdots \lt X_{(2n)}$$

(여기서 F 는 연속적 이므로 두 개가 같을 가능성은 없습니다.) N 개의 구간은 랜덤 순열을 선택하여 형성된다 σ ∈ S 2 N을 과 쌍들을 연결$F$$n$$\sigma\in\mathfrak{S}_{2n}$

[ 분 ( X σ ( 1 ) , X σ ( 2 ) ) , 최대 ( X σ ( 1 ) , X σ ( 2 ) ) ] , … , [ 분 ( X σ ( 2 N – 1 ) , X σ ( 2 n ) ) , 최대 ( X σ ( 2N – 1 ) , X σ ( 2 N ) )].

$$[\min(X_{\sigma(1)},X_{\sigma(2)}), \max(X_{\sigma(1)},X_{\sigma(2)})], \ldots, [\min(X_{\sigma(2n-1)}, X_{\sigma(2n)}), \max(X_{\sigma(2n-1)}, X_{\sigma(2n)})].$$

이러한 중첩 두인지 여부의 값에 의존하지 않는 X ( I ) ,$X_{(i)}$ 겹쳐진 어떤 의한 단조 변환 보존되기 때문에 F : R → R을 그 송신 같은 변환이있다 X ( I ) 에 난 . 따라서 일반성을 잃지 않으면 서 우리는 X ( i ) = i를 취할 수 있으며 질문은 다음과 같이됩니다.$f:\mathbb{R}\to\mathbb{R}$$X_{(i)}$$i$$X_{(i)}=i$

집합 { 1 , 2 , … , 2 n – 1 , 2 n } 을 n 개의 분리 된 더블 톤 으로 분할합니다 . r 1 > l 2 및 r 2 > l 1 일 때 { l 1 , r 1 } 및 { l 2 , r 2 } ( l i < r i 포함 ) 중 두 개가 겹칩니다.$\{1,2,\ldots, 2n-1, 2n\}$$n$$\{l_1,r_1\}$$\{l_2,r_2\}$$l_i \lt r_i$$r_1 \gt l_2$$r_2 \gt l_1$. 파티션의 요소 중 하나 이상이 다른 모든 요소와 겹칠 때 파티션이 “양호”하다고 가정합니다 (그렇지 않으면 “나쁜”). n 의 함수로서 좋은 파티션의 비율은 얼마입니까?$n$

예를 들어, n = 2 경우를 고려하십시오 . 세 개의 파티션이 있습니다.$n=2$

{ { 1 , 2 } , { 3 , 4 } } , { { 1 , 4 } , { 2 , 3 } } , { { 1 , 3 } , { 2 , 4 } } ,  

$$\color{gray}{\{\{1,2\},\{3,4\}\}},\ \color{red}{\{\{1,4\},\{2,3\}\}},\ \color{red}{\{\{1,3\},\{2,4\}\}},$$

그 중 두 가지 좋은 것 (두 번째와 세 번째)은 빨간색으로 표시됩니다. 따라서 경우에 응답 N = 2 인 2 / 3 .$n=2$$2/3$

이러한 파티션 { { l i , r i } ,숫자 라인에점 { 1 , 2 , … , 2 n } 을플롯하고각 l i 와 r i 사이에 선 세그먼트를 그려서시각적으로 겹치는 부분을 해결하기 위해포인트를약간 상쇄함으로써 i = 1 , 2 , … , n } . 다음은 동일한 색상으로 동일한 순서로 이전 세 파티션의 도표입니다.$\{\{l_i,r_i\},\,i=1,2,\ldots,n\}$$\{1,2,\ldots,2n\}$$l_i$$r_i$

From now on, in order to fit such plots easily in this format, I will turn them sideways. For instance, here are the $15$ partitions for $n=3$, once again with the good ones colored red:

Ten are good, so the answer for $n=3$ is $10/15=2/3$.

첫 번째 흥미로운 상황은 n = 4 일 때 발생합니다 . 이제, 처음으로, 스팬 간격의 조합 가능하다 (1) 을 2 N 다른 교차 그들 중 어느 하나 일없이. 예는 { { 1 , 3 } , { 2 , 5 } , { 4 , 7 } , { 6 , 8 } } 입니다. 선분의 결합은 1 에서 8 까지 끊어지지 않습니다.$n=4$$1$$2n$$\{\{1,3\},\{2,5\},\{4,7\},\{6,8\}\}$$1$$8$ but this is not a good partition. Nevertheless, $70$ of the $105$ partitions are good and the proportion remains $2/3$.

---

The number of partitions increases rapidly with $n$: it equals $1\cdot 3\cdot 5 \cdots \cdot 2n-1 = (2n)!/(2^nn!)$. Exhaustive enumeration of all possibilities through $n=7$ continues to yield $2/3$ as the answer. Monte-Carlo simulations through $n=100$ (using $10000$ iterations in each) show no significant deviations from $2/3$.

I am convinced there is a clever, simple way to demonstrate there is always a $2:1$ ratio of good to bad partitions, but I have not found one. A proof is available through careful integration (using the original uniform distribution of the $X_i$), but it is rather involved and unenlightening.

---

답변