30. 비어 있는 주머니 10개가 일렬로 놓여 있고, 공 8개가 있다.
각 주머니에 들어 있는 공의 개수가 2 이하가 되도록 공을 주머니에 남김없이 나누어 넣을 때, 다음 조건을 만족시키는 경우의 수를 구하시오. (단, 공끼리는 서로 구별하지 않는다.) [4점]
(가) 들어 있는 공의 개수가 1인 주머니는 4개 또는 6개이다.
(나) 들어 있는 공의 개수가 2인 주머니와 이웃한 주머니에는 공이 들어 있지 않다.
본 문항은 방정식의 정수해 개수와 중복조합을 활용한 경우의 수 계산 능력을 평가합니다. 특히 조건 (나)의 '이웃하지 않는다'는 제한 조건을 해결하기 위해, 배열된 대상들 사이의 '공간(Space)'을 설정하고 그 공간에 빈 주머니(공이 0개인 주머니)를 필수적으로 배치하는 공간 모델링(Stars and Bars 변형) 기법을 완벽히 숙지하고 있는지 묻는 고난도 추론 문제입니다.
주머니에 들어갈 수 있는 공의 개수는 $0$, $1$, $2$ 중 하나입니다. 각 개수별 주머니의 개수를 미지수로 설정합니다.
$x_0$ : 공이 $0$개인 주머니의 개수
$x_1$ : 공이 $1$개인 주머니의 개수
$x_2$ : 공이 $2$개인 주머니의 개수
전체 주머니는 $10$개, 전체 공은 $8$개이므로 다음 연립방정식이 성립합니다.
조건 (가)에 의해 $x_1 = 6$ 또는 $x_1 = 4$ 이므로, 두 가지 케이스로 나누어 풉니다.
$x_1 = 6$을 대입하면 $x_2 = 1$, $x_0 = 3$ 이 됩니다. 즉, [1인 주머니 6개, 2인 주머니 1개, 빈 주머니 3개]를 일렬로 나열하는 경우의 수입니다.
우선 공이 들어있는 주머니들(1인 주머니 6개, 2인 주머니 1개)을 먼저 나열합니다. 같은 것이 있는 순열에 의해 그 경우의 수는 다음과 같습니다.
먼저 나열한 7개의 주머니(1인 주머니 6개 + 2인 주머니 1개)를 하나의 벽(칸막이)이라고 생각해 보세요. 이 주머니들 사이사이와 맨 앞, 맨 뒤에 남은 빈 주머니(0)가 들어갈 수 있는 '자리(공간)'가 생깁니다.
위 그림처럼 7개의 주머니가 일렬로 서 있다면, 화살표(↓)로 표시된 공간은 정확히 $7 + 1 = 8$개가 됩니다.
이제 남은 3개의 빈 주머니를 이 8개의 화살표 공간 중 어딘가에 자유롭게 나누어 담는 문제로 바뀝니다. 한 공간에 빈 주머니가 여러 개 들어가도 무방하므로(예: 0이 2개 연속으로 배치됨), 서로 다른 8개의 공간에서 중복을 허락하여 남은 빈 주머니 수만큼 고르는 '중복조합' 상황이 됩니다.
조건 (나) : "2인 주머니와 이웃한 주머니에는 공이 들어 있지 않다."
이 조건은 2인 주머니의 양옆 공간(단, 양 끝에 놓일 경우 한쪽 공간만)에는 반드시 빈 주머니($0$)가 최소 1개 이상 들어가야 함을 의미합니다. 2인 주머니가 7개의 뼈대 중 어디에 위치하느냐에 따라 필수적으로 소모되는 빈 주머니의 개수가 달라집니다.
2인 주머니가 맨 앞이나 맨 뒤에 놓이는 경우입니다. (총 2가지)
아래 그림처럼 2인 주머니가 맨 앞에 놓였다고 가정해 봅시다. 2인 주머니의 '이웃'은 바로 오른쪽 한 곳뿐입니다. 조건 (나)를 지키기 위해 이 이웃한 1개의 공간에 빈 주머니(0)를 1개 필수적으로 배치해야 합니다.
2 0 0 1), 2인 주머니와 이웃하지 않는다는 조건은 여전히 완벽하게 충족됩니다.
2인 주머니가 양 끝을 제외한 중간 자리에 놓이는 경우입니다. (총 7개의 뼈대 중 양 끝 2개를 뺀 5가지)
아래 그림처럼 2인 주머니 양옆으로 '이웃'이 두 곳 생깁니다. 따라서 양옆 2개의 공간에 빈 주머니(0)를 각각 1개씩, 총 2개를 필수적으로 배치해야 합니다.
0 0 형태로 두 개 연속으로 나열될 뿐입니다. 2인 주머니의 이웃은 여전히 '0개'인 상태로 든든하게 보호받으므로, 조건 (나)에 전혀 위배되지 않습니다. 따라서 8곳 중 아무 곳이나 자유롭게 고르면 됩니다.
$x_1 = 4$를 대입하면 $x_2 = 2$, $x_0 = 4$ 가 됩니다. [1인 주머니 4개, 2인 주머니 2개, 빈 주머니 4개]를 나열해야 합니다.
마찬가지로 공이 있는 주머니 6개를 먼저 나열합니다. (경우의 수 : $\frac{6!}{4!2!} = 15$가지). 사이사이의 공간은 $7$곳입니다.
이 15가지를 '2인 주머니의 인접 형태'에 따라 3가지 패턴으로 분류하여 필수 빈 주머니 개수($k$)를 파악합니다.
예: ... _ [2] _ [2] _ ...
[2]와 [2] 사이의 공간에는 반드시 빈 주머니가 필요합니다. 놀랍게도 빈 주머니 1개가 양쪽 [2]의 이웃 조건을 모두 만족시켜 줍니다! 따라서 필요한 필수 공간은 2곳 뿐인 경우가 발생합니다.
221111, 111122, 211112 (끝과 끝) -> 총 3가지212111, 211211, 211121,
122111, 121112, 112211,
112112, 111221, 111212
121211, 121121, 112121212111, 211211, 211121,
122111, 121112, 112211,
112112, 111221, 111212
121211, 121121, 112121분할한 Case 1과 Case 2의 경우의 수를 합산합니다.
방정식 $x_1 + x_2 + ... + x_n = r$ 의 음이 아닌 정수해의 개수는 중복조합 $_{n}\mathrm{H}_{r}$ 로 계산합니다. 공간에 빈 주머니를 분배하는 논리의 근간입니다.
$n$개 중에서 서로 같은 것이 각각 $p, q, ...$ 개 있을 때 일렬로 나열하는 경우의 수 $\frac{n!}{p!q!...}$ 입니다. 공이 들어있는 주머니들의 뼈대를 세울 때 사용됩니다.
특정 원소들이 이웃하지 않아야 할 때, 나머지 원소들을 먼저 나열하고 그 '사이사이의 공간(Bars)'에 금지된 원소(Stars)를 끼워 넣거나, 혹은 이 문제처럼 특정 대상 사이에 빈 공간을 강제로 할당한 뒤 남은 공간을 자유 분배하는 기법입니다.
학생들이 가장 자주 범하는 실수는 "2인 주머니가 2개 있으면, 이를 막기 위한 빈 주머니(0)도 무조건 각각 따로따로 2개씩 필요할 것이다"라고 착각하는 것입니다. 즉, 빈 주머니가 양쪽을 모두 커버하는 상황을 놓치게 됩니다.
위 그림을 보세요. 가운데 있는 빈 주머니(0) 하나가 왼쪽의 '2'에게도 이웃이 없게 해주고, 오른쪽의 '2'에게도 이웃이 없게 만들어 줍니다. 하나의 0이 양쪽 모두의 조건을 동시에 만족시키는 '공용 방패' 역할을 완벽히 수행하는 것이죠.
따라서 2인 주머니 두 개가 인접하려 할 때(패턴 A), 그 사이에 빈 주머니(0)를 단 1개만 배치해도 조건 (나)에 전혀 위배되지 않습니다. 이를 억지로 2개씩 분리하려고 하면 답을 구할 수 없습니다.
$n$개의 서로 다른 상자(공간)에 $r$개의 똑같은 공(빈 주머니)을 넣는 방법의 수는 $n$개의 변수 $x_1, ..., x_n$에 대하여 $x_1 + x_2 + ... + x_n = r$ 을 만족하는 음이 아닌 정수해의 개수와 같습니다.
이를 시각적으로 증명하기 위해 $r$개의 공을 일렬로 나열합니다. ($O$ 로 표시)
이 공들을 $n$개의 그룹으로 나누기 위해서는 칸막이(Bar, $|$ 로 표시)가 필요합니다. 그룹이 $n$개이므로 칸막이는 $(n-1)$개가 필요합니다.
예를 들어 $x_1=2, x_2=0, x_3=1$ 이라면 (n=3, r=3):
결국 이 문제는 $r$개의 공과 $(n-1)$개의 칸막이를 일렬로 배열하는 경우의 수와 정확히 일치합니다.
전체 기호의 개수는 $r + (n-1)$ 개이며, 이 중 공을 놓을 자리 $r$개를 선택하는 조합의 수이므로 다음이 성립합니다.
'빈 주머니를 이용한 공간 분리' 과정을 시각적 슬라이드로 확인합니다. 탭을 선택하고 다음 슬라이드로 넘기며 빨간색 주머니(2) 양 옆 공간의 변화를 관찰하세요.