의예과 3번

인하대 2022학년도 모의 의예과 3번 · mathesis.kr/archive/inha/2022mo/uiye_3

[문제 3] (30점) 다음 제시문을 읽고 물음에 답하시오.

(가) [수학적 귀납법] 자연수 $\displaystyle n$ 에 대한 명제 $\displaystyle p(n)$ 이 모든 자연수 $\displaystyle n$ 에 대하여 성립함을 증명하려면 다음 두 가지를 보이면 된다.(1) $\displaystyle n=1$ 일 때, 명제 $\displaystyle p(n)$ 이 성립한다.(2) $\displaystyle n=k\ (k\ge1)$ 일 때 명제 $\displaystyle p(n)$ 이 성립한다고 가정하면, $\displaystyle n=k+1$ 일 때에도 명제 $\displaystyle p(n)$ 이 성립한다.

(나) [집합의 분할] 집합 $\displaystyle X$ 에 대하여 다음 조건을 모두 만족하는 집합 $\displaystyle \{A_1,A_2,\ldots,A_m\}$ 을 “ $\displaystyle X$ 의 분할”이라 한다.(1) 모든 $\displaystyle i=1,2,\ldots,m$ 에 대하여 $\displaystyle \varnothing\neq A_i\subseteq X$ 이다.(2) 서로 다른 $\displaystyle i,j\in\{1,2,\ldots,m\}$ 에 대하여 $\displaystyle A_i\cap A_j=\varnothing$ 이다.(3) $\displaystyle A_1\cup A_2\cup\cdots\cup A_m=X$ 예를 들어, $\displaystyle \{\{1,2,3\},\{4\}\}$ 와 $\displaystyle \{\{1,2\},\{3\},\{4\}\}$ 는 모두 $\displaystyle \{1,2,3,4\}$ 의 분할이다.또한, $\displaystyle m$ 개의 부분집합으로 구성된 $\displaystyle X$ 의 분할이 존재하면, “ $\displaystyle X$ 를 $\displaystyle m$ 개의 집합으로 분할 가능하다”라고 한다.

(※) 자연수를 원소로 갖는 공집합이 아닌 집합 $\displaystyle A$ 가 다음 조건 중 하나를 만족하면 $\displaystyle A$ 를 “독립적인 집합”이라 부르자.(1) $\displaystyle n(A)=1$ (2) $\displaystyle A$ 의 임의의 서로 다른 두 원소 $\displaystyle x,y$ 에 대하여 $\displaystyle x$ 는 $\displaystyle y$ 의 약수도 아니고 배수도 아니다.

(3-1) (a) $\displaystyle 2$ 이상인 모든 자연수 $\displaystyle n$ 에 대하여 $\displaystyle A_n=\{2^{n-1}+1,2^{n-1}+2,\ldots,2^n\}$ 은 독립적인 집합임을 보이시오. [5점](b) 임의의 자연수 $\displaystyle n$ 에 대하여 집합 $\displaystyle \{1,2,3,\ldots,2^n\}$ 을 $\displaystyle n+1$ 개의 독립적인 집합으로 분할 가능함을 보이시오. [5점]

(3-2) 자연수 $\displaystyle n$ 에 대하여 $\displaystyle D(n)$ 을 $\displaystyle n$ 의 모든 약수의 집합이라 하자.(a) 음이 아닌 정수 $\displaystyle m$ 에 대하여 집합 $\displaystyle X_m=\{2^a\cdot3^b\mid$ $\displaystyle a$ 와 $\displaystyle b$ 는 $\displaystyle a+b=m$ 을 만족하는 음이 아닌 정수 $\displaystyle \}$ 가 독립적인 집합임을 보이시오. [5점](b) 음이 아닌 정수 $\displaystyle a,b$ 에 대하여 $\displaystyle D(2^a\cdot3^b)$ 은 $\displaystyle a+b+1$ 개의 독립적인 집합으로 분할 가능함을 보이시오. [5점]

(3-3) 수학적 귀납법을 이용하여 다음 명제가 성립함을 보이시오. [10점]

$\displaystyle a+b\ge1$ 인 모든 음이 아닌 정수 $\displaystyle a,b$ 에 대하여 $\displaystyle D(2^a\cdot3^b)$ 은 $\displaystyle a+b$ 개의 독립적인 집합으로 분할 가능하지 않다.

