어떤 문제인가
이 문제는 주어진 조건에 맞게 공을 주머니에 나누어 넣는 경우의 수를 구하는 문제입니다.
문제를 해결하기 위해 사용할 핵심 개념은 다음과 같습니다.
- 방정식을 이용한 상황 분류: 전체 주머니 수와 공의 개수를 이용해 주머니들의 상태를 분류합니다.
- 이웃하지 않게 배열하기 (칸막이 모델): 특정 조건(이웃하지 않음)을 만족하도록 대상을 배열하는 방법을 배웁니다.
- **중복조합 ($_nH_r$)**: 서로 다른 상자(구역)에 같은 물건을 나누어 담는 경우의 수를 구합니다.
단계별 풀이
1단계: 주머니의 상태를 변수로 잡고 방정식 세우기
먼저 주머니에 들어가는 공의 개수에 따라 주머니를 세 종류로 분류해 봅시다.
- 공이 2개 들어있는 주머니의 개수: $x$개
- 공이 1개 들어있는 주머니의 개수: $y$개
- 공이 0개 들어있는(비어있는) 주머니의 개수: $z$개
전체 주머니는 10개이고, 사용한 공은 총 8개이므로 다음과 같은 두 식을 세울 수 있습니다.
- 주머니 개수의 합:
$$x + y + z = 10$$
- 공 개수의 합:
$$2x + y = 8$$
조건 (가)에서 $y$는 4 또는 6이라고 했습니다. 이 조건에 따라 경우를 두 가지로 나누어 풀어봅시다.
2단계: [경우 1] $y = 4$인 경우
$y = 4$를 공 개수 식($2x + y = 8$)에 대입하면,
$$2x + 4 = 8 \implies x = 2$$
이 값을 주머니 개수 식($x + y + z = 10$)에 대입하면,
$$2 + 4 + z = 10 \implies z = 4$$
즉, 이 경우는 '2개짜리 주머니 2개', '1개짜리 주머니 4개', '0개짜리 주머니 4개'를 일렬로 배열하는 문제입니다. 편의상 각각을 $A(2개)$, $B(1개)$, $C(0개)$라고 부릅시다.
조건 (나)에 의해 **$A$는 다른 $A$나 $B$와 이웃할 수 없습니다.** 즉, $A$의 양옆에는 반드시 $C$가 오거나 주머니의 맨 끝이어야 합니다.
이것을 쉽게 해결하기 위해 '칸막이 모델'을 사용해 봅시다.
먼저 이웃해도 상관없는 $C$ 4개를 일렬로 세웁니다.
$$\text{_ } C \text{ _ } C \text{ _ } C \text{ _ } C \text{ _}$$
이때 $C$의 사이사이와 양 끝에 총 5개의 빈 공간(자리)이 생깁니다.
$A$는 $C$하고만 이웃할 수 있으므로, 이 5개의 자리 중 **$A$가 들어갈 자리 2개를 선택**해야 합니다. (한 자리에 $A$가 2개 들어가거나, $A$와 $B$가 한 자리에 같이 들어가면 이웃하게 되므로 안 됩니다.)
- 5개의 자리 중 $A$가 들어갈 2자리를 고르는 경우의 수:
$$\binom{5}{2} = 10$$
이제 $A$가 들어간 2자리를 제외한 **남은 3개의 자리에 $B$ 4개를 나누어 넣으면** 됩니다. $B$끼리는 이웃해도 상관없으므로, 중복조합을 사용할 수 있습니다.
- 서로 다른 3개의 자리에 중복을 허용하여 4개의 $B$를 배치하는 경우의 수:
$$_3H_4 = \binom{3+4-1}{4} = \binom{6}{4} = 15$$
따라서 [경우 1]의 경우의 수는 다음과 같습니다.
$$10 \times 15 = 150$$
3단계: [경우 2] $y = 6$인 경우
$y = 6$을 공 개수 식에 대입하면,
$$2x + 6 = 8 \implies x = 1$$
주머니 개수 식에 대입하면,
$$1 + 6 + z = 10 \implies z = 3$$
즉, **'2개짜리 주머니($A$) 1개', '1개짜리 주머니($B$) 6개', '0개짜리 주머니($C$) 3개'**를 배열하는 문제입니다.
마찬가지로 $C$ 3개를 먼저 세웁니다.
$$\text{_ } C \text{ _ } C \text{ _ } C \text{ _}$$
이때 생기는 빈 공간은 총 4개입니다.
이 4개의 자리 중 **$A$가 들어갈 자리 1개를 선택**합니다.
- 경우의 수:
$$\binom{4}{1} = 4$$
$A$가 들어간 자리를 제외한 **남은 3개의 자리에 $B$ 6개를 나누어 넣습니다.**
- 경우의 수:
$$_3H_6 = \binom{3+6-1}{6} = \binom{8}{6} = 28$$
따라서 [경우 2]의 경우의 수는 다음과 같습니다.
$$4 \times 28 = 112$$
4단계: 최종 계산
두 경우는 동시에 일어날 수 없으므로(합의 법칙), 두 경우의 수를 더합니다.
$$150 + 112 = 262$$
답
$$262$$
확인해보기
공이 들어있지 않은 주머니($C$)가 5개, 공이 1개 들어있는 주머니($B$)가 3개, 공이 2개 들어있는 주머니($A$)가 1개 있을 때, 조건 (나)를 만족하도록 9개의 주머니를 일렬로 나열하는 경우의 수는 식을 어떻게 세워서 구할 수 있을까요? 위에서 배운 '칸막이 모델'을 적용해 스스로 식을 세워보세요.