의예과 3번

(3-1) $\displaystyle n=2$이면 $\displaystyle x_n=x_2$이고 $\displaystyle x_1x_2<0$이므로 $\displaystyle x_1$과 $\displaystyle x_n$의 부호는 서로 다르다.$\displaystyle n=3$이면 $\displaystyle x_n=x_3$이다. $\displaystyle x_1x_2<0$이므로 $\displaystyle x_1$과 $\displaystyle x_2$는 부호가 다르다. 또한 $\displaystyle x_2x_3<0$이므로 $\displaystyle x_2$와 $\displaystyle x_3$는 부호가 다르다. 따라서 $\displaystyle x_1$과 $\displaystyle x_3$는 부호가 서로 같다.$\displaystyle k\ge4$에 대하여 $\displaystyle n=k-1$일 때 성립한다고 가정하고, $\displaystyle n=k$일 때 성립함을 보이자.$\displaystyle k$가 짝수이면 $\displaystyle k-1$은 홀수이다. 따라서 $\displaystyle x_{k-1}$은 $\displaystyle x_1$과 부호가 같다. 또한 $\displaystyle x_{k-1}x_k<0$이므로 $\displaystyle x_{k-1}$과 $\displaystyle x_k$는 부호가 다르다. 즉, $\displaystyle x_1$과 $\displaystyle x_k$는 부호가 서로 다르다.$\displaystyle k$가 홀수이면 $\displaystyle k-1$은 짝수이다. 따라서 $\displaystyle x_1$과 $\displaystyle x_{k-1}$은 부호가 다르고, $\displaystyle x_{k-1}x_k<0$이므로 $\displaystyle x_{k-1}$과 $\displaystyle x_k$는 부호가 다르므로 $\displaystyle x_1$과 $\displaystyle x_k$는 부호가 서로 같다.따라서 수학적 귀납법에 의하여 $\displaystyle 2$ 이상인 모든 자연수 $\displaystyle n$에 대하여 명제가 성립한다.

(3-2) (a) 귀류법으로 증명하자. $\displaystyle N=0$인 재배열 $\displaystyle a_1,a_2,\cdots,a_{99}$가 존재한다고 가정하자. 그러면 각각의 $\displaystyle i=1,2,\cdots,98$에 대하여 $\displaystyle b_ib_{i+1}<0$이다. (3-1)에 의하여 $\displaystyle b_1$과 $\displaystyle b_{99}$의 부호는 같고 $\displaystyle b_{99}b_1>0$이므로 $\displaystyle N=0$이라는 것에 모순이다. 따라서 $\displaystyle N\ge1$이다.

(b) $\displaystyle n$이 짝수일 때 $\displaystyle a_n$은 $\displaystyle 51$ 이상이고 $\displaystyle n$이 홀수일 때 $\displaystyle a_n$은 $\displaystyle 50$ 이하인 아래 재배열에 대하여 $\displaystyle N=1$임을 보이자.$\displaystyle a_1=50,\ k=1,2,\cdots,49$에 대하여 $\displaystyle a_{2k}=50+k,\ a_{2k+1}=k$ (*)

$\displaystyle k=1,\cdots,49$에 대하여 $\displaystyle b_{2k}=a_{2k+1}-a_{2k}\le50-51<0$, $\displaystyle b_{2k-1}=a_{2k}-a_{2k-1}\ge51-50>0$이고 $\displaystyle b_{99}=a_1-a_{99}=50-49>0$이다. 즉, $\displaystyle b_1,b_2,\cdots,b_{99}$에는 양수와 음수가 교대로 나온다. 따라서 $\displaystyle b_1b_2,b_2b_3,\cdots,b_{98}b_{99}$는 모두 음수이고 $\displaystyle b_{99}b_1$은 양수이다. 그러므로 이 재배열에서 $\displaystyle N=1$이다.

(3-3) $\displaystyle N=1$이므로 어떤 $\displaystyle j=1,2,\cdots,99$에 대하여 $\displaystyle b_jb_{j+1}>0$이고 (단, $\displaystyle b_{100}=b_1$) $\displaystyle j$가 아닌 $\displaystyle i$에 대하여 $\displaystyle b_ib_{i+1}<0$이다. 일반성을 잃지 않고 $\displaystyle j=99$, 즉, $\displaystyle b_{99}b_1>0$이고 $\displaystyle b_1b_2,b_2b_3,\cdots,b_{98}b_{99}<0$이라 하자. 또한 일반성을 잃지 않고 $\displaystyle b_{99}>0$이라 하자. 이때 $\displaystyle b_1>0$이다. $\displaystyle b_1b_2,b_2b_3,\cdots,b_{98}b_{99}<0$이므로 (3-1)에 의하여 $\displaystyle b_1,b_3,\cdots,b_{99}$는 모두 양수 $\displaystyle b_2,b_4,\cdots,b_{98}$은 모두 음수이다. 따라서 $\displaystyle |b_{2k-1}|=b_{2k-1}=a_{2k}-a_{2k-1}$, $\displaystyle |b_{2k}|=-b_{2k}=a_{2k}-a_{2k+1}$이다. 그러므로

$\displaystyle \begin{aligned}\sum_{i=1}^{99}|b_i|&=\sum_{k=1}^{50}|b_{2k-1}|+\sum_{k=1}^{49}|b_{2k}|\\&=(a_2-a_1)+(a_4-a_3)+\cdots+(a_{96}-a_{95})+(a_{98}-a_{97})+(a_1-a_{99})\\&\quad+(a_2-a_3)+(a_4-a_5)+\cdots+(a_{96}-a_{97})+(a_{98}-a_{99})\\&=2(a_2+a_4+\cdots+a_{98})-2(a_3+a_5+\cdots+a_{99})\end{aligned}$이다.

(a) $\displaystyle a_2+a_4+\cdots+a_{98}\le51+52+\cdots+99=49\cdot\frac{150}{2}=49\cdot75=3675$이고 $\displaystyle a_3+a_5+\cdots+a_{99}\ge1+2+\cdots+49=49\cdot\frac{50}{2}=1225$이므로 $\displaystyle \sum_{i=1}^{99}|b_i|\le2\cdot(3675-1225)=4900$이다.

또한 (3-2)(b)에서 구한 재배열(*)에서 $\displaystyle \sum_{i=1}^{99}|b_i|=4900$이므로 $\displaystyle M=4900$이다.

이러한 재배열의 개수는 $\displaystyle (49!)^2$이다. 그런데 $\displaystyle j$는 $\displaystyle 1,2,\cdots,99$ 모두 가능하고 $\displaystyle b_{99}$가 음수인 경우도 있으므로 재배열의 총 개수는 $\displaystyle 99\cdot2\cdot(49!)^2=198\cdot(49!)^2$이다.