어떤 문제인가
이 문제는 주어진 두 가지 조건을 만족하는 함수 $f: X \to X$의 개수를 구하는 문제입니다. 문제를 해결하기 위해 우리가 꼭 알아야 할 핵심 개념은 다음과 같습니다.
- 합성함수의 성질과 경우 분류: $f(f(1)) = 4$라는 조건에서 $f(1)$의 값에 따라 함수 전체의 모습이 결정되므로, $f(1)$이 될 수 있는 값을 기준으로 경우를 나누어 생각합니다.
- **중복조합 ($_nH_r$)**: 조건 (나)의 $f(1) \le f(3) \le f(5)$처럼 크기가 정해져 있고 등호가 포함된 관계를 만족하는 함숫값을 정할 때는 중복조합을 사용합니다.
- 곱의 법칙: 각 조건에 영향을 받지 않는 나머지 원소들의 함숫값을 결정하는 경우의 수를 곱해줍니다.
단계별 풀이
1단계: $f(1)$의 값에 따라 경우 분류하기
조건 (가)에서 $f(f(1)) = 4$라고 했습니다.
여기서 $f(1) = a$ ($a \in X$)라고 하면, 이 식은 $f(a) = 4$가 됩니다.
정의역과 공역이 $X = \{1, 2, 3, 4, 5\}$이므로, $f(1)$이 될 수 있는 값은 $1, 2, 3, 4, 5$ 중 하나입니다. 각각의 경우를 살펴봅시다.
- **$f(1) = 1$인 경우**:
$f(f(1)) = f(1) = 1$이 되어 조건 (가)의 $f(f(1)) = 4$에 모순됩니다. 따라서 이 경우는 불가능합니다.
- **$f(1) = 5$인 경우**:
$f(5) = 4$가 됩니다. 그런데 조건 (나)에 의해 $f(1) \le f(3) \le f(5)$이어야 하므로 $5 \le f(3) \le 4$가 되어 모순이 생깁니다. 따라서 이 경우도 불가능합니다.
결국 가능한 $f(1)$의 값은 **$2, 3, 4$** 세 가지뿐입니다. 이제 이 세 가지 경우를 나누어 계산해 봅시다.
2단계: $f(1) = 2$인 경우
- 조건 (가) 분석: $f(1) = 2$이므로 $f(2) = 4$로 고정됩니다. (경우의 수: $1$가지)
- 조건 (나) 분석: $2 \le f(3) \le f(5)$이어야 합니다.
$f(3)$과 $f(5)$가 가질 수 있는 값은 $\{2, 3, 4, 5\}$의 4개 원소 중 중복을 허용하여 2개를 선택하는 중복조합과 같습니다.
$$\text{경우의 수} = _4H_2 = \binom{4+2-1}{2} = \binom{5}{2} = 10\text{가지}$$
- 나머지 원소 처리: 아직 함숫값이 정해지지 않은 원소는 $4$입니다. $f(4)$는 공역 $X$의 5개 원소 중 아무거나 가질 수 있습니다. (경우의 수: $5$가지)
따라서 $f(1) = 2$일 때의 함수 개수는:
$$1 \times 10 \times 5 = 50\text{가지}$$
3단계: $f(1) = 3$인 경우
- 조건 (가) 분석: $f(1) = 3$이므로 $f(3) = 4$로 고정됩니다. (경우의 수: $1$가지)
- 조건 (나) 분석: $3 \le f(3) \le f(5)$에 $f(3) = 4$를 대입하면, $3 \le 4 \le f(5)$가 됩니다.
즉, $f(5)$가 가질 수 있는 값은 $4$ 이상이어야 하므로 $\{4, 5\}$ 중 하나입니다. (경우의 수: $2$가지)
- 나머지 원소 처리: 아직 함숫값이 정해지지 않은 원소는 $2$와 $4$입니다. $f(2)$와 $f(4)$는 각각 공역 $X$의 5개 원소 중 아무거나 가질 수 있습니다. (경우의 수: $5 \times 5 = 25$가지)
따라서 $f(1) = 3$일 때의 함수 개수는:
$$1 \times 2 \times 5 \times 5 = 50\text{가지}$$
4단계: $f(1) = 4$인 경우
- 조건 (가) 분석: $f(1) = 4$이므로 $f(4) = 4$로 고정됩니다. (경우의 수: $1$가지)
- 조건 (나) 분석: $4 \le f(3) \le f(5)$이어야 합니다.
$f(3)$과 $f(5)$가 가질 수 있는 값은 $\{4, 5\}$의 2개 원소 중 중복을 허용하여 2개를 선택하는 중복조합과 같습니다.
$$\text{경우의 수} = _2H_2 = \binom{2+2-1}{2} = \binom{3}{2} = 3\text{가지}$$
- 나머지 원소 처리: 아직 함숫값이 정해지지 않은 원소는 $2$입니다. $f(2)$는 공역 $X$의 5개 원소 중 아무거나 가질 수 있습니다. (경우의 수: $5$가지)
따라서 $f(1) = 4$일 때의 함수 개수는:
$$1 \times 3 \times 5 = 15\text{가지}$$
5단계: 총 경우의 수 구하기
각 경우는 동시에 일어날 수 없으므로(합의 법칙), 구한 경우의 수들을 모두 더합니다.
$$\text{전체 함수의 개수} = 50 + 50 + 15 = 115$$
답
$$115$$
확인해보기
만약 조건 (나)가 등호가 없는 조건인 **$f(1) < f(3) < f(5)$**로 바뀐다면, $f(1) = 2$일 때 $f(3)$과 $f(5)$의 값을 정하는 경우의 수는 어떤 개념을 사용하여 구해야 할까요? (직접 경우의 수도 구해보세요!)