공집합을 빼도 부분집합의 짝수 크기 확률은 1/2일까

U=\{1,2,\ldots,8\},\quad S\subseteq U,\ S\ne\varnothing, \quad P(|S|\text{가 짝수})=?

비어 있지 않은 부분집합 $S$ 255개를 같은 확률로 고른다. 전체 $2^8=256$ 개에서는 원소 1의 포함 여부를 바꿀 때 짝수 크기와 홀수 크기 집합이 짝을 이루므로 각각 128개다.

P(|S|\text{가 짝수})=\frac{128-1}{256-1} =\frac{127}{255}<\frac12.

공집합은 크기가 0인 짝수 집합이다. 이것을 빼면 $\varnothing$ 과 짝이던 $\{1\}$ 은 남고 짝수 127개, 홀수 128개가 된다. $1/2$ 와의 차는 $1/510$ 이다.

“여전히 반씩 남는다”는 답에는 학생이 만든 짝을 그리게 한다. $\{1\}$ 의 짝이 허용된 선택 목록에 있는가? 후속으로 공집합 대신 전원 선택 집합 하나를 제외해 보자. 크기 8도 짝수이므로 답은 다시 $127/255$ 다. 어떤 결과를 균등하게 고르는지 먼저 정해야 한다.

출처·착안: Peter Mattock, 「Multiplicative counting – the different types」. 문항과 예시 답안은 새로 작성했다.