2019학년도 07월 나형 28번

28. 집합 $X=\{1,2,3,4,5,6,7,8\}$$X=\big\{1,~2,~3,~4,~5,~6,~7,~8\big\}$에 대하여 일대일 대응인 함수 $f:X\to X$$f:X\rightarrow X$가 다음 조건을 만족시킬 때, 함수 $f$$f$의 개수를 구하시오.

(가) $p$$p$가 소수일 때, $f(p)\le p$$f(p)\le p$이다.

(나) $a<b$$a<b$이고 $a$$a$가 $b$$b$의 약수이면 $f(a)<f(b)$$f(a)<f(b)$이다.

---

i. 정리

• $f(2)\le 2,f(3)\le 3,f(5)\le 5,f(7)\le 7$$f(2)\le 2,~f(3)\le 3,~f(5)\le 5,~f(7)\le 7$

• $8$$8$의 약수 : $1,2,4,8$$1,~2,~4,~8$

  $f(1)<f(2)<f(4)<f(8)$$f(1)<f(2)<f(4)<f(8)$

• $6$$6$의 약수 : $1,2,3,6$$1,~2,~3,~6$

  $f(1)<f(2)<f(3)<f(6)$$f(1)<f(2)<f(3)<f(6)$

ii. 정리

• $f(1)=1,f(2)=2,f(3)=3$$f(1)=1,~f(2)=2,~f(3)=3$일 수 밖에 없다.

• 대충 수형도로 표시하고 생각하자.

  

  $\begin{array}{c}f(5)=\{\begin{array}{l}4\\ \\ 5\end{array},f(7)=\{\begin{array}{l}4\\ \\ 5\\ \\ 6\\ \\ 7\end{array}\end{array}$$f(5)=\begin{cases} 4\\ \\ 5\end{cases} ,~\quad f(7)=\begin{cases} 4\\ \\ 5 \\ \\ 6\\ \\ 7\end{cases} \quad$이 가능하다.

• $f(5)=4$$f(5)=4$이고, $f(7)=5$$f(7)=5$일 때를 생각해보자.

  

  $f(4)<f(8)$$f(4)<f(8)$만 만족시키면 되네?

  ${}_3{C}_2\times 1=3$${}_3C_2\times 1=3$

• $f(5)=4,f(7)=6$$f(5)=4,~f(7)=6$일 때를 볼까?

  

  마찬가지네?

  $3$$3$

• $f(5)=4,f(7)=7$$f(5)=4,~f(7)=7$이어도?

  $3$$3$

$f(5)=4$$f(5)=4$일 때, $3\times 3=9$$3\times 3=9$

 

• $f(5)=5,f(7)=4$$f(5)=5,~f(7)=4$일 때를 생각하자.

  

  어? 똑같다. $f(4)<f(8)$$f(4)<f(8)$만 만족시키면 된다.

  그럼 나머지도 마찬가지겠다?

$f(5)=5$$f(5)=5$일 때, $3\times 3=9$$3\times 3=9$

 

$\therefore 9\times 2=18$$\therefore~ 9\times 2=18$