의예과 1번

[문제 1-1] (답) $\displaystyle c_{2}=2$ <표 2>

(풀이) (ⅰ) $\displaystyle a_{2}=12$이 성립함을 보이자.$\displaystyle a_{2}$는 $\displaystyle U_{3}=\{1,2,3\}$의 두 부분집합 $\displaystyle A$와 $\displaystyle B$에 대해서 두 조건 $\displaystyle A\cup B=U_{3}$과 $\displaystyle n(A)=2$을 만족시키는 $\displaystyle (A,B)$의 개수이다. $\displaystyle A$의 원소가 2개이므로, $\displaystyle U_{3}$의 부분집합 중에서 원소가 2개인 부분집합의 개수는 $\displaystyle {}_{3}\mathrm{C}_{2}=3$이다. 즉, $\displaystyle \{1,2\},\{1,3\},\{2,3\}$. 각 집합에 대해서 조건 $\displaystyle A\cup B=U_{3}$를 만족시키는 $\displaystyle B$를 구하자. 먼저 $\displaystyle A^{c}$의 모든 원소는 반드시 $\displaystyle B$에 속해야 한다.

① $\displaystyle A=\{1,2\}$이면 3은 반드시 $\displaystyle B$에 속해야 하고 $\displaystyle A$의 두 원소 1과 2는 각각 $\displaystyle B$에 속할 수도 있고 속하지 않을 수도 있다. 이때 $\displaystyle A=\{1,2\}$의 부분집합의 개수는 $\displaystyle 2\times2=2^{2}$이고 $\displaystyle A$의 부분집합은 $\displaystyle \emptyset,\{1\},\{2\},\{1,2\}$이다. 각각의 부분집합에 3이 속해야 하기 때문에 $\displaystyle B$는 $\displaystyle \{3\},\{1,3\},\{2,3\},\{1,2,3\}$이 된다.

비슷한 방법으로 ② $\displaystyle A$가 $\displaystyle \{1,3\}$, ③ $\displaystyle A$가 $\displaystyle \{2,3\}$인 경우에 $\displaystyle B$를 찾으면 $\displaystyle a_{2}=3\times2^{2}=12$이다.

