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

원 위에 임의로 균일하게 $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_i$ 와 $X_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}$ 이 된다.