30. 집합 $X=\{x \mid x \text{는 } 10 \text{ 이하의 자연수}\}$에 대하여 다음 조건을 만족시키는 함수 $f : X \to X$의 개수를 구하시오. [4점]
(가) 9 이하의 모든 자연수 $x$에 대하여 $f(x) \le f(x+1)$이다.
(나) $1 \le x \le 5$일 때 $f(x) \le x$이고,
$6 \le x \le 10$일 때 $f(x) \ge x$이다.
(다) $f(6) = f(5) + 6$
이 문항은 수형도(Tree Diagram)를 활용한 체계적인 경우의 수 구하기를 기반으로 합니다. 단순히 중복조합 공식을 적용하는 것을 넘어, 치역과 정의역의 부등식 조건($f(x) \le x$ 등)에 의해 수형도의 가지가 어떻게 잘려나가는지(Pruning)를 직접 추적하여 논리적으로 경우의 수를 셀 수 있는지 평가합니다. 또한 함수 조건의 구조적 대칭성을 파악하여 연산 과정을 단축하는 고차원적인 추론 능력을 요구합니다.
문제의 핵심 연결 고리인 $x=5$와 $x=6$에서의 함수값을 먼저 찾아야 합니다.
조건 (나)에 의해 $f(5) \le 5$ 이고, $f(6) \ge 6$ 입니다.
조건 (다)에 의해 $f(6) = f(5) + 6$ 입니다.
| $f(5)$ | $f(6)$ | 조건 만족 여부 ($6 \le f(6) \le 10$) |
|---|---|---|
| 1 | 7 | 가능 ($7 \ge 6$ 이고 $7 \le 10$) |
| 2 | 8 | 가능 ($8 \ge 6$ 이고 $8 \le 10$) |
| 3 | 9 | 가능 ($9 \ge 6$ 이고 $9 \le 10$) |
| 4 | 10 | 가능 ($10 \ge 6$ 이고 $10 \le 10$) |
| 5 | 11 | 불가능 (10 초과) |
따라서 가능한 순서쌍 $(f(5), f(6))$은 $(1, 7), (2, 8), (3, 9), (4, 10)$ 총 4가지 경우입니다.
구간 $1 \le x \le 5$에서 지켜야 할 조건은 두 가지입니다.
1) $f(1) \le f(2) \le f(3) \le f(4) \le f(5)$ (단조증가)
2) $f(x) \le x$ (함수값의 상한선 제한)
복잡한 공식을 쓰기보다, 수형도(나뭇가지 모양 그림)를 그려서 각 단계마다 뻗어나갈 수 있는 경우를 직접 찾아보는 것이 가장 쉽고 정확합니다.
후반부 구간($6 \le x \le 10$)의 조건은 $f(x) \ge x$ 이며 역시 단조증가합니다.
이 조건은 부등식의 방향과 숫자만 반대일 뿐, 구조적으로 Step 2의 수형도와 완전히 똑같은 형태(대칭)를 가집니다. 즉, 거꾸로 수형도를 그린다고 생각하면 됩니다.
따라서 대칭성에 의해, $f(6)$의 값에 따른 후반부 경우의 수는 전반부 수형도 결과를 뒤집어서 적용할 수 있습니다.
- $f(6) = 7$ 일 때 : (전반부 끝값이 4일 때와 동일) $\to$ 14개
- $f(6) = 8$ 일 때 : (전반부 끝값이 3일 때와 동일) $\to$ 9개
- $f(6) = 9$ 일 때 : (전반부 끝값이 2일 때와 동일) $\to$ 4개
- $f(6) = 10$ 일 때 : (전반부 끝값이 1일 때와 동일) $\to$ 1개
이제 Step 1에서 찾은 4가지 경우에 대해 전반부와 후반부의 경우의 수를 곱하여 더해줍니다.
따라서 정답은 ③번 입니다.
경우의 수를 빠짐없이 중복 없이 세기 위해, 나뭇가지가 뻗어나가는 모양으로 모든 가능한 경우를 체계적으로 나열하는 기초적이면서도 가장 강력한 수학적 도구입니다.
전반부 조건 $f(x) \le x$와 후반부 조건 $f(x) \ge x$가 정의역과 공역의 반전에 의해 수형도의 모양이 완벽히 일치(동형)함을 파악하는 기법입니다.
학생들이 (가)의 단조증가 조건만을 보고 무의식적으로 중복조합($_nH_r$) 공식을 적용하려 합니다. 예를 들어 $f(5)=3$일 때, $f(1) \sim f(4)$를 $1, 2, 3$ 중에서 고르는 $_3H_4 = 15$개로 계산하는 심각한 오류를 범합니다.
$_3H_4$ 로 계산한 15개의 경우 중에는, 모두 3을 선택하는 경우인 $(3, 3, 3, 3, 3)$도 포함되어 있습니다.
이 경우 $f(1) = 3$ 이 됩니다. 하지만 조건 (나)에 의해 $f(1) \le 1$ 이어야 하므로 명백한 모순이 발생합니다.
$f(x) \le x$ 조건은 수형도에서 특정 숫자를 넘지 못하게 가지를 미리 잘라내는(Pruning) 역할을 합니다. 따라서 공식이 아닌 직접 수형도를 그리거나 분기를 추적해야만 정확한 답을 얻을 수 있습니다.
이 문제처럼 "증가해야 하지만(우측 이동), 특정 경계를 넘을 수 없는(상한선)" 제한을 가진 수형도는 수학에서 유명한 '카탈란 수'의 원리를 따릅니다. 심화 수학 원리 연계
이 구조는 교과서에 나오는 '대각선을 넘지 못하는 최단 경로' 문제와 완벽히 같습니다. 수형도의 각 분기(가지)는 격자점에서의 이동(위로 가거나 오른쪽으로 가거나)과 1:1로 대응됩니다.
수형도의 장점은 눈에 보이지 않는 공식을 시각적인 나뭇가지 형태로 모두 풀어내어, 어떤 가지가 부등식 조건에 의해 잘려나갔는지 직관적으로 확인할 수 있게 해준다는 점입니다.