자연계열 3번

■ 3-1㉡에 있는 주머니5, 주머니6, 주머니9가 가짜 동전들이 들어 있는 주머니이고 나머지 주머니에는 진짜 동전들이 들어 있다면, 각각의 주머니 $\displaystyle k$에서 $\displaystyle 2^{k-1}$개의 동전을 꺼내, 그 꺼낸 동전들의 무게를 쟀을 때, 그 무게의 합이 꺼낸 동전 모두가 진짜일 때의 합보다$\displaystyle 2^4+2^5+2^8$그램이 작다. 한편, 집합 $\displaystyle \{1,2,2^2,2^3,\cdots,2^9\}$의 부분집합 $\displaystyle \{2^4,2^5,2^8\}$의 원소들의 합이 $\displaystyle 2^4+2^5+2^8$이고, 집합 $\displaystyle \{1,2,2^2,2^3,\cdots,2^9\}$의 공집합이 아닌 각각의 부분집합의 원소의 합은 서로 다르므로, 원소들의 합이 $\displaystyle 2^4+2^5+2^8$인 부분집합은$\displaystyle \{2^4,2^5,2^8\}$이 유일하다. 따라서, 가짜 동전들이 들어 있는 가능한 주머니들의 경우는주머니5, 주머니6, 주머니9가 유일하다.

집합 $\displaystyle \{1,2,2^2,2^3,\cdots,2^9\}$의 원소의 합은 $\displaystyle 1+2+2^2+2^3+\cdots+2^9=2^{10}-1$이고 이 합은 부등식 (1)의 우변과 같다. 집합 $\displaystyle \{1,2,2^2,2^3,\cdots,2^9\}$의 공집합을 제외한 모든 부분집합은 원소의 합이 다르므로, 부등식 (1)에서 등호가 성립할 때의 가능한 집합 $\displaystyle A_{10}$은 집합 $\displaystyle \{1,2,2^2,2^3,\cdots,2^9\}$이 있다.

■ 3-2$\displaystyle 1\le k\le N$인 자연수 $\displaystyle k$에 대하여, $\displaystyle S(C_k)$를 집합 $\displaystyle C_k$의 모든 원소들의 합이라 하고, 집합$\displaystyle C=\{S(C_1),S(C_2),\cdots,S(C_N)\}$을 생각하자. 집합 $\displaystyle A_{10}$의 공집합이 아닌 서로 다른 모든 부분집합의 원소의 합은 서로 다르므로 각각의 $\displaystyle S(C_k)$의 값은 모두 다르다. 따라서 집합 $\displaystyle C$의 원소의 개수는 “집합 $\displaystyle A_{10}$의 공집합이 아닌 서로 다른 모든 부분집합 $\displaystyle C_1,C_2,\cdots,C_N$의 개수”와 같으므로 $\displaystyle N=2^{10}-1$이다.

한편, 집합 $\displaystyle C$의 원소 중에서 가장 큰 원소는 $\displaystyle a_1+a_2+\cdots+a_{10}$이므로, ㉢에 의해 집합 $\displaystyle C$의 원소의 개수 $\displaystyle 2^{10}-1$은 집합 $\displaystyle C$의 원소 중 가장 큰 자연수 $\displaystyle a_1+a_2+\cdots+a_{10}$보다 작거나 같다. 즉,$\displaystyle a_1+a_2+\cdots+a_{10}\ge2^{10}-1$이다.제시문에 의하면 집합 $\displaystyle A_{10}$의 원소 중 가장 큰 자연수 $\displaystyle x$는 $\displaystyle 107$보다 크거나 같다. 따라서, 서로 다른 $\displaystyle 10$개의 자연수를 원소로 가진 집합 중, 가장 큰 원소가 $\displaystyle 104$이고 공집합이 아닌 모든 부분집합의 원소의 합이 다른 집합은 존재하지 않는다.