다음 조건을 만족시키는 $6$ 이하의 자연수 $a, b, c, d$ 의 모든 순서쌍 $(a, b, c, d)$ 의 개수를 구하시오. [4점]
이 문항은 주어진 다중 부등식 조건에서 종속적인 변수와 독립적인 변수를 식별하고, 가장 핵심이 되는 기준 변수(Pivot Variable)를 설정하여 경우의 수를 분할하는 논리적 추론 능력을 평가합니다. 곱의 법칙과 합의 법칙을 유기적으로 연결하여 중복조합적 상황을 대수적으로 해결할 수 있는지 묻는 고난도 문항입니다.
주어진 조건식 $a \le c \le d$ 와 $b \le c \le d$ 의 공통점과 차이점을 면밀히 관찰해야 합니다.
따라서, 교차점 역할을 하는 변수 $c$ 의 값을 기준으로 경우를 나누는 것이 가장 체계적이고 실수 없는 풀이의 출발점입니다.
자연수 $c$ 의 값을 $k$ $(1 \le k \le 6)$ 라고 가정하고, 나머지 변수 $a, b, d$ 가 가질 수 있는 경우의 수를 $k$ 에 대한 식으로 표현해 봅시다.
1) $a$ 와 $b$ 의 경우의 수
$a \le k$ 이고 $b \le k$ 이며, $a, b$ 는 독립적입니다.2) $d$ 의 경우의 수
$k \le d \le 6$ 이므로,변수 $c$ 는 $1$ 부터 $6$ 까지의 자연수를 가질 수 있으므로, Step 2에서 구한 식에 $k = 1, 2, \dots, 6$ 을 대입하여 모두 더해줍니다.
참고 도형 1 : $c$ 의 값에 따른 경우의 수 집계표
| $c$ 의 값 ($k$) | $(a, b)$ 의 개수 ($k^2$) | $d$ 의 개수 ($7-k$) | 부분합 ($k^2 \times (7-k)$) |
|---|---|---|---|
| $1$ | $1^2 = 1$ | $6$ | $6$ |
| $2$ | $2^2 = 4$ | $5$ | $20$ |
| $3$ | $3^2 = 9$ | $4$ | $36$ |
| $4$ | $4^2 = 16$ | $3$ | $48$ |
| $5$ | $5^2 = 25$ | $2$ | $50$ |
| $6$ | $6^2 = 36$ | $1$ | $36$ |
기준 변수를 $c$ 로 두지 않고, 독립 변수인 $a, b$ 중 더 큰 값을 새로운 기준(최댓값)으로 설정하여 중복조합의 개념을 적극적으로 활용할 수도 있습니다.
$M = \max(a, b)$ 라고 정의합시다.
$a \le c$, $b \le c$ 조건은 곧 $\max(a, b) \le c$ 와 동치입니다.
따라서 주어진 부등식은 $M \le c \le d \le 6$ 이라는 논리적이고 아름다운 다중 부등식으로 변환됩니다.
$M$ 이 특정 값 $m$ 을 가질 때 $(1 \le m \le 6)$, $a, b$ 중 적어도 하나는 $m$ 이어야 하고 나머지는 $m$ 이하이어야 합니다.
$M = m$ 으로 고정되었을 때, $m \le c \le d \le 6$ 을 만족하는 자연수 $(c, d)$ 의 순서쌍 개수는 서로 다른 $(7-m)$ 개의 수 $\{m, m+1, \dots, 6\}$ 중 중복을 허락하여 2개를 뽑는 중복조합입니다.
사건이 동시에(연이어) 일어나는 경우 경우의 수를 곱하고(곱의 법칙), 상호 배반인 여러 경우로 나누어질 때 각 경우의 수를 더하는(합의 법칙) 조합론의 가장 기초이자 핵심 정리입니다.
이 문제는 $c$ 를 고정하지 않고 $a, b$ 중 최댓값 $M = \max(a, b)$ 을 기준으로 $M \le c \le d \le 6$ 의 형태인 중복조합 ${}_{7-M}H_2$ 을 이용하여 풀이할 수도 있는 성질을 내포하고 있습니다.
학생들이 가장 많이 하는 실수는 $a \le c$ 와 $b \le c$ 를 합쳐서 무의식적으로 '$a \le b \le c$ 또는 $b \le a \le c$' 라고 가정해버리는 것입니다.
주어진 논리식은 $P \land Q$ 의 형태입니다. 즉, $(a \le c) \land (b \le c)$ 입니다.
만약 $c = 4$ 라고 할 때, $a$ 가 $3$ 이라는 사건이 $b$ 의 값에 영향을 미칠까요?
$a = 3$ 이더라도 명제 $(b \le 4)$ 의 참/거짓에는 아무런 영향을 주지 않습니다. $b$ 는 여전히 $1, 2, 3, 4$ 중 어떤 값이든 될 수 있습니다.
이는 두 변수가 서로에 대해 구속 조건을 가지지 않는 직교하는 2차원 평면상의 좌표 $(a, b)$ 를 선택하는 것과 수학적으로 동치(Cartesian Product)입니다. 따라서 $a$ 의 경우의 수와 $b$ 의 경우의 수를 단순히 곱하는 것이 정당합니다.
부등식 $x \le y \le z$ 형태를 해결할 때 자주 등장하는 중복조합 기호 ${}_n H_r$ 이 왜 조합 ${}_{n+r-1} C_r$ 과 같은지 칸막이 모델(Stars and Bars)을 통해 증명합니다.
1. 서로 다른 $n$ 개의 대상에서 중복을 허락하여 $r$ 개를 뽑는 상황을 가정합니다.
2. $n$ 개의 서로 다른 종류를 구분하기 위해서는 $(n-1)$ 개의 '칸막이(|)'가 필요합니다.
3. 뽑힌 $r$ 개의 대상을 '별(*)'이라고 합시다. 우리의 목표는 칸막이 사이에 별을 배치하는 경우의 수를 구하는 것으로 치환됩니다.
4. 예를 들어 3종류($A, B, C$) 중 4개를 뽑는다면 칸막이는 2개, 별은 4개입니다.
(** | * | *) $\rightarrow$ $A$ 2개, $B$ 1개, $C$ 1개를 의미합니다.
5. 즉, 전체 (별 $r$ 개) + (칸막이 $n-1$ 개) = $n+r-1$ 개의 빈자리가 있고, 이 중 별이 들어갈 $r$ 개의 자리를 선택하는 조합의 수와 같습니다.
따라서, ${}_n H_r = {}_{n+r-1} C_r$ 이 성립합니다.
기준 변수 c 의 값을 변경하며 $a, b$ 의 평면(면적)과 $d$ 의 수직선(길이)이 어떻게 변하는지 관찰하세요.