어떤 문제인가
이 문제는 주어진 세 가지 조건을 만족하는 함수 $f: X \to X$의 개수를 구하는 문제입니다. 문제 해결을 위해 우리가 꼭 알아야 할 핵심 개념은 다음과 같습니다.
- **중복조합 ($\mathbf{H}$)**: 조건 (가)처럼 $a \le b$일 때 $f(a) \le f(b)$를 만족하는 함수의 개수를 구할 때 사용합니다. 서로 다른 $n$개에서 중복을 허용하여 $r$개를 택하는 조합의 수인 $_nH_r = _{n+r-1}C_r$ 공식을 활용합니다.
- 조건의 분할과 대칭성: 조건 (나)와 (다)를 기준으로 정의역을 $\{1, 2, 3, 4, 5\}$와 $\{6, 7, 8, 9, 10\}$의 두 그룹으로 나누어 생각하면 복잡한 문제를 훨씬 쉽게 해결할 수 있습니다. 또한, 두 그룹 사이에 존재하는 '대칭성'을 이용하면 계산 과정을 절반으로 줄일 수 있습니다.
단계별 풀이
1단계: $f(5)$와 $f(6)$이 가질 수 있는 값 정하기
조건 (다)에서 $f(6) = f(5) + 6$이라고 했습니다. 이 식을 만족하는 $f(5)$와 $f(6)$의 후보를 먼저 찾아봅시다.
- 공역이 $X = \{1, 2, \dots, 10\}$이므로 함숫값은 $1$ 이상 $10$ 이하의 자연수여야 합니다.
- 조건 (나)에 의해 $f(5) \le 5$이고, $f(6) \ge 6$이어야 합니다.
- $f(6) = f(5) + 6$이므로, $f(5)$의 값에 따라 $f(6)$의 값이 결정됩니다.
가능한 쌍 $(f(5), f(6))$을 구해보면 다음과 같이 딱 4가지 경우만 존재합니다.
- $f(5) = 1$ 일 때, $f(6) = 7$
- $f(5) = 2$ 일 때, $f(6) = 8$
- $f(5) = 3$ 일 때, $f(6) = 9$
- $f(5) = 4$ 일 때, $f(6) = 10$
(만약 $f(5) = 5$가 되면 $f(6) = 11$이 되어 공역을 벗어나므로 불가능합니다.)
이제 이 4가지 경우에 대해, **[1부: $f(1)$부터 $f(5)$까지 정하기]와 [2부: $f(6)$부터 $f(10)$까지 정하기]**로 나누어 경우의 수를 구해봅시다.
2단계: [1부] $f(5) = k$ 일 때, $f(1)$부터 $f(5)$까지 정하는 경우의 수
조건 (가)에 의해 $f(1) \le f(2) \le f(3) \le f(4) \le f(5) = k$가 성립해야 합니다.
또한 조건 (나)에 의해 $f(1) \le 1$이므로 **$f(1) = 1$로 고정**됩니다.
따라서 우리는 $1 \le f(2) \le f(3) \le f(4) \le k$를 만족하면서, 조건 (나)의 $f(x) \le x$를 만족하는 경우의 수를 구해야 합니다.
$k$의 값($1$부터 $4$까지)에 따라 나누어 계산해 봅시다.
- **경우 1) $f(5) = 1$ 인 경우**
$1 \le f(2) \le f(3) \le f(4) \le 1$ 이므로, 모든 값이 $1$이 되어야 합니다.
* $f(1)=f(2)=f(3)=f(4)=f(5)=1$ (조건 (나) 모두 만족)
* **경우의 수: $1$가지**
- **경우 2) $f(5) = 2$ 인 경우**
$1 \le f(2) \le f(3) \le f(4) \le 2$ 인 경우입니다.
이때 조건 (나)의 제한 조건은 $f(2) \le 2, f(3) \le 3, f(4) \le 4$인데, 함숫값이 어차피 $1$ 또는 $2$뿐이므로 이 조건들은 자동으로 만족됩니다.
따라서 $\{1, 2\}$ 중에서 중복을 허용하여 $f(2), f(3), f(4)$가 될 3개의 숫자를 고르는 중복조합과 같습니다.
* $_2H_3 = _4C_3 = 4$
* **경우의 수: $4$가지**
- **경우 3) $f(5) = 3$ 인 경우**
$1 \le f(2) \le f(3) \le f(4) \le 3$ 인 경우입니다.
조건 (나)에서 $f(2) \le 2$여야 하므로, $f(2)$는 $3$이 될 수 없습니다. ($f(3) \le 3, f(4) \le 4$는 자동으로 만족됩니다.)
* 전체 경우의 수: $\{1, 2, 3\}$에서 3개를 고르는 중복조합 $_3H_3 = _5C_3 = 10$가지
* 안 되는 경우 ($f(2) = 3$인 경우): $f(2)=3$이면 $3 \le f(3) \le f(4) \le 3$이므로 $f(3)=3, f(4)=3$으로 고정됩니다. 즉, $(3, 3, 3)$의 $1$가지뿐입니다.
* **경우의 수: $10 - 1 = 9$가지**
- **경우 4) $f(5) = 4$ 인 경우**
$1 \le f(2) \le f(3) \le f(4) \le 4$ 인 경우입니다.
조건 (나)에서 $f(2) \le 2$, $f(3) \le 3$이어야 합니다. $f(2)$의 값에 따라 나누어 구해보겠습니다.
* **$f(2) = 1$일 때**: $1 \le f(3) \le f(4) \le 4$ 이고 $f(3) \le 3$이어야 합니다.
* $f(3) = 1$이면 $f(4)$는 $1, 2, 3, 4$ 중 가능 ($4$가지)
* $f(3) = 2$이면 $f(4)$는 $2, 3, 4$ 중 가능 ($3$가지)
* $f(3) = 3$이면 $f(4)$는 $3, 4$ 중 가능 ($2$가지)
* 소계: $4 + 3 + 2 = 9$가지
* **$f(2) = 2$일 때**: $2 \le f(3) \le f(4) \le 4$ 이고 $f(3) \le 3$이어야 합니다.
* $f(3) = 2$이면 $f(4)$는 $2, 3, 4$ 중 가능 ($3$가지)
* $f(3) = 3$이면 $f(4)$는 $3, 4$ 중 가능 ($2$가지)
* 소계: $3 + 2 = 5$가지
* **경우의 수: $9 + 5 = 14$가지**
3단계: [2부] 대칭성을 이용하여 $f(6)$부터 $f(10)$까지 정하는 경우의 수 구하기
이제 $f(6)$부터 $f(10)$까지 정하는 경우의 수를 구해야 합니다. 조건들을 잘 살펴보면 1부의 상황과 완벽한 대칭 구조를 이루고 있음을 알 수 있습니다.
- 1부: $f(1)=1$로 고정, $f(x) \le x$, 위로 갈수록 범위가 넓어짐.
- 2부: $f(10)=10$으로 고정 (조건 (나)에서 $f(10) \ge 10$이므로), $f(x) \ge x$, 아래로 갈수록 범위가 넓어짐.
이 대칭성 덕분에 2부의 경우의 수는 1부의 결과를 거꾸로 적용하면 됩니다!
- $f(6) = 7$ 인 경우 (1부의 $f(5) = 4$인 상황과 대칭) $\to$ **$14$가지**
- $f(6) = 8$ 인 경우 (1부의 $f(5) = 3$인 상황과 대칭) $\to$ **$9$가지**
- $f(6) = 9$ 인 경우 (1부의 $f(5) = 2$인 상황과 대칭) $\to$ **$4$가지**
- $f(6) = 10$ 인 경우 (1부의 $f(5) = 1$인 상황과 대칭) $\to$ **$1$가지**
4단계: 최종 계산하기
1단계에서 나눈 4가지 경우에 대해, [1부의 경우의 수]와 [2부의 경우의 수]를 곱한 뒤 모두 더해줍니다.
답
$$100$$
확인해보기
질문: 2단계의 **경우 3 ($f(5)=3$)** 풀이에서, 만약 조건 (나)의 $f(x) \le x$라는 제한 조건이 아예 없었다면, $f(1)=1$이고 $f(5)=3$일 때 $f(1) \le f(2) \le f(3) \le f(4) \le f(5)$를 만족하는 경우의 수는 중복조합을 이용하여 어떻게 식을 세우고 계산해야 할까요? (스스로 식을 세워 계산해 보세요!)