일등급
부분집합의 개수
최대·최소 원소
출제의도
이 문항은 부분집합의 개수 공식을 ‘조건이 걸린 원소’와 ‘자유로운 원소’로 나누어 쓸 수 있는지를 묻습니다. 최대인 원소와 최소인 원소가 정해지면 그 두 원소는 반드시 포함되어야 하고, 두 값 사이에 놓인 원소들만 넣거나 빼는 자유가 생깁니다. 이 구조를 파악하면 계산은 2의 거듭제곱 몇 개를 더하는 일로 끝납니다.
일등급 문제로 배치된 이유는 두 겹의 경우 나누기가 필요하기 때문입니다. 먼저 합이 8이 되는 (최소, 최대) 쌍을 빠짐없이 찾아야 하고, 각 쌍마다 사이에 있는 원소가 몇 개인지를 다시 세야 합니다. 어느 한쪽만 놓쳐도 답이 달라집니다.
단계별 힌트
힌트 1단계 · 발상과 연결고리
집합 X를 통째로 고르려 하지 말고, 먼저 최소인 원소와 최대인 원소를 먼저 확정해 보세요. 이 둘이 정해지면 X의 나머지 원소가 어디에 놓일 수 있는지가 자동으로 결정됩니다.
조건 n(X)≥2에 주목하세요. 원소가 2개 이상이므로 최소인 원소와 최대인 원소는 서로 다른 값입니다. 두 값이 같아지는 경우는 애초에 후보에서 빠집니다.
힌트 2단계 · 풀이 설계 (계산은 직접 해보세요)
최소인 원소를 m, 최대인 원소를 M이라 하면 m<M이고 m+M=8입니다. A={1, 2, 3, 4, 5, 6, 7} 안에서 이 조건을 만족하는 (m, M)의 쌍을 모두 적어보세요. 세 가지가 나옵니다.
각 쌍마다 m과 M은 반드시 X에 들어가고, m보다 작거나 M보다 큰 원소는 절대 들어갈 수 없습니다. 따라서 자유롭게 넣고 뺄 수 있는 원소는 m과 M 사이에 있는 원소들뿐이고, 그 개수가 k개면 경우의 수는 2k입니다. 세 경우를 더하면 끝입니다.
정답 확인
정답 42
상세 해설
풀이 흐름 한눈에 정리
해설 이미지의 계산을 따라가기 전에 전체 흐름을 문장으로 정리하면 다음과 같습니다.
STEP A합이 8이 되는 (최소, 최대) 쌍 나열하기
S(X)=8이므로 8=1+7=2+6=3+5의 세 가지로 나뉩니다. n(X)≥2에서 최소와 최대가 서로 다르므로 4+4는 후보가 되지 않습니다. 이 세 갈래가 곧 경우 나누기의 기준입니다.
STEP B각 경우마다 사이 원소의 부분집합 개수 세기
최소·최대가 1과 7이면 사이 원소는 {2, 3, 4, 5, 6}의 5개이므로 25=32, 2와 6이면 {3, 4, 5}의 3개이므로 23=8, 3과 5면 {4}의 1개이므로 21=2입니다. 세 값을 더하면 32+8+2=42가 됩니다.
1등급 다른 풀이 · 일반식으로 한 번에 세기
세 경우를 따로 세지 않고 하나의 식으로 묶을 수도 있습니다. 최소가 m, 최대가 M일 때 사이에 있는 원소의 개수는 M−m−1개이므로, 그 경우의 수는 언제나 2M−m−1입니다.
m+M=8, m<M이므로 (m, M)=(1, 7), (2, 6), (3, 5)이고 지수 M−m−1은 각각 5, 3, 1이 됩니다. 따라서 구하는 개수는 25+23+21=42로 곧바로 나옵니다. 합이 8이 아닌 다른 값으로 바뀌어도 이 식만 그대로 쓰면 되므로, 변형 문제에 훨씬 강한 접근입니다.
같은 아이디어를 확장한 것이 이 문항의 내신 연계 유형입니다. 모든 부분집합에 대해 (최소+최대)를 전부 더하라는 형태로 나오면, 최소인 원소를 기준으로 한 번, 최대인 원소를 기준으로 한 번 세어 합치는 방식으로 처리합니다.
실수를 줄이는 전략
- n(X)≥2 조건을 반드시 먼저 확인하세요. 이 조건이 없으면 X={4}처럼 최소와 최대가 같은 경우까지 세어야 하므로 답이 달라집니다.
- 최소·최대로 지정한 두 원소는 ‘선택하는 대상’이 아니라 ‘고정된 원소’입니다. 이 둘까지 2의 지수에 넣어버리면 개수가 크게 부풀려집니다.
- m보다 작은 원소와 M보다 큰 원소는 넣을 수 없다는 점을 잊지 마세요. 예를 들어 최소가 2인 경우에 1을 넣으면 최소가 1로 바뀌어 조건이 깨집니다.
- (m, M) 쌍을 셀 때 (7, 1)처럼 순서를 뒤집은 쌍을 따로 세면 중복입니다. 항상 m<M으로 고정해 두고 나열하세요.
엄선된 풀이 영상
위 풀이 흐름을 영상으로 한 번 더 확인하고 싶다면 재생 버튼을 누르세요.