부분집합 원소의 개수_난이도 중상 (2018년 7월 교육청 나형 29번)

전체집합 $U=\{2, \; 2^2, \; 2^3, \; 2^4, \; 2^5, \; 2^6\}$ 의 서로 다른 부분집합을 $A_i$ $(i=1, \; 2, \; 3, \; \cdots, \; 64)$ 라 하자. $n(A_i) \ge 3$ 을 만족시키는 모든 집합 $A_i$ 에 대하여 각 집합의 가장 작은 원소를 모두 더한 값을 구하시오. (단, $n(A)$ 는 집합 $A$ 의 원소의 개수이다.)

정답 $144$

이 문제는 최소인 원소가 $2$, $2^2$, $2^3$, $2^4$ 일 때로 나누어 풀면 됩니다.

1. 최소인 원소가 $2$ 인 경우

   원소의 개수가 $3$ 개인 부분집합의 개수는 $2$ 보다 큰 원소 $5$ 개 중 $2$ 개만 선택하면 되므로 ${}_5{\rm C}_2$ 

   원소의 개수가 $4$ 개인 부분집합의 개수는 2보다 큰 원소 $5$ 개 중 $3$ 개만 선택하면 되므로 $_5{\rm C}_3$

   원소의 개수가 $5$ 개인 경우는 $_5{\rm C}_4$

   원소의 개수가 $6$ 개인 경우는 $_5{\rm C}+5$

   따라서 최소인 원소가 $2$ 이면서 원소의 개수가 $3$ 개 이상인 부분집합의 개수는 $_5{\rm C}_2+ {}_5{\rm C}_3+{}_5{\rm C}_4+{}_5{\rm C}_5=26$ 

   결국 $2$ 는 $26$ 번 더해져서 $52$

2. 최소인 원소가 $2^2$ 인 경우

   위와 같이 하면 구하는 부분집합의 개수는 ${}_4{\rm C}_2 +{}_4{\rm C}_3+{}_4{\rm C}_4 = 11$

   결국 $2^2$ 은 $11$ 번 더해져서 $44$

3. 최소인 원소가 $2^3$ 인 경우

   위와 같이 하면 구하는 부분집합의 개수는 ${}_3{\rm C}_2 + {}_3{\rm C}_3 = 4$

   결국 $2^3$ 은 $4$ 번 더해져서 $32$

4. 최소인 원소가 $2^4$ 인 경우

   위와 같이 하면 구하는 부분집합의 개수는 ${}_2{\rm C}_2=1$

   결국 $2^4$ 은 $1$ 번 더해져서 $16$

최소인 원소가 $2^5$ 이나 $2^6$ 이면서 원소의 개수가 $3$ 개인 부분집합은 존재하지 않는다.

따라서 1, 2, 3, 4 의 결과를 모두 더하면 $52+44+32+16=144$