“
멱집합(P(A))의 원소가 될 수 없는 것을 찾는 문제입니다.
접근법:
1. 집합 A = {1, 2, 3} 입니다.
2. 멱집합 P(A)의 원소는 A의 **부분집합**들입니다.
– P(A) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
3. 각 보기가 P(A)의 원소 목록에 있는지 확인합니다.
4. 보기 ③의 0은 숫자이며, A의 부분집합이 아니므로 P(A)의 원소가 될 수 없습니다.
주의할 점:
멱집합의 원소는 항상 ‘집합’의 형태를 띠고 있어야 합니다. (공집합 ∅ 포함)
”
멱집합의 원소가 될 수 없는 것 찾기
“
멱집합(Power Set)의 부분집합의 개수를 구하는 문제입니다.
접근법:
1. 먼저 집합 A를 원소나열법으로 나타냅니다. A = {1, 3, 9}.
2. P(A)는 집합 A의 **모든 부분집합을 원소로 갖는** 집합입니다.
3. 집합 A의 원소 개수는 3개이므로, A의 부분집합의 개수는 2³ = 8개 입니다.
4. 즉, 집합 P(A)의 **원소의 개수가 8개**입니다. n(P(A)) = 8.
5. 문제에서 묻는 것은 P(A)의 ‘부분집합’의 개수이므로, 2^(n(P(A))) = 2⁸ 입니다.
주의할 점:
P(A)의 원소 개수(2ⁿ)와 P(A)의 부분집합 개수(2^(2ⁿ))를 혼동하지 않도록 주의해야 합니다.
”
멱집합의 부분집합의 개수 구하기
“
원소 개수 조건이 추가된, 각 부분집합의 가장 큰 원소들의 합을 구하는 문제입니다.
접근법:
1. 각 원소가 ‘가장 큰 원소’로서 몇 번이나 선택되는지를 셉니다.
2. (9가 최대 원소인 경우) 9를 반드시 포함하고, 9보다 큰 원소는 없는(당연) 부분집합 중, 원소 개수가 2 이상인 것을 셉니다. 9를 제외한 나머지 {1,3,5,7} (4개)로 만드는 부분집합(2⁴개)에 9를 추가하면 되는데, 공집합에 9를 추가한 {9}는 원소가 1개이므로 제외합니다. (2⁴ – 1)번 등장.
3. (7이 최대 원소인 경우) 7을 반드시 포함하고 9는 포함하지 않는 부분집합 중, 원소 개수가 2 이상인 것을 셉니다. 7,9 제외한 {1,3,5}(3개)로 만드는 부분집합(2³개) 중, 공집합 제외. (2³ – 1)번 등장.
4. 이 규칙을 반복하고, 최종 합 = (9 × (2⁴-1)) + (7 × (2³-1)) + … 를 계산합니다.
주의할 점:
최대 원소 문제는 ‘그 원소보다 큰 원소는 모두 제외’하는 조건이 숨어있으며, ‘원소 개수 2 이상’ 조건 때문에 각 경우에서 1씩 빼주어야 합니다.
”
각 부분집합의 최대 원소들의 총합 구하기
“
766번 문제와 동일한 유형으로, 각 부분집합의 가장 작은 원소들의 합을 구하는 문제입니다.
접근법:
1. 각 원소가 ‘가장 작은 원소’로서 몇 번이나 선택되는지를 셉니다.
2. (1/16이 가장 작은 경우) 1/16을 반드시 포함하고, 그보다 작은 원소는 없는(이 경우 해당 없음) 부분집합입니다. 나머지 4개 원소로 만들 수 있는 부분집합의 개수인 2⁴ 번 등장합니다.
3. (1/8이 가장 작은 경우) 1/8을 반드시 포함하고, 1/16은 포함하지 않는 부분집합입니다. 나머지 3개 원소로 만들 수 있는 부분집합의 개수인 2³ 번 등장합니다.
4. 이 규칙을 모든 원소에 대해 적용합니다.
5. 최종 합 = (1/16 × 2⁴) + (1/8 × 2³) + … + (1 × 2⁰)
주의할 점:
원소들이 분수이더라도, ‘최소 원소’를 세는 원리는 동일합니다. 자기보다 작은 원소는 모두 제외하고 계산합니다.
”
각 부분집합의 최소 원소들의 총합(분수)
“
각 부분집합의 최소 원소들을 모두 더하는 문제입니다.
접근법:
1. 각 원소가 ‘최소 원소’로서 몇 번이나 선택되는지를 셉니다.
2. (1이 최소 원소인 경우) 1을 반드시 포함하고, 1보다 작은 원소는 없는 부분집합의 개수입니다. 이는 1을 제외한 나머지 원소 {2, 4, …, 64} (6개)로 만들 수 있는 부분집합의 개수인 2⁶과 같습니다.
3. (2가 최소 원소인 경우) 2를 반드시 포함하고, 1은 포함하지 않는 부분집합의 개수입니다. 이는 2와 1을 제외한 나머지 5개 원소로 만들 수 있는 부분집합의 개수인 2⁵와 같습니다.
4. 이와 같은 방식으로 각 원소에 대해 계산합니다.
5. 최종 합 = (1 × 2⁶) + (2 × 2⁵) + (4 × 2⁴) + … + (64 × 2⁰)
주의할 점:
최소 원소 문제는 ‘그 원소보다 작은 원소는 모두 제외’하는 조건이 숨어있다는 것을 파악하는 것이 핵심입니다.
”
각 부분집합의 최소 원소들의 총합 구하기
“
공집합을 제외한 모든 진부분집합들의 원소의 총합을 이용해 미지수를 찾는 문제입니다.
접근법:
1. 먼저 집합 A의 모든 부분집합(2⁴=16개)의 원소 총합을 구합니다. 각 원소는 2⁴⁻¹ = 8번씩 포함되므로, 총합은 8(1+2+3+a) 입니다.
2. 문제에서 요구하는 합은 이 총합에서 **공집합(합=0)과 집합 A 자신(합=6+a)을 제외**한 것입니다.
3. 따라서, 8(6+a) – (0) – (6+a) = 7(6+a) = 42+7a 입니다.
4. 이 값이 91과 같다고 등식을 세워 a값을 구합니다.
5. n은 공집합을 제외한 진부분집합의 개수이므로 2⁴-2=14 입니다. 최종적으로 n+a를 계산합니다.
주의할 점:
문제에서 제외하라고 하는 부분집합(공집합, 진부분집합이 아닌 자기 자신)을 정확히 파악하고, 그들의 원소 합을 전체 합에서 빼주어야 합니다.
”
진부분집합들의 원소 총합과 미지수 찾기
“
A ⊂ X ⊂ B를 만족하는 모든 집합 X들의 원소의 총합을 구하는 문제입니다.
접근법:
1. 집합 X는 {1,2}를 반드시 포함하고, B-A={4,8}의 원소를 추가로 가질 수 있습니다.
2. (고정 원소의 합) {1,2}는 모든 가능한 집합 X에 항상 포함됩니다. 집합 X의 개수는 2^(4-2)=4개 이므로, 1과 2는 각각 4번씩 더해집니다.
3. (선택 원소의 합) B-A={4,8}의 원소들이 각각 몇 번이나 더해지는지 셉니다. 4가 포함되는 경우는 {1,2,4}를 포함하는 X의 개수와 같으므로, 나머지 원소 {8}로 만들 수 있는 부분집합의 개수인 2¹=2번 입니다. 8도 마찬가지로 2번 더해집니다.
4. 모든 합 = (1×4 + 2×4) + (4×2 + 8×2)
주의할 점:
반드시 포함되는 원소와, 선택적으로 포함되는 원소를 나누어 각각이 총 몇 번씩 더해지는지를 계산해야 합니다.
”
A⊂X⊂B를 만족하는 집합들의 원소 총합
“
원소의 개수가 특정 값(3개)으로 정해진 부분집합들의 모든 원소의 합을 구하는 문제입니다.
접근법:
1. 760번과 동일하게, 각 원소가 총 몇 번이나 더해지는지를 셉니다.
2. 특정 원소(예: 1)가 포함되는 3개짜리 부분집합의 개수는, **1을 반드시 포함**하고 나머지 4개의 원소 {2,3,4,5} 중에서 **2개를 추가로 선택**하는 경우의 수와 같습니다. (₄C₂)
3. 모든 원소(1,2,3,4,5)에 대해 이 규칙은 동일하게 적용됩니다.
4. 따라서 모든 원소의 총합은 (1+2+3+4+5) × (₄C₂) 입니다.
주의할 점:
조합(Combination)을 이용하여 특정 원소가 포함되는 부분집합의 개수를 정확하게 세는 것이 핵심입니다.
”
원소 개수가 정해진 부분집합의 원소 총합
“
모든 부분집합의 원소의 곱을 다시 모두 곱하는 문제입니다.
접근법:
1. 760번 문제와 유사하게, 각 원소가 최종 곱셈에서 총 몇 번 곱해지는지(지수가 얼마인지)를 생각합니다.
2. 특정 원소(예: 1)가 곱해지는 횟수는, **1을 반드시 포함하는 부분집합의 개수**와 같습니다.
3. 집합 A의 원소는 4개이므로, 1을 반드시 포함하는 부분집합의 개수는 2⁴⁻¹ = 8개 입니다.
4. 마찬가지로, 2, 4, 8도 각각 8번씩 곱해집니다.
5. 따라서 최종 곱은 1⁸ × 2⁸ × 4⁸ × 8⁸ 입니다. 이 값을 지수법칙을 이용해 2의 거듭제곱으로 표현하고 지수 k를 구합니다.
주의할 점:
문제에서 ‘공집합이 아닌’ 부분집합이라고 했지만, 공집합은 원소가 없어 곱에 영향을 주지 않으므로, 전체 부분집합을 기준으로 계산해도 결과는 같습니다.
”
모든 부분집합 원소의 총곱 구하기
“
특정 조건을 만족하는 부분집합들의 모든 원소의 합을 구하는 문제입니다. 760번의 응용 유형입니다.
접근법:
1. (집합 X의 개수) 먼저 조건을 만족하는 집합 X가 몇 개인지 구합니다. X는 {1,3,5}를 제외한 나머지 원소 {2,4,6}으로 만들 수 있는 부분집합에 {1}을 추가한 형태입니다. 따라서 2³ = 8개 입니다.
2. (각 원소가 더해지는 횟수)
– 1은 모든 8개의 집합 X에 반드시 포함됩니다.
– 2가 포함되는 경우는, {1}을 포함하고 {3,5}는 제외하며, 2를 반드시 포함하는 부분집합의 개수와 같습니다. (2³⁻¹ = 4개)
– 4와 6도 마찬가지로 각각 4번씩 더해집니다.
3. 모든 합 = (1×8) + (3×0) + (5×0) + (2×4) + (4×4) + (6×4)
주의할 점:
주어진 조건(포함/불포함)을 정확히 반영하여 각 원소가 최종적으로 몇 번이나 합산되는지를 계산해야 합니다.
”
특정 조건의 부분집합 원소 총합 구하기
