반원 위에 있을 확률, 반구 위에 있을 확률

원 위에 임의로 균일하게 n개의 점을 잡았을 때 그들이 한 반원 위에 있을 확률은?

브레인 티저로도 종종 쓰이는 유명한 문제. Bull이 1948년 Mathematical Gazette에 한 문제를 냈고[1], Rushton이 1949년 동지에 해당 문제를 이 문제로 변형하여 매우 간단한 증명을 내놓았다.[2]

먼저 n개의 점을 P_1,P_2, \ldots,P_n이라 둔다. 원 위에서 P_i에서 시작해 시계방향으로 움직여 P_i의 반대쪽까지 움직이면서 지나게 되는 반원을 생각한다. (단, P_i는 포함하지만 반대쪽 점은 포함하지 않아 한 쪽으론 폐구간, 한 쪽으론 개구간이 되도록 잡는다) 이 반원 위에 모든 n개의 점이 오게 되는 사건을 X_i라 하면, P_i 외의 n-1개의 점들 각각에 대해 그 반원 위에 올 확률은 1/2이므로 \text{Pr}(X_i) = 1/2^{n-1}이 된다.

한 편, n개의 점이 한 반원 위에 오는 사건은 어떤 i가 있어 X_i가 일어나는 것과 동치이며, 서로 다른 i,j에 대해 X_iX_j가 동시에 일어나는 것은 불가능하다. 따라서 구하고자 하는 확률은

\displaystyle \text{Pr}(X_1 \vee X_2 \vee \cdots \vee X_n) = \text{Pr}(X_1) + \text{Pr}(X_2) + \cdots + \text{Pr}(X_n)=\frac{n}{2^{n-1}}

이 된다.

한 편 이런 관점에서 생각해보는 것도 가능하다. 먼저 n개의 지름을 균일하게 선택하고, 각 지름마다 양 끝점 중 하나만을 선택해서 n개의 점을 뽑는 식. (전체 경우의 수는 2^n) 이렇게 하면 지름 양끝점 다 선택하는 경우들을 제외해야 하는데, 그 제외되는 경우에 해당되는 measure가 0이기 때문에 제외하고 생각해도 무방하다. 그러면 원 위에 2n개의 점이 놓여있게 되고, 이들 중 한 반원에 있는 n개의 점을 택해야 한다.

그를 위해서, 먼저 이 지름들 각각과 수직인 지름들을 그려 그 양끝점을 원 위에 표시하면 총 2n개의 점이 나오는데 순서대로 A_1,\ldots,A_{2n}으로 두도록 한다. 이제, 원 위의 한 점 P를 택하고, 원의 중심 O와 연결하고, OP와 수직인 지름 QR을 잡은 후, 반원 QPR 위에 있는 n개의 점을 택하는 것을 생각한다. 모든 “반원 위의 n개의 점”들은 P가 움직이는 과정에서 언젠가 반원 QPR이 그 반원과 일치하는 순간이 존재하므로, 이 과정을 통해 모든 경우의 수를 따질 수 있게 된다.

만약 P가 한 호 A_i A_{i+1} 내부에서 움직인다면 위와 같이 잡는 n개의 점은 변하지 않지만, 다른 호로 움직이게 되면 그 때 변동이 생긴다는 점을 주목한다. 곧 우리가 따져야 할 경우의 수는 곧 선택할 수 있는 원호의 개수와 같아지므로 2n개가 되고, 전체 경우의 수는 앞서 2^n이라 했으므로 확률은 \frac{2n}{2^n}=\frac{n}{2^{n-1}}이 된다.

이 관점은 앞서 본 것보다 조금 설명이 길어지지만, 고차원으로 확장이 가능하다는 점에서 좋다. 즉 예컨대 3차원 구에서 n개의 점을 균일하게 뽑았을 때 그들이 한 반구에 놓일 확률을 구한다면? 전자의 풀이를 그대로 적용하기는 힘들지만, 후자의 풀이는 바로 적용할 수 있다.

이 번에도 구에서 미리 n개의 지름을 균일하게 뽑은 후, 그들의 양끝점들 중 하나씩을 뽑아(총 경우의 수 2^n) 그들이 한 반구 위에 오는 경우의 수를 세도록 한다. 그러면 이번엔 각 지름과 수직인 대원 C_i들을 잡는다. 그러면 구면 위에 n개의 대원들이 있게 되는데, 어떤 세 대원도 한 점에서 만나지 않는 가장 generic한 포지션을 보도록 한다. (제외되는 경우의 measure는 0이라 이번에도 무시해도 무방) 그러면 이 대원들은 구면을 몇 개의 영역으로 나누게 된다.

앞서 본 것처럼, 구면 위의 한 점 P를 잡고 OP와 수직인 대원을 잡은 후 이 대원이 나누는 두 반구 중 P를 포함하는 반구를 잡아 그 위에 있는 n개의 점을 택한다고 할 때, P가 한 영역 내부에 있으면 변하지 않고 영역을 옮길 때마다 변한다는 것을 알 수 있다. 즉 이번에는 영역의 개수를 구하는 문제로 바뀐다. 이는 오일러의 정리를 이용해서 확인할 수 있는데, 교점들을 꼭지점으로, 대원의 원호들을 변으로 갖는 그래프를 생각하도록 한다. 임의의 두 대원은 두 점에서 만나야 하고 이 두 점은 최대 두 대원만이 지날 수 있으므로 모든 교점의 개수는 v=2\binom{n}{2}=n^2-n이 되고, 각각의 대원 위에는 2n-2개의 교점이 있으므로 2n-2개의 원호로 나뉘게 되어 변의 개수는 n(2n-2)=2n^2-2n개가 된다. 따라서 v-e+f=2로부터 f=2-v+e=2-(n^2-n)+(2n^2-2n)=n^2-n+2개가 되고, 구하고자 하는 확률은 \frac{n^2-n+2}{2^n}이 된다.

이 반구 위의 점들을 뽑을 확률에 대한 문제는 n=4인 경우 Putnam competition에 나온 적이 있다. (1992년 A6) 위 풀이는 아래 3Blue1Brown의 영상에서도 소개된 바 있다.

Elegant Math 계정에서 작성한 트윗 타래트윗 타래를 정리. (2017/07/14, 2017/12/09)

References

[1] G. A. Bull, “2016. A Broken Stick” The Mathematical Gazette, Vol. 32, No. 299 (May, 1948), pp. 87-88. DOI: 10.2307/3610712

[2] S. Rushton, “2083. A Broken Stick” The Mathematical Gazette, Vol. 33, No. 306 (Dec., 1949), pp. 286-288. DOI: 10.2307/3611314

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중