의예과 3번

(3-1) $\displaystyle 5$ 이하의 자연수 $\displaystyle n$에 대하여 $\displaystyle a+b=4n$인 $\displaystyle S$의 원소 $\displaystyle a,b\ (a<b)$의 순서쌍 $\displaystyle (a,b)$의 개수는 $\displaystyle n-1$이고 $\displaystyle a+b=4n-2$인 $\displaystyle S$의 원소 $\displaystyle a,b\ (a<b)$의 순서쌍 $\displaystyle (a,b)$의 개수는 $\displaystyle n-1$이므로$\displaystyle \sigma(S)=\sum_{i=1}^5 2(i-1)=20$이다.

(3-2)\n(a) $\displaystyle a+b=x$, $\displaystyle a+b=y$인 $\displaystyle S$의 원소 $\displaystyle a,b\ (a<b)$의 순서쌍 $\displaystyle (a,b)$의 개수는 각각 최대 $\displaystyle n$, $\displaystyle n-1$이므로 조건을 만족하는 순서쌍의 개수는 $\displaystyle 2n-1$ 이하이다.

한편 $\displaystyle S=\{1,2,\cdots,2n+1\}$일 때 조건을 만족하는 순서쌍 $\displaystyle (a,b)$의 개수는 정확히 $\displaystyle 2n-1$이므로 답은 $\displaystyle 2n-1$이다.

(b) $\displaystyle S$의 원소를 $\displaystyle a_1,a_2,\cdots,a_{2n},a_{2n+1}\ (a_1<a_2<\cdots<a_{2n}<a_{2n+1})$이라 하고 $\displaystyle n$ 이하의 자연수 $\displaystyle k$에 대하여 $\displaystyle S_k=\{a_1,a_2,\cdots,a_{2k+1}\}$이라 하자. (a)에 의하여 $\displaystyle k\ge2$이면 $\displaystyle \sigma(S_k)-\sigma(S_{k-1})\le2k-1$임을 알 수 있다. 따라서$\displaystyle \begin{aligned}\sigma(S_n)&=(\sigma(S_n)-\sigma(S_{n-1}))+(\sigma(S_{n-1})-\sigma(S_{n-2}))+\cdots+(\sigma(S_2)-\sigma(S_1))+\sigma(S_1)\\&\le(2n-1)+(2n-3)+\cdots+3+1=n^2\end{aligned}$이다.

한편, $\displaystyle S=\{1,2,\cdots,2n+1\}$이면 $\displaystyle \sigma(S)=n^2$이므로 최댓값 $\displaystyle M$은 $\displaystyle n^2$이다.

(c) $\displaystyle S=\{1,2,\cdots,2n+1\}$이면 문제의 조건을 만족한다. 이제 $\displaystyle n\ge2$에 대하여 $\displaystyle S$는 $\displaystyle \{1,2,\cdots,2n+1\}$뿐임을 수학적 귀납법을 이용하여 증명하자.$\displaystyle n=2$인 경우를 보자. $\displaystyle S=\{1,a_2,a_3,a_4,a_5\}\ (1<a_2<\cdots<a_5)$라 하자. $\displaystyle \sigma(S)=2^2=4$이므로 $\displaystyle (a,b,c)$가 $\displaystyle (1,a_2,a_3)$, $\displaystyle (1,a_4,a_5)$, $\displaystyle (a_2,a_3,a_5)$인 경우 $\displaystyle a+b=c$를 만족해야 한다. 즉, $\displaystyle a_3=a_2+1$, $\displaystyle a_4=2a_2$, $\displaystyle a_5=2a_2+1$이다. 또한 $\displaystyle a_4$는 $\displaystyle 1+a_2$, $\displaystyle 1+a_3$, $\displaystyle a_2+a_3$ 중 하나와 같아야 하는데, $\displaystyle 1+a_2<2a_2(=a_4)<a_2+a_3$이므로 $\displaystyle a_4=1+a_3$이고 $\displaystyle a_2=2$, $\displaystyle a_3=3$, $\displaystyle a_4=4$, $\displaystyle a_5=5$이다. 즉, $\displaystyle S=\{1,2,3,4,5\}$이다.

