2배 원소 없는 집합

[출제의도] 집합을 이용하여 문제를 해결한다. 조건 (가)에 의해 집합 $A$의 모든 원소 $a$에 대하여 $2 a \notin A$이므로 $a$와 $2 a$가 집합 $A$에 동시에 속할 수 없다. $a$, $2 a$가 모두 속하는 집합들로 집합 $U$를 나누어 보면 다음과 같다. $\left\{ 1 , 2 , 4 , 8 , 16 \right\}$, $\left\{ 3 , 6 , 12 \right\}$, $\left\{ 5 , 10 \right\}$, $\left\{ 7 , 14 \right\}$, $\left\{ 9 , 18 \right\}$, $\{ 11 \}$, $\{ 13 \}$, $\{ 15 \}$, $\{ 17 \}$, $\{ 19 \}$ 각 집합에 속하는 모든 원소들을 크기 순서대로 나열 할 때, 이웃한 두 원소는 동시에 $A$에 속할 수 없다. $\left\{ 1 , 2 , 4 , 8 , 16 \right\}$에서 조건 (가)를 만족시키는 집합 $A$의 부분집합은 $\emptyset$, $\{ 1 \}$, $\{ 2 \}$, $\{ 4 \}$, $\{ 8 \}$, $\{ 16 \}$, $\{ 1 , 4 \}$, $\{ 1 , 8 \}$, $\{ 1 , 16 \}$, $\{ 2 , 8 \}$, $\{ 2 , 16 \}$, $\{ 4 , 16 \}$, $\{ 1 , 4 , 16 \}$ 이다. 이 중 집합 $A$의 원소의 개수가 최대일 때는 $\left\{ 1 , 4 , 16 \right\} \subset A$인 경우이다. 마찬가지 방법으로 $\{ 3 , 6 , 12 \}$에서 $\left\{ 3 , 12 \right\} \subset A$이고 세 집합 $\left\{ 5 , 10 \right\}$, $\left\{ 7 , 14 \right\}$, $\left\{ 9 , 18 \right\}$에서는 각 집합의 두 원소 중 하나의 원소가 $A$에 속한다. 또한 집합 $A$의 원소의 개수가 최대가 되기 위해서는 $11$, $13$, $15$, $17$, $19$는 항상 $A$에 속해야 한다. 즉, $\{ 11 , 13 , 15 , 17 , 19 \} \subset A$이다. 이상에서 반드시 포함되어야 하는 원소의 합은 $1 + 3 + 4 + 11 + 12 + 13 + 15 + 16 + 17 + 19 = 111$이다. 조건 (나)에 의해 각 집합 $\left\{ 5 , 10 \right\}$, $\left\{ 7 , 14 \right\}$, $\left\{ 9 , 18 \right\}$에서 한 개씩 선택한 원소의 합이 최대인 홀수가 되도록 $5$, $14$, $18$을 선택한다. 따라서 집합 $A$의 모든 원소의 합의 최댓값은 $111 + 5 + 14 + 18 = 148$이다.