의예과 3번

(3-1) $\displaystyle \{1,2,3\}$은 흩어진 집합이고 $\displaystyle \{1,2,3,4\}$는 $\displaystyle 1+4=2+3$이므로 흩어진 집합이 아니다. 그리고 $\displaystyle \{1,2,3,5\}$는 흩어진 집합이므로 $\displaystyle a_4=3,a_5=4$이다. $\displaystyle \{1,2,3,5,8\}$은 흩어진 집합이므로 $\displaystyle a_8\ge5$이다.$\displaystyle a_7=4$임을 보이자. $\displaystyle n(S)=5$인 흩어진 집합 $\displaystyle S\subset\{1,2,\cdots,7\}$이 존재한다고 가정하자.$\displaystyle S$의 가장 큰 원소를 $\displaystyle M$, 가장 작은 원소를 $\displaystyle m$이라 하면 $\displaystyle k\le\frac{M-m}{2}$인 자연수 $\displaystyle k$에 대하여 두 자연수 $\displaystyle m+k,M-k$ 중 최대 하나만 $\displaystyle S$에 속할 수 있다. 따라서 $\displaystyle S$의 원소의 개수는 $\displaystyle 2+\frac{M-m}{2}$ 이하인데 $\displaystyle n(S)=5$이므로 $\displaystyle m=1,M=7$이다. $\displaystyle 2$와 $\displaystyle 6$ 중 하나만 $\displaystyle S$에 속하고 $\displaystyle 3$과 $\displaystyle 5$ 중 하나만 $\displaystyle S$에 속하므로 $\displaystyle 4\in S$이어야 하고, 각각의 경우를 확인해보면 $\displaystyle x+y=z+w$인 서로 다른 네 원소를 항상 찾을 수 있다. 이는 $\displaystyle S$가 흩어진 집합이라는 것에 모순이고, 따라서 $\displaystyle a_7=4$이다.또한 $\displaystyle a_5=4,a_7=4$이므로 $\displaystyle a_6=4$이다. 따라서 조건을 만족하는 $\displaystyle k$는 $\displaystyle 5,6,7$이다.

(3-2) 귀류법을 이용하여 $\displaystyle 1,k\in S$임을 증명하자.(i) $\displaystyle k\notin S$라고 가정하자. 이때 $\displaystyle S\subset\{1,2,\cdots,k-1\}$이고 $\displaystyle S$는 흩어진 집합이므로 $\displaystyle a_{k-1}\ge n(S)=a_k$이다. 이는 $\displaystyle a_{k-1}<a_k$에 모순이다. 따라서 $\displaystyle k\in S$이다.(ii) $\displaystyle 1\notin S$라고 가정하자. $\displaystyle S^{\prime}=\{i-1\mid i\in S\}$라 하자. $\displaystyle S$의 모든 원소는 $\displaystyle 1$보다 크기 때문에 $\displaystyle S^{\prime}$의 모든 원소는 $\displaystyle 1$이상 $\displaystyle k-1$ 이하이다. 그리고 제시문 (나)에 의하여 $\displaystyle S^{\prime}$은 흩어진 집합이고 $\displaystyle a_{k-1}\ge n(S^{\prime})=a_k>a_{k-1}$이 되어 모순이 생긴다. 따라서 $\displaystyle 1\in S$이다.그러므로 $\displaystyle m=1,M=k$이고 $\displaystyle M-m$으로 가능한 값은 $\displaystyle k-1$뿐이다.

(3-3) (a) $\displaystyle 1$ 이상 $\displaystyle k$ 이하인 서로 다른 자연수 $\displaystyle a,b,c,d$가 존재하여 $\displaystyle p_a+p_b=p_c+p_d$라 가정하자.일반성을 잃지 않고 $\displaystyle a>c>d>b$라 하자. $\displaystyle a,c,d$는 자연수이므로 $\displaystyle c\le a-1,d\le a-2$이다.이때 $\displaystyle p_a=p_{a-1}+p_{a-2}\ge p_c+p_d=p_a+p_b>p_a$이므로 $\displaystyle p_a+p_b=p_c+p_d$라는 것에 모순이다. 귀류법에 의하여 $\displaystyle \{p_1,p_2,\cdots,p_k\}$는 흩어진 집합이다.

(b) $\displaystyle S=\{p_k-p_i+1\mid$ $\displaystyle i$는 $\displaystyle 1\le i\le k$인 자연수$\displaystyle \}$라 하면 조건 (i), (ii)를 만족한다. 이제 $\displaystyle S$가 흩어진 집합임을 증명하자. $\displaystyle x_1+x_2=x_3+x_4$인 서로 다른 네 개의 자연수 $\displaystyle x_1,x_2,x_3,x_4\in S$가 존재한다고 가정하자. $\displaystyle i=1,2,3,4$에 대하여 $\displaystyle y_i=p_k+1-x_i$라 정의하자. 그러면 제시문 (나)에 의하여 $\displaystyle y_1+y_2=y_3+y_4$이고 $\displaystyle y_1,y_2,y_3,y_4\in\{p_1,p_2,\cdots,p_k\}$가 성립한다. 이는 집합 $\displaystyle \{p_1,p_2,\cdots,p_k\}$가 흩어진 집합이라는 것에 모순이다. 따라서 $\displaystyle S$는 흩어진 집합이다.