자연계열 3번

<다>㉡ 주머니1, 주머니2, ⋯, 주머니10에는 각각 동전들이 $\displaystyle 2^{10}$개 들어 있다. 동전들은 진짜 동전과 가짜 동전으로 구분되며, 진짜 동전들의 무게는 모두 같고, 가짜 동전의 무게는 진짜 동전의 무게보다 1그램이 작다. 각 주머니의 동전들은 모두 진짜이거나 모두 가짜이고, 이 중 모두 가짜 동전들이 들어 있는 주머니는 1개 이상이다.각각의 주머니 $\displaystyle k$에서 $\displaystyle k$개, 즉, 주머니1에서 1개, 주머니2에서 2개, ⋯, 주머니10에서 10개의 동전을 꺼내, 그 꺼낸 동전들 $\displaystyle 1+2+\cdots+10=55$개의 무게를 재었을 때, 그 무게의 합이 $\displaystyle 55$개 동전 모두가 진짜일 때의 합보다 $\displaystyle 5$그램이 작다고 하자. 이때, $\displaystyle 5=1+4=2+3$이므로 가짜 동전들이 들어 있는 주머니들의 가능한 경우는 다음의 3가지이다.주머니5, 주머니1과 주머니4, 주머니2와 주머니3.㉢ 집합 $\displaystyle B=\{b_1,b_2,\cdots,b_n\}$의 모든 원소는 서로 다른 자연수이고 $\displaystyle b_1<b_2<\cdots<b_n$이면$\displaystyle 1\le b_1,\ 2\le b_2,\ \cdots,\ n\le b_n$이다. 즉, 집합 $\displaystyle B$의 원소의 개수 $\displaystyle n$은 집합 $\displaystyle B$의 원소 중 가장 큰 자연수 $\displaystyle b_n$보다 작거나 같다.집합 $\displaystyle A_{10}=\{a_1,a_2,\cdots,a_{10}\}$의 모든 원소는 서로 다른 자연수이고, 집합 $\displaystyle A_{10}$의 공집합이 아닌 서로 다른 모든 부분집합의 개수는 $\displaystyle 2^{10}-1$이다. 이러한 $\displaystyle 2^{10}-1$개의 부분집합들은 각각 원소의 합이 서로 다르다고 하자. 이때,$\displaystyle a_1+a_2+\cdots+a_{10}\ge2^{10}-1=1023\quad\cdots\cdots\quad(1)$임을 증명할 수 있다. 집합 $\displaystyle A_{10}$의 원소 중 가장 큰 자연수를 $\displaystyle x$라고 하면$\displaystyle a_1+a_2+\cdots+a_{10}\le x+(x-1)+(x-2)+\cdots+(x-8)+(x-9)=10x-45$이고 (1)에 의해 $\displaystyle x\ge\frac1{10}(2^{10}+44)=106.8$이다. 집합 $\displaystyle A_{10}$의 예로는 집합$\displaystyle \{1,2,2^2,2^3,\cdots,2^9\},\ \{2^{10}+1,2^{10}+2,2^{10}+2^2,2^{10}+2^3,\cdots,2^{10}+2^9\}$등이 있다.