(ⅱ) $\displaystyle b_{3}=32$이 성립함을 보이고 $\displaystyle b_{3}$을 구하는 데 사용된 $\displaystyle <A,B>$를 모두 찾는다.$\displaystyle b_{3}$는 $\displaystyle U_{3}=\{1,2,3,4\}$의 두 부분집합 $\displaystyle A$와 $\displaystyle B$에 대해서 두 조건 $\displaystyle A\cup B=U_{4}$과 $\displaystyle n(A)=3$을 만족시키는 $\displaystyle <A,B>$의 개수이다. $\displaystyle A$의 원소가 3개이므로, $\displaystyle U_{4}$의 부분집합 중에서 원소가 3개인 부분집합의 개수는 $\displaystyle {}_{4}\mathrm{C}_{3}=4$이고 그 부분집합은 $\displaystyle \{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}$이다. 각각의 부분집합에 대해서 조건 $\displaystyle A\cup B=U_{4}$를 만족시키는 $\displaystyle B$를 구하면 <표 2>와 같이 나타낼 수 있다. 예를 들어 $\displaystyle A$가 $\displaystyle \{1,2,3\}$이면 4는 반드시 $\displaystyle B$에 속해야 하고 $\displaystyle A$의 세 원소는 각각 $\displaystyle B$에 속할 수도 있고 속하지 않을 수도 있다. $\displaystyle A$의 부분집합의 개수는 $\displaystyle 2\times2\times2=2^{3}$이고 $\displaystyle A$의 부분집합은 $\displaystyle \emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$이다. 각각의 부분집합에 4가 속해야 하기 때문에 집합 $\displaystyle B$는 $\displaystyle \{4\},\{1,4\},\{2,4\},\{3,4\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\{1,2,3,4\}$이 된다. 따라서Correction. $\displaystyle U_3=\{1,2,3,4\}$에서 $\displaystyle U_3$는 $\displaystyle U_4$의 오기다. 그러나 원칙에 따라 원문 표기를 그대로 실었다.$\displaystyle b_{3}=4\times2^{3}=32$이다.

(ⅲ) 등식 $\displaystyle b_{2}=2a_{1}$이 성립함을 보이자.

㉠ $\displaystyle a_{1}$는 $\displaystyle U_{2}=\{1,2\}$의 두 부분집합 $\displaystyle A$와 $\displaystyle B$에 대해서 두 조건 $\displaystyle A\cup B=U_{2}$와 $\displaystyle n(A)=2$를 만족시키는 $\displaystyle (A,B)$의 개수이다. 이때 $\displaystyle n(A)=2$를 만족시키는 $\displaystyle A$는 전체집합 $\displaystyle U_{2}=\{1,2\}$로 1가지이고 이 경우에 대하여 $\displaystyle B$는 $\displaystyle A$의 모든 부분집합이 가능하다. 따라서 $\displaystyle a_{1}=2^{2}$이다.

㉡ $\displaystyle b_{2}$는 $\displaystyle U_{3}=\{1,2,3\}$의 두 부분집합 $\displaystyle A$와 $\displaystyle B$에 대해서 두 조건 $\displaystyle A\cup B=U_{3}$와 $\displaystyle n(A)=3$을 만족시키는 $\displaystyle <A,B>$의 개수이다. 이때 $\displaystyle n(A)=3$를 만족시키는 $\displaystyle A$는 전체집합 $\displaystyle U_{3}=\{1,2,3\}$로 1가지이고 이 경우에 대하여 $\displaystyle B$는 $\displaystyle A$의 모든 부분집합이 가능하다. 따라서 $\displaystyle b_{2}=2^{3}$이다.

㉠과 ㉡에 의해 $\displaystyle b_{2}=2^{3}=2a_{1}$이고 $\displaystyle c_{1}=2$이다.그러므로 (ⅰ)과 (ⅱ)와 (ⅲ)에 의해 $\displaystyle b_{3}=2a_{1}+2a_{2}$이므로 $\displaystyle c_{2}=2$ 이다.

<표 2> $\displaystyle b_{3}$을 구하는 데 사용한 $\displaystyle <A,B>$

[문제 1-2] (답) $\displaystyle c_{1}c_{2}\cdots c_{k}=2^{k}$

(풀이) (ⅰ) $\displaystyle a_{k}$를 구하자.$\displaystyle a_{k}$는 $\displaystyle U_{k+1}=\{1,2,\ldots,k+1\}$의 두 부분집합 $\displaystyle A$와 $\displaystyle B$에 대해서 두 조건 $\displaystyle A\cup B=U_{k+1}$과 $\displaystyle n(A)=2$를 만족시키는 $\displaystyle (A,B)$의 개수이다. 전체집합 $\displaystyle U_{k+1}$의 원소 중에서 2개를 택하는 경우의 수는 $\displaystyle {}_{k+1}\mathrm{C}_{2}$이다. 그리고 $\displaystyle A\cup B=U_{k+1}$를 만족시키는 집합 $\displaystyle B$의 개수는 4이다. 여기에 곱의 법칙을 사용하면 다음 식을 얻는다.$\displaystyle a_{k}={}_{k+1}\mathrm{C}_{2}\times4=2k(k+1),\ k=1,2,\ldots$비슷한 방법으로 $\displaystyle b_{k}$를 구하면 다음 식을 얻는다.$\displaystyle b_{k}={}_{k+1}\mathrm{C}_{3}\times8=\frac{4}{3}(k-1)k(k+1),\ k=1,2,\ldots$

(ⅱ) $\displaystyle \begin{aligned} \sum_{i=1}^{k}a_{i} &= \sum_{i=1}^{k}2i(i+1)=2\sum_{i=1}^{k}\left(i^{2}+i\right)=2\left\{\frac{k(k+1)(2k+1)}{6}+\frac{k(k+1)}{2}\right\} \\ &= \frac{2}{3}k(k+1)(k+2)=\frac{1}{2}b_{k+1} \end{aligned}$이므로 $\displaystyle b_{k+1}=2\sum_{i=1}^{k}a_{i}\ (k=1,2,3,\ldots)$.

(ⅰ)과 (ⅱ)에 의해 $\displaystyle c_{1}c_{2}\cdots c_{k}=2^{k}$.