의예과 3번

(3-1) 함수 $\displaystyle f:\{1,2,\cdots,n\}\to\{1,2,\cdots,n\}$이 공평한 함수가 되도록 $\displaystyle f(1)$부터 $\displaystyle f(n)$까지 값을 차례대로 정하자. $\displaystyle f(1)$의 값으로 가능한 것은 $\displaystyle 1$부터 $\displaystyle n$까지 $\displaystyle n$가지 경우가 있다. $\displaystyle f(1)$의 값을 정한 후에, $\displaystyle f(2)$의 값은, 시행 후 $\displaystyle R_2$가 $\displaystyle R_1$과 겹치지 않아야 하므로 $\displaystyle n-1$가지 경우가 있다. 같은 방법으로 $\displaystyle f(3)$의 값은, 시행 후 $\displaystyle R_3$가 $\displaystyle R_1$ 또는 $\displaystyle R_2$와 겹치지 않아야 하므로, $\displaystyle n-2$가지 경우가 있고, $\displaystyle \cdots$, $\displaystyle f(n)$의 값은 시행 후 $\displaystyle R_n$이 $\displaystyle R_1,R_2,\ldots,R_{n-1}$과 겹치지 않아야 하므로 $\displaystyle 1$가지 경우가 있다.

따라서 곱의 법칙에 의하여 공평한 함수 $\displaystyle f$의 개수는 $\displaystyle n!$이다.

(3-2) (a) 함수 $\displaystyle g$로 시행을 하여 동전을 옮기면, 함수 $\displaystyle f$로 시행을 하여 동전을 옮긴 후 시계 방향으로 $\displaystyle 1$만큼씩 더 옮긴 것과 같다. 동전은 모두 다른 꼭짓점 위로 옮겨지므로 $\displaystyle g$는 공평한 함수이다.

(3-2) (b) 치역이 $\displaystyle \{a,b\}$인 공평한 함수가 존재하면, (3-2) (a)에 의하여 치역이 $\displaystyle \{a-b+9,9\}$인 공평한 함수가 존재한다. 이때, 치역의 두 원소의 차는 변화가 없으므로 $\displaystyle b=9$이고, $\displaystyle 9-a\ge5$, 즉, $\displaystyle a=1,2,3,4$인 경우만 고려하면 된다.정9각형 위에 있는 9개의 동전 중 일부는 시계 방향으로 9만큼 옮기고, 나머지는 시계 방향으로 $\displaystyle a$만큼 옮긴다. 9만큼 옮기면 원래 있던 꼭짓점으로 돌아오므로, 움직이지 않는 것으로 간주할 수 있다. 시행을 할 때, 옮기지 않는 동전과 $\displaystyle a$만큼 옮기는 동전이 각각 적어도 하나씩 존재하므로, 정9각형 위에는 $\displaystyle R$은 옮기지 않고, $\displaystyle R^{\prime}$은 시계 방향으로 $\displaystyle a$만큼 옮기는 시계 방향으로 연속하여 위치한 두 동전 $\displaystyle R,R^{\prime}$이 존재한다.정$\displaystyle n$각형을 적당히 회전하여 $\displaystyle R=R_9$, $\displaystyle R^{\prime}=R_1$, 즉, $\displaystyle f(9)=9$, $\displaystyle f(1)=a$라고 가정할 수 있다. 이때 시행 후 동전 $\displaystyle R_9$는 $\displaystyle P_9$ 위에 그대로 남아있고, $\displaystyle R_1$은 $\displaystyle P_{1+a}$로 이동한다. 시행 후 동전의 위치가 겹치지 않으므로 원래 $\displaystyle P_{1+a}$ 위에 있던 동전 $\displaystyle R_{1+a}$는 이동해야 한다. 따라서 $\displaystyle f(1+a)=a$이고, $\displaystyle R_{1+a}$는 $\displaystyle P_{1+2a}$로 이동한다. 그러면 $\displaystyle P_{1+2a}$ 위에 있던 동전 $\displaystyle R_{1+2a}$도 이동해야 하고, $\displaystyle f(1+2a)=a$이다. 이와 같은 방법으로 시행 후 동전의 위치를 보면 다음과 같다.$\displaystyle a=1$인 경우, $\displaystyle R_1$은 $\displaystyle P_2$, $\displaystyle R_2$는 $\displaystyle P_3$, $\displaystyle \cdots$, $\displaystyle R_8$은 $\displaystyle P_9$로 이동한다.$\displaystyle a=2$인 경우, $\displaystyle R_1$은 $\displaystyle P_3$로, $\displaystyle R_3$는 $\displaystyle P_5$로, $\displaystyle R_5$는 $\displaystyle P_7$로, $\displaystyle R_7$은 $\displaystyle P_9$로 이동한다.$\displaystyle a=4$인 경우, $\displaystyle R_1$은 $\displaystyle P_5$로, $\displaystyle R_5$는 $\displaystyle P_9$로 이동한다.위의 세 가지 경우에는 $\displaystyle P_9$ 위에 적어도 두 개의 동전이 위치하게 되어 공평한 함수가 될 수 없다. 따라서, $\displaystyle a=1,2,4$인 공평한 함수는 존재하지 않는다.

$\displaystyle a=3$인 경우에는,$\displaystyle f(k)=\begin{cases}3&k=1,4,7\\9&k=2,3,5,6,8,9\end{cases}$로 정의하면 공평한 함수가 된다. 이때 $\displaystyle b-a$의 값은 $\displaystyle 6$이다.따라서 $\displaystyle 5$ 이상의 자연수 중 $\displaystyle b-a$의 값으로 가능한 것은 $\displaystyle 6$뿐이다.

(3-3) 귀류법으로 공평한 일대일대응이 존재하지 않음을 보이자.공평한 일대일대응 $\displaystyle f$가 존재한다고 가정하자.각각의 $\displaystyle i$에 대하여, 시행 후 동전 $\displaystyle R_i$의 위치를 $\displaystyle P_k$라 하면, $\displaystyle i+f(i)=k$이거나 $\displaystyle i+f(i)=n+k$이다. 즉, $\displaystyle i+f(i)-k$는 $\displaystyle n$의 배수이다. 따라서 모든 동전 $\displaystyle R_i$에 대하여 $\displaystyle (i+f(i)-k)$의 값을 모두 더하면 그 값은 $\displaystyle n$의 배수가 된다.

또한 공평한 함수의 정의에 의하여 시행 후에는 각각의 $\displaystyle 1\le k\le n$에 대하여 $\displaystyle P_k$에 정확히 하나의 동전이 놓인다. 따라서 모든 동전 $\displaystyle R_i$에 대하여 $\displaystyle (i+f(i)-k)$의 값을 더한 것은 $\displaystyle \sum_{i=1}^n(i+f(i))-\sum_{k=1}^n k$와 같고, $\displaystyle f$는 일대일 대응이므로 제시문(나)에 의하여$\displaystyle \sum_{i=1}^n(i+f(i))-\sum_{k=1}^n k=\sum_{i=1}^n f(i)=1+2+\cdots+n=\frac{n(n+1)}{2}$이다.

그런데 $\displaystyle n$이 짝수이므로 $\displaystyle \frac{n(n+1)}{2}=\frac{n}{2}\cdot n+\frac{n}{2}$은 $\displaystyle n$으로 나눈 나머지가 $\displaystyle \frac{n}{2}$으로 $\displaystyle n$의 배수가 될 수 없다. 이는 모순이다. 따라서 공평한 일대일대응은 존재하지 않는다.