자연계열 2번

[문제 2-1](1) 함숫값 $\displaystyle f(1),f(2),\cdots,f(9)$을 차례로 나열하면 $\displaystyle 4,2,3,3,2,4,4,3,1$이므로, $\displaystyle f$의 반복쌍은 $\displaystyle (2,3)$과 $\displaystyle (4,3)$뿐임을 관찰할 수 있다.

(2) $\displaystyle 1\le i\le6$일 때, $\displaystyle g(i)=f(i)$이고, $\displaystyle 7\le i\le n-2$일 때 $\displaystyle g(i)=4$이고,

$\displaystyle g(n-1)=f(8)$, $\displaystyle g(n)=f(9)$로 정의되는 함수 $\displaystyle g$는 주어진 조건을 만족한다.

[문제 2-2](1) $\displaystyle N_4$의 서로 다른 두 자연수 $\displaystyle s$와 $\displaystyle t$로 이루어진 모든 순서쌍 $\displaystyle (s,t)$가 반복쌍인 함수 $\displaystyle f$가 존재한다고 하자. 함숫값 $\displaystyle f(1),f(2),\cdots,f(m)$을 차례로 나열했을 때 $\displaystyle 1,2,3,4$가 각각 적어도 두 번 나타나야 한다. 편의상 $\displaystyle a_i=f(i)$라 적자. $\displaystyle a_1$이 함숫값의 나열에서 정확히 두 번 나타나면, $\displaystyle a_1$이 아닌 임의의 원소 $\displaystyle b$에 대하여, $\displaystyle (b,a_1)$이 반복쌍이 될 수 없으므로, $\displaystyle a_1$은 함숫값의 나열에서 세 번 이상 나타난다. $\displaystyle a_i\ne a_1$인 가장 작은 $\displaystyle i$를 고르자. $\displaystyle a_1,a_i$가 아닌 임의의 원소 $\displaystyle b$에 대하여, $\displaystyle (b,a_i)$가 반복쌍이려면, $\displaystyle a_i$는 함숫값의 나열에서 세 번 이상 나타나야 한다. 마찬가지로, $\displaystyle a_j\ne a_1,a_i$인 가장 작은 $\displaystyle j$를 고르자. $\displaystyle a_1,a_i,a_j$가 아닌 임의의 원소 $\displaystyle b$에 대하여, $\displaystyle (b,a_j)$가 반복쌍이려면 $\displaystyle a_j$이 함숫값의 나열에서 세 번 이상 나타난다. 즉 $\displaystyle m$은 11이상이어야 한다.

예를 들어 $\displaystyle g(1),g(2),\cdots,g(11)$을 차례로 나열한 것이 $\displaystyle 1,2,3,4,1,2,3,4,1,2,3$인 함수 $\displaystyle g:N_{11}\to N_4$에 대하여 $\displaystyle N_4$의 서로 다른 두 자연수 $\displaystyle s$와 $\displaystyle t$로 이루어진 모든 순서쌍 $\displaystyle (s,t)$가 $\displaystyle g$의 반복쌍이다. 따라서 $\displaystyle m$의 최솟값은 11이다.

(2) 귀류법으로 증명하자. 반복쌍의 집합이 $\displaystyle \{(1,2),(2,3),(3,4),(4,1)\}$인 함수 $\displaystyle f$가 존재한다고 가정하자. $\displaystyle f(1),f(2),\cdots,f(m)$을 차례로 나열한 것을 생각하자. $\displaystyle f(1),f(2),\cdots,f(k)$에서 반복쌍이 나타나는 가장 작은 $\displaystyle k$를 생각하자. 예를 들어 그때의 반복쌍을 $\displaystyle (1,2)$라 하자. 또한 $\displaystyle k$의 성질과 반복쌍의 집합의 성질에 의하여, $\displaystyle f(1),f(2),\cdots,f(k)$에서 반복쌍은 정확히 하나뿐이다.

한편 $\displaystyle (4,1)$이 반복쌍이므로, $\displaystyle f(k+1),f(k+2),\cdots,f(m)$에 1이 나타난다. 그러면 $\displaystyle (2,1)$이 $\displaystyle f$의 반복쌍이 되어 반복쌍이 $\displaystyle (1,2),(2,3),(3,4),(4,1)$뿐이라는 조건에 모순이다. $\displaystyle f(1),f(2),\cdots,f(k)$에서 나타나는 반복쌍이 $\displaystyle (2,3)$, $\displaystyle (3,4)$, $\displaystyle (4,1)$인 경우도 같은 방법으로 증명된다.

[문제 2-3]치역의 원소의 개수가 1인 경우의 수는 $\displaystyle n$이다. 치역의 원소의 개수가 2인 경우를 생각하자. 조건을 만족하려면 함숫값 $\displaystyle f(1),f(2),\cdots,f(n)$을 차례로 나열했을 때 숫자가 두 번 이하로 바뀌어야 한다. 숫자가 한 번 바뀌는 경우는 첫 번째 자리를 제외한 $\displaystyle (n-1)$개의 자리 중 숫자가 바뀔 한 자리를 고르는 경우를 살펴야 하고, 숫자가 두 번 바뀌는 경우는 $\displaystyle (n-1)$개의 자리 중 숫자가 바뀔 두 자리를 고르는 경우가 된다. 따라서, 다음이 성립한다.$\displaystyle \begin{aligned}a_n&=n+n(n-1)\times\left({}_{n-1}\mathrm{C}_1+{}_{n-1}\mathrm{C}_2\right)\\&=n+n(n-1)\left(n-1+\frac{(n-1)(n-2)}2\right)=n+\frac{n^2(n-1)^2}2\end{aligned}$

이로부터 $\displaystyle \frac{a_n}n=1+\frac{n(n-1)^2}2$이므로 $\displaystyle \frac{a_n}n>2025$을 계산하면, $\displaystyle n\ge17$이어야 한다. 따라서 구하는 $\displaystyle n$의 최솟값은 17이다.