해설강의 준비중

인하대 2022학년도 모의 의예과 3번 · mathesis.kr/archive/inha/2022mo/uiye_3

+5점 · (a) 서로 다른 두 자연수

\displaystyle a,b

에 대하여

\displaystyle a

가

\displaystyle b

의 배수이면

\displaystyle a

는

\displaystyle 2b

이상이어야 된다는 사실을 이용하여 증명하면

(3-1) (a) 주어진 집합이 독립적인 집합이 아니라고 가정하자. 그러면 약수 배수 관계인 서로 다른 두 원소 $\displaystyle x,y$ 가 존재한다. 일반성을 잃지 않고 $\displaystyle x$ 가 $\displaystyle y$ 의 약수라 하면 $\displaystyle 2^n\ge y\ge2x\ge2(2^{n-1}+1)=2^n+2$ 가 되어 모순이 생긴다. 따라서 독립적인 집합이다.

+5점 · (b) (a)의 결과를 이용하지 않더라도 올바른 예를 찾아 증명하면

(b) $\displaystyle \{\{1\},\{2\},A_2,\cdots,A_n\}$ 은 $\displaystyle \{1,2,\ldots,2^n\}$ 의 분할이고 $\displaystyle \{1\},\{2\},A_2,\ldots,A_n$ 은 서로 다른 독립적인 집합이다. 따라서 $\displaystyle \{1,2,\ldots,2^n\}$ 은 $\displaystyle n+1$ 개의 독립적인 집합으로 분할 가능하다.

+5점 · (a)

\displaystyle X_m

의 두 원소

\displaystyle 2^{a_1}\cdot3^{b_1}

과

\displaystyle 2^{a_2}\cdot3^{b_2}

에 대하여

\displaystyle 2^{a_1}\cdot3^{b_1}

이

\displaystyle 2^{a_2}\cdot3^{b_2}

의 약수일 필요충분조건이

\displaystyle a_1\le a_2

이고

\displaystyle b_1\le b_2

이라는 사실을 이용하여 증명하면

(3-2) (a) $\displaystyle m=0$ 이면 $\displaystyle X_0=\{1\}$ 이므로 정의에 따라 $\displaystyle X_0$ 는 독립적인 집합이다. $\displaystyle m\ge1$ 이라 하자. $\displaystyle X_m$ 이 독립적인 집합이 아니라고 가정하면, $\displaystyle X_m$ 의 서로 다른 두 원소 $\displaystyle x=2^{a_1}\cdot3^{b_1}$ , $\displaystyle y=2^{a_2}\cdot3^{b_2}$ 이 존재하여 $\displaystyle x$ 가 $\displaystyle y$ 의 약수이거나 $\displaystyle y$ 가 $\displaystyle x$ 의 약수이어야 한다. 일반성을 잃지 않고 $\displaystyle x$ 가 $\displaystyle y$ 의 약수라 하자. 이때 $\displaystyle a_1\le a_2,b_1\le b_2$ 가 성립하는데 $\displaystyle a_1+b_1=a_2+b_2=m$ 이므로 $\displaystyle a_1=a_2,b_1=b_2$ 가 되어 $\displaystyle x\neq y$ 에 모순이다. 따라서 $\displaystyle X_m$ 은 독립적인 집합이다.

+5점 · (b) (a)의 결과를 이용하여 올바른 예를 찾아 증명하면

(b) $\displaystyle \{X_0,X_1,\ldots,X_{a+b}\}$ 는 $\displaystyle D(2^a\cdot3^b)$ 의 분할이고 각 $\displaystyle X_i$ 는 독립적인 집합이므로 $\displaystyle D(2^a\cdot3^b)$ 은 $\displaystyle a+b+1$ 개의 독립적인 집합으로 분할 가능하다.Comment. (3-2)(b)의 분할은 $\displaystyle X_i$ 가 아니라 $\displaystyle X_i\cap D(2^a3^b)$ , $\displaystyle i=0,1,\ldots,a+b$ 로 구성해야 한다. 예를 들어 $\displaystyle a=b=1$ 이면 $\displaystyle X_2=\{4,6,9\}$ 에는 $\displaystyle D(6)$ 의 원소가 아닌 $\displaystyle 4,9$ 가 포함된다. 교집합을 취하면 원하는 분할을 얻는다. 그러나 원칙에 따라 원문 표기를 그대로 실었다.