$\displaystyle n>2$라 하자. $\displaystyle n-1$인 경우에는 조건을 만족하는 집합이 $\displaystyle \{1,2,\cdots,2(n-1)+1\}$뿐이라 가정하고, $\displaystyle n$인 경우를 증명하자. $\displaystyle S$의 원소 중 가장 큰 것과 두 번째로 큰 것을 각각 $\displaystyle x$, $\displaystyle y$라 하자.$\displaystyle S^{\prime}=S-\{x,y\}$라 하면 (a)에 의하여 $\displaystyle 2n-1\ge\sigma(S)-\sigma(S^{\prime})=n^2-\sigma(S^{\prime})$이므로 $\displaystyle \sigma(S^{\prime})\ge(n-1)^2$이다. (b)에 의하여 $\displaystyle \sigma(S^{\prime})\le(n-1)^2$이므로 $\displaystyle \sigma(S^{\prime})=(n-1)^2$이다.$\displaystyle 1\in S^{\prime}$이고 $\displaystyle \sigma(S^{\prime})=(n-1)^2$이므로 가정에 의하여 $\displaystyle S^{\prime}=\{1,2,\cdots,2(n-1)+1\}$이고 $\displaystyle S=\{1,2,\cdots,2(n-1)+1,x,y\}$이다. 그런데 $\displaystyle a+b\in\{x,y\}$인 $\displaystyle (a,b)$의 개수가 정확히 $\displaystyle 2n-1$이어야 하므로 $\displaystyle x=2n$, $\displaystyle y=2n+1$이다.Correction. 앞에서 $\displaystyle x$를 가장 큰 원소, $\displaystyle y$를 두 번째로 큰 원소로 정했으므로 $\displaystyle x=2n+1$, $\displaystyle y=2n$이다. 집합 자체와 최종 답에는 영향이 없다. 원칙에 따라 원문 표기를 그대로 실었다.즉, $\displaystyle S=\{1,2,\cdots,2n+1\}$이다. 따라서 수학적 귀납법에 의하여 $\displaystyle 2$ 이상인 모든 자연수 $\displaystyle n$에 대하여 $\displaystyle S=\{1,2,\cdots,2n+1\}$이다.

(3-3) $\displaystyle S$의 원소를 크기순으로 $\displaystyle a_1<a_2<\cdots<a_{202}$라 하고 $\displaystyle S^{\prime}=S-\{a_{202}\}$라 하자.$\displaystyle n(S^{\prime})=201$이므로 (3-2)(b)에 의하여 $\displaystyle \sigma(S^{\prime})\le100^2$이다.한편 $\displaystyle 100\ge\sigma(S)-\sigma(S^{\prime})=(100^2+100)-\sigma(S^{\prime})\ge(100^2+100)-100^2=100$이므로 $\displaystyle 100=\sigma(S)-\sigma(S^{\prime})$이고 $\displaystyle \sigma(S^{\prime})=100^2$이어야 한다.$\displaystyle 100=\sigma(S)-\sigma(S^{\prime})$에서 $\displaystyle a+b=a_{202}$를 만족하는 $\displaystyle S$의 원소 $\displaystyle a,b\ (a<b)$의 순서쌍 $\displaystyle (a,b)$의 개수가 정확히 $\displaystyle 100$개라는 것을 알 수 있다. 또한, $\displaystyle \sigma(S^{\prime})=100^2$이므로 (3-2)(c)와 같은 방법으로 $\displaystyle S^{\prime}$은 반드시 $\displaystyle \{d,2d,\cdots,201d\}$꼴, 즉 $\displaystyle a_k=dk\ (k=1,2,\cdots,201)$인 자연수 $\displaystyle d$가 존재함을 알 수 있다. 한편 $\displaystyle a+b=a_{202}$를 만족하는 순서쌍 $\displaystyle (a,b)$의 개수가 정확히 $\displaystyle 100$개이기 위해서는 $\displaystyle a_{202}=202d$ 또는 $\displaystyle 203d$이어야 한다. 그러므로 $\displaystyle S=\{d,2d,\cdots,201d,202d\}$ 또는 $\displaystyle \{d,2d,\cdots,201d,203d\}$꼴이다.

전자의 경우 가능한 $\displaystyle S$의 개수는 $\displaystyle 10$, 후자의 경우 가능한 $\displaystyle S$의 개수는 $\displaystyle 9$이므로 가능한 $\displaystyle S$의 개수는 총 $\displaystyle 19$이다.