함수의 치역 범위와 대소 관계를 분석하여 중복조합으로 경우의 수를 구하는 문항
28. 집합 $X = \{1, 2, 3, 4, 5, 6\}$에 대하여 다음 조건을 만족시키는 함수 $f : X \rightarrow X$의 개수는? [4점]
(가) $f(1) \times f(6)$의 값이 6의 약수이다.
(나) $2f(1) \le f(2) \le f(3) \le f(4) \le f(5) \le 2f(6)$
이 문항은 주어진 함수의 조건들을 분석하여 가능한 함숫값의 순서쌍을 분류하고, 부등식으로 주어진 조건과 함수의 정의(공역의 제한)를 동시에 고려하여 중복조합을 활용해 경우의 수를 구하는 논리적 추론 능력을 평가합니다.
조건 (가)에 의해 $f(1) \times f(6)$ 은 6의 약수, 즉 1, 2, 3, 6 중 하나여야 합니다. 집합 $X$의 원소로 이루어진 가능한 순서쌍 $(f(1), f(6))$을 구하면 다음과 같습니다.
조건 (나)에 포함된 양 끝의 부등식을 살펴보면 $2f(1) \le 2f(6)$ 이어야 하므로, 결과적으로 $f(1) \le f(6)$ 을 만족해야 합니다. 따라서 Step 1에서 구한 순서쌍 중 이 조건을 만족하는 것만 남기면 다음 5가지 Case로 압축됩니다.
위의 Case들은 동시에 일어날 수 없는 서로 배반사건이므로 합의 법칙을 적용하여 모두 더해줍니다.
크기가 정해져 있는 부등식 $\le$ 조건을 만족하며 여러 개의 함숫값을 공역에서 선택해야 할 때 사용하는 핵심 도구입니다.
분할된 Case들이 서로 교집합이 없는 배반사건일 경우, 전체 경우의 수는 각각의 경우의 수를 더하여 구합니다.
함수 $f : X \rightarrow X$ 라는 기호의 의미로부터, 도출된 함숫값이 반드시 집합 $X$ 내부에 존재해야 한다는 제한 조건을 놓치지 않아야 합니다.
수험생들이 Case 4에서 가장 많이 범하는 실수는 $2f(6) = 12$ 라는 결과만을 보고 부등식을 $2 \le f(2) \le f(3) \le f(4) \le f(5) \le 12$ 로 받아들여, 치역을 $\{2, 3, \dots, 12\}$ 총 11개의 숫자로 착각하고 중복조합 ${}_{11}\mathrm{H}_{4}$ 를 계산하는 것입니다.
함수의 정의에 의해 $f : X \rightarrow Y$ 일 때, 임의의 $x \in X$ 에 대하여 $f(x) \in Y$ 이어야 합니다.
본 문항에서는 $Y = X = \{1, 2, 3, 4, 5, 6\}$ 이 주어졌습니다.
따라서 수학적으로 요구되는 완벽한 조건은 $f(x) \le 2f(6)$ 과 $f(x) \le \max(X)$ 의 교집합입니다.
즉, $f(x) \le \min(2f(6), 6)$ 이 항상 성립해야 하므로, 아무리 $2f(6)$ 이 12로 크더라도 실제 한계치는 6으로 제한됩니다.
서로 다른 $n$개의 원소 중에서 중복을 허락하여 $r$개를 택하는 방법의 수를 구하는 논리는 칸막이 모델로 증명할 수 있습니다.
선택해야 할 $r$개의 대상을 동일한 모양의 별($\star$)이라고 합시다. 이 별들을 $n$개의 서로 다른 종류로 분류하기 위해서는 그룹을 나누는 칸막이($|$)가 $(n-1)$개 필요합니다.
예: $n=3$, $r=4$ 일 때 $\Rightarrow$ $\star \star | \star | \star$ (1번 2개, 2번 1개, 3번 1개)
결과적으로 별 $r$개와 칸막이 $(n-1)$개를 일렬로 나열하는 모든 경우의 수를 구하는 것과 완벽히 동치입니다.
총 물건의 개수는 $r + (n - 1)$ 개이며, 이 중 별이 들어갈 $r$개의 위치를 선택하는 조합의 수와 같으므로 다음과 같이 유도됩니다.
$$ {}_{n}\mathrm{H}_{r} = \frac{(n+r-1)!}{r!(n-1)!} = {}_{n+r-1}\mathrm{C}_{r} $$
이 문제에서 $f(2) \le f(3) \le f(4) \le f(5)$ 조건을 만족하도록 치역에서 값을 선택하는 과정은 값의 크기에 따라 자동으로 순서가 정해지므로 뽑기만 하면 되는 조합의 성질과 완전히 일치합니다.
가로축은 함숫값(1~12)을 나타냅니다. $f(2) \sim f(5)$가 가질 수 있는 값의 범위를 바(Bar)로 표시했습니다. 특히 Case 4에서 공역의 제한선(x=6)에 의해 7~12 구간이 잘려나가는 것을 확인하세요.
각 Case(x축, Red)에 대하여, 선택 대상이 되는 함수 4개(y축 두께, Green)가 선택 가능한 함숫값의 범위(z축, Blue)를 3차원 박스로 나타냅니다.
블록의 z축 길이가 길수록 중복조합에서 선택 가능한 원소 $n$이 큼을 의미합니다. 붉은색 투명 박스는 허용되지 않는 잉여 공간입니다.