+3점 ·

\displaystyle 2^a\cdot3^b

은

\displaystyle D(2^a\cdot3^b)

의 모든 원소의 배수라는 것을 이용하여

\displaystyle 2^a\cdot3^b

을 포함하는

\displaystyle D(2^a\cdot3^b)

의 독립적인 부분집합은

\displaystyle \{2^a\cdot3^b\}

뿐이라는 것을 증명하면

+7점 · 수학적 귀납법을 이용하여 주어진 명제를 증명하면

(3-3) $\displaystyle a+b$ 에 대한 수학적 귀납법을 사용하자. $\displaystyle a+b=1$ 이면 $\displaystyle D(2^a\cdot3^b)$ 은 $\displaystyle \{1,2\}$ 또는 $\displaystyle \{1,3\}$ 이다. 두 집합 모두 독립적인 집합이 아니므로 하나의 독립적인 집합으로 분할 가능하지 않다.수학적 귀납법을 사용하기 위하여 $\displaystyle a+b>1$ 인 경우를 보자. 일반성을 잃지 않고, $\displaystyle a>1$ 이라 할 수 있다.Correction. (3-3)의 ‘ $\displaystyle a>1$ 이라 할 수 있다’에서 $\displaystyle a>1$ 은 $\displaystyle a\ge1$ 의 오기이다. $\displaystyle a=b=1$ 인 경우도 포함해야 하며, 뒤의 논증에서 필요한 조건은 $\displaystyle a-1\ge0$ 이다. $\displaystyle a=0$ 인 경우에는 $\displaystyle b$ 를 하나 줄여 같은 논증을 적용한다. 그러나 원칙에 따라 원문 표기를 그대로 실었다. $\displaystyle D(2^a\cdot3^b)$ 을 $\displaystyle a+b$ 개의 독립적인 집합으로 분할 가능하다고 가정하고, $\displaystyle \{Y_1,Y_2,\ldots,Y_{a+b}\}$ 를 독립적인 집합으로의 분할이라 하자. 일반성을 잃지 않고 $\displaystyle 2^a\cdot3^b\in Y_{a+b}$ 라 하자. $\displaystyle 2^a\cdot3^b$ 은 $\displaystyle D(2^a\cdot3^b)$ 의 모든 원소의 배수이므로 $\displaystyle Y_{a+b}=\{2^a\cdot3^b\}$ 이다. 따라서 $\displaystyle \{Y_1,Y_2,\ldots,Y_{a+b-1}\}$ 은 $\displaystyle D(2^a\cdot3^b)-\{2^a\cdot3^b\}$ 의 분할이 된다. 각각의 $\displaystyle i=1,2,\ldots,a+b-1$ 에 대하여 $\displaystyle Z_i=Y_i\cap D(2^{a-1}\cdot3^b)$ 라 하고 $\displaystyle Z_1,Z_2,\ldots,Z_{a+b-1}$ 중 정확히 $\displaystyle d\ (\le a+b-1)$ 개가 공집합이 아니라고 하자. 일반성을 잃지 않고, $\displaystyle Z_1,Z_2,\ldots,Z_d$ 는 공집합이 아니고, $\displaystyle Z_{d+1}=Z_{d+2}=\cdots=Z_{a+b-1}=\varnothing$ 이라 하자. $\displaystyle D(2^{a-1}\cdot3^b)\subseteq D(2^a\cdot3^b)-\{2^a\cdot3^b\}$ 이므로, $\displaystyle \{Z_1,Z_2,\ldots,Z_d\}$ 는 $\displaystyle D(2^{a-1}\cdot3^b)$ 의 분할인데, $\displaystyle d\le a+b-1$ 이므로 $\displaystyle D(2^{a-1}\cdot3^b)$ 이 $\displaystyle a+b-1$ 개의 독립적인 집합으로 분할 가능하지 않다는 귀납 가정에 모순이다. 따라서 $\displaystyle D(2^a\cdot3^b)$ 은 $\displaystyle a+b$ 개의 독립적인 집합으로 분할 가능하지 않다.

첨삭 사례

아직 등록된 첨삭 사례가 없습니다.

질문과 답변 · 0개질문과 답변 · 고정 0개

아직 등록된 질문이 없습니다. 질문 작성은 멤버십 회원만 가능합니다.