# 24주차 — 중간 종합 평가 (1~23주차) + 오답 클리닉 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 틀린 문제는 실패가 아니라, 어느 주차로 돌아갈지 알려 주는 좌표다. **이 주의 위치**: 50주 과정의 반환점. 범위는 1~23주차 전체(정의$\cdot$집합$\cdot$논리$\cdot$세기$\cdot$직접$\cdot$부등식$\cdot$케이스$\cdot$대우$\cdot$귀류$\cdot$합동)이고, 여기까지가 증명의 4대 기법을 갖추는 구간이었다. **원서 대응**: BoP(Book of Proof) 1~6장 종합 점검. 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. **백지 시험 20문항**으로 상반기 전체를 점검한다 (권장 150분). 1. 오답 클리닉 절차로 약한 주차를 찾아 복습 계획을 세운다. 1. 4대 기법(직접$\cdot$케이스$\cdot$대우$\cdot$귀류)의 관계 지도를 자기 언어로 완성한다. ## 시험 규칙 - 교재와 노트를 완전히 덮는다. 백지와 펜만 쓴다. - 증명 문항은 서식(오프닝~$\blacksquare$)과 글쓰기 규칙 6조(20주차 §1.7)까지 채점 대상이다. - 다 푼 뒤에는 해설의 **접근**만 보고 1차 재시도를 하고, 그다음 풀이로 최종 확인한다. 이어서 §2의 오답 클리닉 절차로 넘어간다. ## 백지 시험 (20문항) ### 기본 ●○○ **1.** [정의 백지 테스트] 다음 8개의 정의를 쓰시오: 짝수 / $a \mid b$ / 소수 / 유리수 / $\lvert x \rvert$ / $A \subseteq B$ / $\mathcal{P}(A)$ / $a \equiv b \pmod n$ **2.** (a) $P \Rightarrow Q$의 진리표를 그리시오. (b) $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$를 진리표로 증명하시오. **3.** 다음 문장의 부정을 만드시오 (부정 기호가 밖에 남지 않게). (a) $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y^2 = x$ (b) $n$이 소수이면 $n$은 홀수이다. (c) $x > 0$이고 $y > 0$이다. **4.** $A = \{1, 2\}$, $B = \{2, 3\}$, $U = \{1,2,3,4\}$일 때: (a) $(A \cup B)^c$ (b) $A - B$ (c) $\mathcal{P}(A)$ (d) $A \times B$를 구하시오. **5.** $C = \{\emptyset, \{1\}, 2\}$에 대해 참$\cdot$거짓: (a) $\emptyset \in C$ (b) $\emptyset \subseteq C$ (c) $\{1\} \subseteq C$ (d) $\{\{1\}\} \subseteq C$ (e) $\{2\} \in C$ **6.** $x$는 실수. "$x^2 < 4$"는 "$x < 2$"이기 위한 무슨 조건인지 진리집합으로 판정하시오. ### 표준 ●●○ **7.** 남자 4명, 여자 5명 중 남자 2명$\cdot$여자 2명으로 위원회를 만드는 가짓수를 구하시오 — 사용한 원리를 명시하며 서술할 것. **8.** 1부터 200까지의 자연수 중 4의 배수이거나 6의 배수인 것은 몇 개인가? **9.** $m, n$이 모두 홀수이면 $m^2 + 3n^2$은 짝수임을 증명하시오. **10.** $x$가 유리수이면 $\dfrac{2x + 1}{3}$도 유리수임을 증명하시오. **11.** $a \ge 0$, $b \ge 0$이면 $\sqrt{ab} \le \dfrac{a + b}{2}$임을 등호 조건까지 증명하시오 (AM–GM 백지 재현). **12.** 모든 실수 $x$에 대해 $|x - 1| + |x + 1| \ge 2$임을 경우 나누기로 증명하시오. (경우: $x \ge 1$ / $-1 \le x < 1$ / $x < -1$) **13.** 정수 $n$에 대해, $5n - 7$이 짝수이면 $n$은 홀수임을 대우로 증명하시오. **14.** $\sqrt{5}$는 무리수임을 증명하시오. (부품: "$5 \mid n^2$이면 $5 \mid n$" — 19주차 문제 15) ### 도전 ●●● **15.** $9^{99}$의 일의 자리를 구하시오 (합동 계산 — 주기부터). **16.** $a \equiv b \pmod n$이면 $a^3 \equiv b^3 \pmod n$임을 (C5)를 인용해 증명하시오. **17.** 파스칼 공식 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$의 세기 증명을 백지 재현하시오. **18.** 다음 각 명제의 1순위 기법과 신호를 쓰시오 (증명 불필요). (a) $n^2 + 3n$이 홀수이면 $n$은 홀수이다. (b) $\sqrt{2} + \sqrt{7}$은 무리수이다. (c) $a \mid b$이고 $b \mid c$이면 $a \mid c$이다. (d) 가장 큰 소수는 존재하지 않는다. **19.** (진단) 다음 답안의 결함을 모두 찾으시오. :::{container} quotebox "명제: $x + y$가 홀수이면 $x$와 $y$의 홀짝이 다르다. 증명: 대우로 증명한다. 대우는 '$x$와 $y$의 홀짝이 다르면 $x+y$는 홀수이다'이다. $x = 2a$, $y = 2b+1$이라 하면 $x + y = 2(a+b)+1$은 홀수이다. 따라서 원명제가 성립한다. $\blacksquare$" ::: **20.** (서술) 직접$\cdot$케이스$\cdot$대우$\cdot$귀류 네 기법의 관계 지도를 그리듯 서술하시오 — 각 기법이 무엇을 가정하고 어디로 가는지, 서로 어떻게 포함$\cdot$조합되는지 (다섯 문장 이내). ## 오답 클리닉 절차 1. 틀린 문항마다 아래 표에서 **돌아갈 주차**를 찾는다. 1. 그 주차의 "백지 복습 체크리스트"를 다시 수행한다 (개념 재독 $\to$ 예제 재필사 $\to$ 해당 유형 문제 2개 재풀이). 1. 이틀 뒤 이 시험의 해당 문항을 **다시 백지로** 푼다. 통과하면 다음 문항 클리닉으로 넘어간다. 1. 틀린 문항이 6개 이상이면 25주차로 넘어가지 말고 1주 복습 주간을 넣는다 — 25주차 이후의 모든 증명이 이 20문항의 도구 위에 쌓인다. **50주는 목표이지 규정이 아니다.** | **문항** | **주차** | **문항** | **주차** | |---|---|---|---| | 1 | 1$\cdot$2$\cdot$4$\cdot$15$\cdot$17$\cdot$20 (정의) | 11 | 16 (부등식) | | 2 | 8$\cdot$9 (조건문$\cdot$대우 동치) | 12 | 17 (케이스$\cdot$절댓값) | | 3 | 11 (부정 규칙) | 13 | 19 (대우) | | 4 | 5$\cdot$6 (집합 연산$\cdot$곱) | 14 | 21 (귀류$\cdot$무리수) | | 5 | 4 ($\in$/$\subseteq$) | 15 | 20 (합동 계산) | | 6 | 8 (진리집합) | 16 | 20 (합동 성질) | | 7 | 12$\cdot$13 (세기 서술) | 17 | 13 (세기 논증) | | 8 | 14 (포함–배제) | 18 | 23 (기법 선택) | | 9 | 15 (직접 증명) | 19 | 11$\cdot$19$\cdot$23 (부정$\cdot$대우 진단) | | 10 | 15 (직접 증명) | 20 | 22$\cdot$23 (기법 관계) | ## 해설 틀린 문제는 **접근**만 읽고 재시도한 뒤, 그다음에 풀이를 확인한다. ### 문제 1 **접근.** 정의는 낱말의 뜻풀이가 아니라 등식과 조건까지가 본체다. 여덟 정의의 출처는 1주차 정의 1.1(짝수), 2주차 정의 2.1($a \mid b$), 15주차 정의 15.2(소수), 15주차 정의 15.1(유리수), 17주차 정의 17.1(절댓값), 4주차 정의 4.1(부분집합), 4주차 정의 4.2(멱집합), 20주차 정의 20.1(합동)이다. 채점 지점은 조건을 담은 낱말들 — "존재한다", 유리수의 $b \neq 0$, 소수의 $n \ge 2$, 절댓값의 케이스 구분, 부분집합의 "모든", 멱집합의 "전부", 합동의 $n \mid (a-b)$ — 이며, 이 중 하나라도 빠지면 정의가 다른 대상을 가리키게 된다. **풀이.** ① **짝수.** 정수 $n$이 짝수라는 것은, $n = 2k$인 정수 $k$가 존재한다는 뜻이다. ② **나누어떨어짐.** 정수 $a, b$에 대해 $a \mid b$라는 것은, $b = ac$인 정수 $c$가 존재한다는 뜻이다. ③ **소수.** $n \ge 2$인 정수 $n$이 소수라는 것은, $n$의 양의 약수가 $1$과 $n$뿐이라는 뜻이다. ④ **유리수.** 실수 $x$가 유리수라는 것은, $x = \dfrac{a}{b}$인 정수 $a, b$ ($b \neq 0$)가 존재한다는 뜻이다. ⑤ **절댓값.** 실수 $x$에 대해 $x \ge 0$이면 $|x| = x$이고, $x < 0$이면 $|x| = -x$이다. ⑥ **부분집합.** $A$의 모든 원소가 $B$의 원소일 때 $A \subseteq B$라 쓴다. 즉 "모든 $x$에 대해, $x \in A$이면 $x \in B$이다". ⑦ **멱집합.** $\mathcal{P}(A)$는 $A$의 부분집합 전부를 원소로 모은 집합이다: $\mathcal{P}(A) = \{X : X \subseteq A\}$. ⑧ **합동.** 정수 $a, b$와 자연수 $n$에 대해, $a \equiv b \pmod n$이라는 것은 $n \mid (a - b)$라는 뜻이다. **복기.** ①②④⑧은 "~인 정수가 존재한다" 또는 나누어떨어짐 꼴이라 증명에서 곧바로 등식을 내어 준다. ③⑥⑦은 등식이 아니라 판정 기준으로 쓰이고, ⑤는 정의 자체가 케이스이므로 절댓값이 걸린 증명이 경우 나누기가 되는 이유가 된다. 하나라도 틀렸다면 해당 주차의 정의 상자를 다시 암기한 뒤 이 문항만 재시험한다. ### 문제 2 **접근.** (a)는 조건문의 정의(8주차 정의 8.1)를 그대로 표로 옮기는 일이고, 기억해야 할 것은 거짓이 되는 행이 "$P$가 참인데 $Q$가 거짓"인 단 한 행뿐이라는 사실이다. (b)는 두 식의 진리값 열을 만들어 네 행 전부에서 일치함을 보이는 작업이며, 9주차 예제 2.1의 6열 표를 그대로 재현하면 된다. 동치의 정의(9주차 정의 9.1)가 "모든 행에서 진리값이 같다"이므로, 결론 문장은 반드시 열 두 개의 일치를 지목하며 닫아야 한다. **풀이.** (a) 조건문의 진리표는 다음과 같다. | **$P$** | **$Q$** | **$P \Rightarrow Q$** | |---|---|---| | T | T | T | | T | F | F | | F | T | T | | F | F | T | 거짓이 되는 행은 둘째 행($P$ 참, $Q$ 거짓) 하나뿐이다. (b) 여섯 열을 만든다. | **$P$** | **$Q$** | **$P \Rightarrow Q$** | **$\neg Q$** | **$\neg P$** | **$\neg Q \Rightarrow \neg P$** | |---|---|---|---|---|---| | T | T | T | F | F | T | | T | F | F | T | F | F | | F | T | T | F | T | T | | F | F | T | T | T | T | 셋째 열과 여섯째 열이 네 행 모두에서 (T, F, T, T)로 일치한다. 따라서 정의 9.1에 의해 $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$이다. $\blacksquare$ **복기.** 여섯째 열을 만들 때 앞선 두 열($\neg Q$가 가정, $\neg P$가 결론)을 (a)의 규칙에 넣는다는 점이 유일한 기술이다. 둘째 행에서 가정 $\neg Q$가 참이고 결론 $\neg P$가 거짓이므로 F가 되고, 그 한 행이 두 열을 동시에 F로 만든다. ### 문제 3 **접근.** 세 문항이 각각 다른 규칙을 요구한다. (a)는 양화사 층별 뒤집기($\forall \to \exists$, $\exists \to \forall$)를 바깥쪽부터 차례로 적용하고 마지막에 남은 열린 문장을 부정한다. (b)는 조건문의 부정이 "이면"이 아니라 "인데" 꼴이 된다는 규칙 $\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$다. (c)는 드모르간 법칙이다. 세 경우 모두 "부정 기호가 밖에 남지 않게"가 조건이므로, 답에는 $\neg$나 "~가 아니다"가 문장 전체를 감싸는 형태가 남아 있으면 안 된다 (11주차). **풀이.** (a) 바깥의 $\forall x$가 $\exists x$로, 안쪽의 $\exists y$가 $\forall y$로 뒤집히고, 마지막에 $y^2 = x$가 $y^2 \neq x$가 된다. $$ \exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ y^2 \neq x $$ 말로 옮기면 "어떤 실수 $x$는 어느 실수의 제곱과도 같지 않다"이다. 이 부정 명제는 참이며, 증인은 음수다 — $x = -1$에 대해 모든 실수 $y$가 $y^2 \ge 0 > -1$을 만족한다. 따라서 원래 명제는 거짓이었다. (b) 원문은 "모든 정수 $n$에 대해, $n$이 소수이면 $n$은 홀수이다"이므로, 전칭이 존재로 바뀌고 조건문이 "인데" 꼴로 풀린다: "$n$이 소수**인데** 홀수가 아닌 그런 $n$이 존재한다." 기호로는 $\exists n$, ($n$은 소수) $\wedge$ ($n$은 홀수가 아니다)이고, 정수 범위에서 "홀수가 아니다"는 "짝수이다"이므로 "짝수인 소수가 존재한다"로도 적는다. 이 부정 역시 참이다 — $n = 2$가 증인이다. (c) 드모르간에 의해 "그리고"가 "또는"으로 바뀌고 각 조각이 부정된다. "$x > 0$"의 부정은 "$x \le 0$"이므로 답은 "$x \le 0$이거나 $y \le 0$이다." **복기.** (c)에서 "$x < 0$이거나 $y < 0$"으로 적는 경우가 많다. 원인은 부등호를 뒤집으면서 등호를 흘린 것이며, $x = 0$이 "$x > 0$"을 만족하지 않는다는 사실을 확인하면 등호가 부정 쪽에 남아야 함이 드러난다. ### 문제 4 **접근.** 네 문항 모두 정의를 그대로 실행하는 계산이다. 여집합은 전체집합에서 빼는 것이므로 $U$를 반드시 사용해야 하고, 차집합은 "$A$에 있으면서 $B$에 없는 것", 멱집합은 부분집합 전부(원소 수 $2^{|A|}$), 데카르트 곱은 순서쌍 전부(원소 수 $|A| \times |B|$)다. 개수를 먼저 계산해 두면 나열이 끝난 뒤 빠뜨린 원소가 있는지 검산할 수 있다. **풀이.** (a) 먼저 $A \cup B = \{1,2\} \cup \{2,3\} = \{1,2,3\}$이다. 여집합은 $U$에서 이것을 뺀 것이므로 $(A \cup B)^c = \{1,2,3,4\} - \{1,2,3\} = \{4\}$. (b) $A - B$는 $A$의 원소 중 $B$에 없는 것이다. $1 \notin B$이므로 남고, $2 \in B$이므로 빠진다. 따라서 $A - B = \{1\}$. (c) $A = \{1,2\}$의 부분집합은 $2^2 = 4$개다: $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$. (d) $A \times B$는 앞자리가 $A$, 뒷자리가 $B$인 순서쌍 전부이므로 $2 \times 2 = 4$개다: $A \times B = \{(1,2), (1,3), (2,2), (2,3)\}$. **복기.** (c)의 답은 집합을 원소로 갖는 집합이므로 중괄호가 두 겹이고, 특히 $\emptyset$과 $A$ 자신을 빠뜨리지 않아야 개수 4가 맞는다. (d)에서 $(2,2)$를 "같은 수라서" 제외하는 경우가 있는데, 순서쌍은 두 자리가 서로 다른 집합에서 오므로 같은 값이 겹치는 것이 정상이다. ### 문제 5 **접근.** $C = \{\emptyset, \{1\}, 2\}$의 원소 목록을 먼저 종이에 박아 둔다 — 원소는 $\emptyset$, $\{1\}$, $2$의 셋뿐이다. 그다음 $\in$과 $\subseteq$를 구분한다. "$X \in C$"는 $X$가 이 목록에 그대로 실려 있는지를 묻고(한 겹 대조), "$X \subseteq C$"는 $X$의 원소를 하나씩 꺼내 그것들이 목록에 있는지를 묻는다(원소 건너보내기). 겹의 수를 세는 것이 판정의 전부다 (4주차). **풀이.** (a) **참.** 목록의 첫째 항이 $\emptyset$이므로 $\emptyset \in C$이다. (b) **참.** $\emptyset \subseteq C$를 풀면 "모든 $x$에 대해, $x \in \emptyset$이면 $x \in C$"인데 가정 $x \in \emptyset$이 결코 참이 되지 않으므로 조건문은 항상 참이다 — 공허한 참이며, 이 논증은 $C$가 무엇이든 성립한다. (c) **거짓.** $\{1\} \subseteq C$를 풀면 $\{1\}$의 원소 $1$이 $C$의 원소여야 한다. 목록에 있는 것은 $\{1\}$이라는 집합이지 $1$이라는 수가 아니므로 $1 \notin C$이고, 따라서 포함이 성립하지 않는다. (d) **참.** $\{\{1\}\}$의 원소는 $\{1\}$ 하나뿐이고, $\{1\}$은 목록의 둘째 항이므로 $\{1\} \in C$이다. 원소가 전부 $C$에 있으므로 $\{\{1\}\} \subseteq C$이다. (e) **거짓.** $\{2\} \in C$는 $\{2\}$라는 집합이 목록에 있는지를 묻는다. 목록에 있는 것은 $2$이지 $\{2\}$가 아니다. **복기.** 판정이 갈리는 자리는 (c)와 (d), 그리고 (d)와 (e)의 한 겹 차이다 — 목록에 실린 것이 $\{1\}$과 $2$이므로, $\{1\}$은 한 겹 올린 $\{\{1\}\}$의 포함을 참으로 만들지만 $2$는 한 겹 올린 $\{2\}$의 소속을 거짓으로 만든다. 반면 (a)와 (b)는 묻는 겹이 다른데도 둘 다 참이다 — (a)는 목록 대조로, (b)는 공허한 참으로 성립하므로 참이 되는 경로 자체가 다르다. 판정이 흔들리면 "지금 묻는 것이 상자 자체인가, 상자 안의 내용물인가"를 소리 내어 되묻는다. ### 문제 6 **접근.** 조건의 판정은 진리집합의 포함 방향으로 환원된다 (8주차). $P(x) \Rightarrow Q(x)$가 참인 것과 $P \subseteq Q$가 같은 말이므로, 두 진리집합을 구간으로 구한 뒤 어느 쪽이 어느 쪽에 들어가는지만 확인하면 된다. 포함이 성립하는 쪽이 충분조건이고, 역방향 포함이 깨지면 필요조건은 아니다. **풀이.** 먼저 진리집합을 구한다. $x^2 < 4 \iff |x| < 2 \iff -2 < x < 2$이므로 $P = (-2, 2)$이고, $Q = \{x : x < 2\} = (-\infty, 2)$이다. 정방향: $-2 < x < 2$인 모든 $x$는 $x < 2$를 만족하므로 $P \subseteq Q$이다. 따라서 "$x^2 < 4$"이면 "$x < 2$"이고, $P$는 $Q$이기 위한 **충분조건**이다. 역방향: $x = -5$는 $x < 2$를 만족하지만 $x^2 = 25 \ge 4$이므로 $P$에 속하지 않는다. 즉 $Q \subseteq P$는 거짓이고, $P$는 $Q$이기 위한 필요조건이 아니다. 결론: **충분조건이지만 필요조건은 아니다.** $\blacksquare$ **복기.** 반례 $x = -5$가 음수라는 점이 핵심이다. 양수만 시험하면 $x^2 < 4$와 $x < 2$가 같아 보이므로 판정이 "필요충분"으로 기운다 — 진리집합을 구간으로 그려 두면 왼쪽 끝이 서로 다르다는 사실이 눈에 남는다. ### 문제 7 **접근.** 위원회 하나를 정하는 일을 두 단계의 목록으로 분해한다 — ① 남자 2명 고르기 ② 여자 2명 고르기. 각 단계는 순서가 없는 선택이므로 조합(13주차 정의 13.1)이고, 단계를 잇는 것은 곱셈 원리(12주차)다. 이 문제는 "사용한 원리를 명시하며 서술할 것"이 조건이므로, 수 60만 적으면 채점 대상의 절반이 비어 있는 답안이 된다. 곱셈 원리를 쓰려면 첫 단계의 결과와 무관하게 둘째 단계의 선택지 수가 일정하다는 사실을 확인하고 적어야 한다. **풀이.** 남자 4명 중 2명을 고르는 방법은 순서가 무관하므로 $$ \binom{4}{2} = \frac{4 \times 3}{2 \times 1} = 6 $$ 가지이고, 여자 5명 중 2명을 고르는 방법은 $$ \binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10 $$ 가지이다. 위원회 하나는 (남자 2명의 모임, 여자 2명의 모임)이라는 길이 2의 목록으로 유일하게 결정되고, 남자를 어떻게 고르든 여자 쪽 선택지 수는 언제나 10으로 일정하다. 따라서 곱셈 원리에 의해 위원회의 가짓수는 $6 \times 10 = 60$가지이다. $\blacksquare$ **복기.** 두 수를 더해 16으로 적는 경우가 있는데, 원인은 "남자를 고르거나 여자를 고르거나"로 읽은 것이다. 덧셈 원리는 한 번에 한 갈래만 일어나는 분할에 쓰고, 곱셈 원리는 두 단계가 모두 일어나는 목록에 쓴다. ### 문제 8 **접근.** "이거나"이므로 합집합의 크기이고, 두 조건을 만족하는 수가 겹치므로 포함–배제의 원리(14주차 예제 2.1)를 쓴다: $|A \cup B| = |A| + |B| - |A \cap B|$. 1부터 $N$까지 $d$의 배수의 개수는 $\lfloor N/d \rfloor$로 세고, 겹침 $A \cap B$는 4의 배수이면서 6의 배수인 수, 곧 4와 6의 공배수이므로 최소공배수 $\mathrm{lcm}(4,6) = 12$의 배수다. **풀이.** $A$를 1부터 200까지의 4의 배수의 집합, $B$를 6의 배수의 집합이라 하자. $$ |A| = \left\lfloor \frac{200}{4} \right\rfloor = 50, \qquad |B| = \left\lfloor \frac{200}{6} \right\rfloor = 33, \qquad |A \cap B| = \left\lfloor \frac{200}{12} \right\rfloor = 16 $$ ($6 \times 33 = 198 \le 200 < 204$, $12 \times 16 = 192 \le 200 < 204$이므로 두 몫이 맞다.) 포함–배제에 의해 $$ |A \cup B| = 50 + 33 - 16 = 67 $$ 따라서 **67개**이다. $\blacksquare$ **복기.** 겹침을 $4 \times 6 = 24$의 배수로 잡아 8개로 세면 답이 75가 되어 어긋난다. 원인은 공배수를 곱으로 오인한 것이며, 4와 6이 공통 인수 2를 가지므로 곱은 공배수 전체가 아니라 그 일부만 센다. 두 수가 서로소일 때만 곱이 최소공배수와 일치한다. ### 문제 9 **접근.** 가정과 결론이 모두 홀짝이므로 직접 증명이 1순위다. 두 가지 길이 있다. 하나는 부품 조립 — "홀수의 제곱은 홀수"(1주차 문제 11), "홀수 $\times$ 홀수 = 홀수"(1주차 문제 8), "홀수 + 홀수 = 짝수"(1주차 예제 2.3)를 근거 ④로 인용해 잇는 길이다. 다른 하나는 정의를 대입해 끝까지 전개하는 길이며, 백지 시험에서는 인용할 문제 번호가 기억나지 않을 수 있으므로 전개 쪽이 안전하다. 어느 길이든 마지막은 $2 \times (\text{정수})$ 꼴을 실제로 만들어 보여야 닫힌다. **풀이.** $m, n$을 홀수라 하자. 정의 1.2에 의해 $m = 2a+1$, $n = 2b+1$인 정수 $a, b$가 존재한다. 그러면 $$ m^2 + 3n^2 = (2a+1)^2 + 3(2b+1)^2 = (4a^2 + 4a + 1) + 3(4b^2 + 4b + 1) $$ $$ = 4a^2 + 4a + 1 + 12b^2 + 12b + 3 = 4a^2 + 4a + 12b^2 + 12b + 4 = 2(2a^2 + 2a + 6b^2 + 6b + 2) $$ 이고, 정수의 합과 곱은 정수이므로(근거 ②) $2a^2 + 2a + 6b^2 + 6b + 2 \in \mathbb{Z}$이다. 따라서 정의 1.1에 의해 $m^2 + 3n^2$은 짝수이다. $\blacksquare$ **복기.** 부품 조립으로 쓰면 다음 세 줄이다 — $m$이 홀수이므로 $m^2$은 홀수(1주차 문제 11), $n^2$도 홀수이고 3이 홀수이므로 $3n^2$은 홀수(1주차 문제 8), 홀수와 홀수의 합은 짝수(1주차 예제 2.3)이므로 $m^2 + 3n^2$은 짝수이다. 상수항 $1 + 3 = 4$가 짝수라는 점이 두 길 모두의 급소이며, 계수 3이 짝수였다면 결론이 뒤집힌다. ### 문제 10 **접근.** 가정도 결론도 유리수이므로 직접 증명이고, 정의 15.1이 등식 $x = a/b$를 내어 주므로 그것을 식에 대입한 뒤 다시 "정수 분의 정수" 꼴로 정리하는 것이 전부다. 채점 지점은 두 곳이다 — 분자와 분모가 정수임을 각각 확인하는 것, 그리고 새 분모 $3b$가 0이 아님을 확인하는 것. 유리수 증명에서 $b \neq 0$의 확인이 빠지면 정의의 조각 하나가 검증되지 않은 채 결론을 선언한 답안이 된다. **풀이.** $x$를 유리수라 하자. 정의 15.1에 의해 $x = \dfrac{a}{b}$인 정수 $a, b$ ($b \neq 0$)가 존재한다. 그러면 $$ \frac{2x + 1}{3} = \frac{2 \cdot \dfrac{a}{b} + 1}{3} = \frac{\dfrac{2a + b}{b}}{3} = \frac{2a + b}{3b} $$ 여기서 $2a + b$는 정수의 곱과 합이므로 정수이고(근거 ②), $3b$도 정수이다. 또 $b \neq 0$이고 $3 \neq 0$이므로 $3b \neq 0$이다. 따라서 정의 15.1에 의해 $\dfrac{2x+1}{3}$은 유리수이다. $\blacksquare$ **복기.** 통분 과정을 생략하고 곧바로 $\dfrac{2a+b}{3b}$를 적어도 되지만, 그 경우에도 분자$\cdot$분모가 정수라는 문장과 $3b \neq 0$이라는 문장은 남겨야 한다. 이 두 문장이 정의의 조각과 일대일로 대응하는 부분이다. ### 문제 11 **접근.** 부등식이므로 차를 만들어 제곱으로 묶는 전략(16주차 예제 2.1)을 쓰는데, 여기서는 $\sqrt a$와 $\sqrt b$를 문자로 보아 $(\sqrt a - \sqrt b)^2 \ge 0$에서 출발하는 것이 가장 짧다(16주차 예제 2.2). 근거는 (W1) "모든 실수 $t$에 대해 $t^2 \ge 0$"이다. 가정 $a \ge 0$, $b \ge 0$은 세 곳에서 쓰인다 — $\sqrt a$, $\sqrt b$가 실수로 존재하게 하는 데, $(\sqrt a)^2 = a$가 성립하게 하는 데, 그리고 $\sqrt a \sqrt b = \sqrt{ab}$가 성립하게 하는 데(16주차 §1.2의 인정 사실). 등호 조건은 따로 계산하지 않고 (W1)의 등호 조건에서 그대로 따라 나온다. **풀이.** $a \ge 0$, $b \ge 0$이라 하자. 그러면 $\sqrt a$와 $\sqrt b$는 실수이고, $\sqrt a - \sqrt b$도 실수이므로 (W1)에 의해 $$ (\sqrt a - \sqrt b)^2 \ge 0 $$ 좌변을 전개하면 $(\sqrt a)^2 - 2\sqrt a \sqrt b + (\sqrt b)^2 = a - 2\sqrt{ab} + b$이고(마지막 등식에서 $a, b \ge 0$일 때의 $\sqrt a \sqrt b = \sqrt{ab}$를 썼다 — 16주차 §1.2의 인정 사실), $$ a - 2\sqrt{ab} + b \ge 0 $$ 양변에 $2\sqrt{ab}$를 더하면 $a + b \ge 2\sqrt{ab}$이고, 양변을 양수 2로 나누어도 부등호 방향은 바뀌지 않으므로 $$ \sqrt{ab} \le \frac{a+b}{2} $$ 등호 조건: 위 변형은 모두 동치 변형이므로, 등호가 성립하는 것과 $(\sqrt a - \sqrt b)^2 = 0$인 것은 같은 말이다. 이는 $\sqrt a = \sqrt b$와 같고, $a, b \ge 0$에서 제곱근이 같으면 양변을 제곱하여 $a = b$이다. 역으로 $a = b$이면 양변이 모두 $a$가 되어 등호가 성립한다. 따라서 등호는 $a = b$일 때에만 성립한다. $\blacksquare$ **복기.** 결론에서 출발해 양변을 제곱하며 내려가는 서술은 순환이 된다 — 증명하려는 것을 가정에 놓았기 때문이다. 반드시 $(\sqrt a - \sqrt b)^2 \ge 0$에서 시작해 결론으로 내려와야 하며, 이것이 차–제곱 전략의 방향 규칙이다. ### 문제 12 **접근.** 절댓값이 두 개이므로 정의 17.1을 벗기려면 각 절댓값의 부호가 갈리는 지점을 모두 표시해야 한다. $|x-1|$은 $x = 1$에서, $|x+1|$은 $x = -1$에서 갈리므로 실수선이 세 구간으로 나뉜다. 각 구간에서 두 절댓값을 동시에 벗겨 식을 정리하고, 그 구간의 조건을 부등식으로 사용해 2 이상임을 보인다. 케이스 증명의 채점 기준 두 가지 — 빠짐없음(세 구간의 합집합이 $\mathbb{R}$)과 각 경우의 완결 — 를 마지막에 명시한다 (17주차). **풀이.** $x$를 임의의 실수라 하자. **경우 1: $x \ge 1$.** 이때 $x - 1 \ge 0$이므로 $|x-1| = x-1$이고, $x + 1 \ge 2 > 0$이므로 $|x+1| = x+1$이다. 따라서 합은 $(x-1) + (x+1) = 2x$이고, $x \ge 1$이므로 $2x \ge 2$이다. ✓ **경우 2: $-1 \le x < 1$.** 이때 $x - 1 < 0$이므로 $|x-1| = -(x-1) = 1-x$이고, $x + 1 \ge 0$이므로 $|x+1| = x+1$이다. 따라서 합은 $(1-x) + (x+1) = 2$이고, $2 \ge 2$이다. ✓ 이 구간 전체에서 등호가 성립한다. **경우 3: $x < -1$.** 이때 $x - 1 < -2 < 0$이므로 $|x-1| = 1-x$이고, $x + 1 < 0$이므로 $|x+1| = -(x+1) = -x-1$이다. 따라서 합은 $(1-x) + (-x-1) = -2x$이고, $x < -1$의 양변에 $-2$를 곱하면 부등호가 뒤집혀 $-2x > 2$이다. ✓ 세 구간 $[1, \infty)$, $[-1, 1)$, $(-\infty, -1)$의 합집합이 $\mathbb{R}$ 전체이므로, 모든 실수 $x$에 대해 $|x-1| + |x+1| \ge 2$이다. $\blacksquare$ **복기.** 경우 3에서 $-2x > 2$를 얻을 때 음수를 곱하면서 부등호를 뒤집는 자리가 유일한 계산상의 급소다. 기하적으로 읽으면 $|x-1| + |x+1|$은 수직선에서 $x$로부터 $1$과 $-1$까지의 거리의 합이고, 이 합은 두 점 사이의 거리 2보다 작을 수 없으며 $x$가 두 점 사이에 있을 때 정확히 2가 된다 — 경우 2가 통째로 등호인 이유다. ### 문제 13 **접근.** 가정이 $5n-7$이라는 합성식이고 결론이 $n$이라는 단순식이다. 직접 증명은 $5n - 7 = 2k$에서 $n$의 꼴을 끌어내야 하는데 5로 나누는 단계가 정수 범위에서 보장되지 않아 막힌다. 반면 결론의 부정 "$n$은 짝수"는 곧바로 $n = 2k$라는 등식을 내어 주므로 대우가 1순위다(19주차 정의 19.1). 대우를 만들 때는 두 조각을 모두 부정하고 순서를 바꾼다는 규칙을 그대로 적용한다. **풀이.** 원명제의 가정은 "$5n-7$이 짝수", 결론은 "$n$이 홀수"이므로, 대우는 "$n$이 짝수이면 $5n-7$은 홀수이다"이다 (정수 범위에서 "홀수가 아니다"는 "짝수이다"이고, "짝수가 아니다"는 "홀수이다"이다). 이 대우를 증명한다. $n$을 짝수라 하자. 정의 1.1에 의해 $n = 2k$인 정수 $k$가 존재한다. 그러면 $$ 5n - 7 = 10k - 7 = 10k - 8 + 1 = 2(5k - 4) + 1 $$ 이고 $5k - 4$는 정수이므로(근거 ②), 정의 1.2에 의해 $5n - 7$은 홀수이다. 이로써 대우가 증명되었다. 대우는 원명제와 논리적으로 동치이므로(문제 2에서 진리표로 확인한 사실), 원명제 "$5n-7$이 짝수이면 $n$은 홀수이다"도 참이다. $\blacksquare$ **복기.** $-7$을 $-8 + 1$로 쪼개는 자리가 이 증명의 유일한 기술이다. $10k - 7$에서 멈추면 정의의 꼴 $2(\text{정수}) + 1$이 아니므로 아직 증명이 닫히지 않은 상태다. 또 답안 첫 줄에 "대우로 증명한다"와 대우 문장을 명시하지 않으면, 읽는 쪽에서는 가정과 결론이 뒤바뀐 답안으로 보인다. ### 문제 14 **접근.** 결론이 "무리수이다", 곧 "유리수가 아니다"라는 부정형이므로 직접 만들 재료가 없다. 귀류법으로 "유리수이다"를 가정하면 정의 15.1이 등식을 내어 준다 (21주차 예제 2.2의 $\sqrt2$ 증명과 같은 뼈대이고, 부품만 5짜리로 바꾼다). 기약분수(정의 21.2)로 두는 것이 모순을 만드는 장치이며, 마지막에 분자와 분모가 공통 약수 5를 가진다는 사실이 그 가정과 충돌한다. 부품 "$5 \mid n^2$이면 $5 \mid n$"은 19주차 문제 15에서 이미 증명했으므로 근거 ④로 인용한다. **풀이.** 모순을 이끌기 위해 $\sqrt5$가 유리수라고 가정하자. 정의 15.1에 의해 $\sqrt 5 = \dfrac{a}{b}$인 정수 $a, b$ ($b \neq 0$)가 존재하고, 공약수를 약분하여 $a$와 $b$가 서로소인 기약분수로 둘 수 있다(정의 21.2). 양변을 제곱하면 $5 = \dfrac{a^2}{b^2}$이고, 양변에 $b^2$을 곱하면 $$ a^2 = 5b^2 $$ $b^2$은 정수이므로 이 등식은 $5 \mid a^2$을 뜻한다. 19주차 문제 15에 의해 $5 \mid a$이므로, $a = 5c$인 정수 $c$가 존재한다. 이를 대입하면 $$ (5c)^2 = 5b^2 \ \Longrightarrow\ 25c^2 = 5b^2 \ \Longrightarrow\ b^2 = 5c^2 $$ 같은 이유로 $5 \mid b^2$이고, 다시 19주차 문제 15에 의해 $5 \mid b$이다. 그러면 5가 $a$와 $b$의 공약수인데, 이는 $\dfrac{a}{b}$가 기약분수라는 가정과 모순이다. 따라서 처음의 가정이 거짓이고, $\sqrt5$는 무리수이다. $\blacksquare$ **복기.** 기약이라는 단서를 처음에 걸어 두지 않으면 마지막 줄에서 부딪힐 대상이 없어 증명이 닫히지 않는다. 또 $5 \mid a^2$에서 곧바로 $5 \mid a$로 넘어가는 것은 5가 소수이기 때문에 성립하는 성질이고, 인용 없이 자명한 것으로 쓰면 그 자리가 논리 비약이 된다 — 실제로 4처럼 소수가 아닌 수에서는 $4 \mid 6^2$이지만 $4 \nmid 6$이다. ### 문제 15 **접근.** 일의 자리를 구하는 것은 10으로 나눈 나머지를 구하는 것, 곧 법 10에서의 합동을 구하는 것이다. 지수가 99로 크므로 직접 계산하지 않고 (C5) 곱 보존을 반복 적용해 지수를 쪼갠다(20주차 §1.6의 방법 — 확인 8$\cdot$9에서 $3^{100}$의 일의 자리를 구한 그 절차다). 절차는 세 단계다 — ① $9^k$를 작은 $k$부터 계산해 나머지가 1로 돌아오는 주기를 찾는다 ② 99를 주기로 나눈 몫과 나머지를 구한다 ③ 거듭제곱을 그 모양으로 쪼갠다. **풀이.** 법 10에서 9의 거듭제곱을 차례로 계산한다. $$ 9^1 \equiv 9, \qquad 9^2 = 81 = 8 \times 10 + 1 \equiv 1 \pmod{10} $$ $9^2 \equiv 1$이므로 주기는 2이다. 이제 $99 = 2 \times 49 + 1$이므로 $$ 9^{99} = 9^{2 \times 49 + 1} = (9^2)^{49} \cdot 9 $$ $9^2 \equiv 1$이므로 (C5)를 반복 적용하면 $(9^2)^{49} \equiv 1^{49} = 1 \pmod{10}$이고(반복 적용은 인정하고 쓴다 — 20주차 §1.6, 엄밀한 증명은 31주차 문제 13), 다시 (C5)로 $9$를 곱하면 $$ 9^{99} \equiv 1 \times 9 = 9 \pmod{10} $$ 따라서 $9^{99}$을 10으로 나눈 나머지는 9이고, **일의 자리는 9**이다. $\blacksquare$ **복기.** 검산으로 다른 길을 하나 더 쓸 수 있다. $9 \equiv -1 \pmod{10}$이므로 (C5)에 의해 $9^{99} \equiv (-1)^{99} = -1 \equiv 9 \pmod{10}$이다. 두 길의 답이 일치한다. 주기를 찾을 때 나머지가 1로 돌아오는 지점을 기준으로 삼는 이유는, 1이 되어야 그 뭉치를 통째로 지울 수 있기 때문이다. ### 문제 16 **접근.** (C5)는 "$a \equiv b$이고 $c \equiv d$이면 $ac \equiv bd \pmod n$"이다(20주차). 여기서 $c, d$ 자리에 새로운 합동을 넣을 필요가 없다 — 가진 합동이 하나뿐이므로 그것을 자기 자신과 짝지어 쓰면 지수가 하나씩 올라간다. 따라서 두 번 적용하면 3제곱에 도달한다. 답안에서는 (C5)를 쓸 때마다 어떤 두 합동에 적용했는지를 괄호로 밝히는 것이 채점 지점이다. **풀이.** $a \equiv b \pmod n$이라 하자. ① (C5)를 두 합동 ($a \equiv b$)와 ($a \equiv b$)에 적용한다. 곱 보존에 의해 $a \cdot a \equiv b \cdot b$, 즉 $$ a^2 \equiv b^2 \pmod n $$ ② 다시 (C5)를 두 합동 ($a^2 \equiv b^2$)와 ($a \equiv b$)에 적용한다. 곱 보존에 의해 $a^2 \cdot a \equiv b^2 \cdot b$, 즉 $$ a^3 \equiv b^3 \pmod n $$ 따라서 $a \equiv b \pmod n$이면 $a^3 \equiv b^3 \pmod n$이다. $\blacksquare$ **복기.** 같은 방식을 반복하면 지수를 하나씩 올릴 수 있다. 다만 "모든 자연수 $k$에 대해 $a^k \equiv b^k \pmod n$"이라는 일반형은 반복 자체를 정당화하는 귀납법이 필요하므로, 지금은 인정하고 쓴다(31주차 문제 13 — 20주차 §1.6의 유보와 같다). 이 성질이 문제 15에서 $9^{99}$의 지수를 쪼갤 때 쓴 근거이고, 두 문항은 같은 도구의 증명과 사용에 해당한다. 반대로 나눗셈은 (C5)로 보장되지 않으므로 $a^3 \equiv b^3$에서 $a \equiv b$를 되돌리는 서술은 성립하지 않는다. ### 문제 17 **접근.** 등식의 양변을 각각 무엇의 개수로 읽고, 같은 대상을 두 방법으로 세어 일치를 보이는 세기 논증이다(13주차 예제 2.2). 좌변은 정의 그대로 $k$-부분집합의 개수이고, 우변은 특정 원소 하나를 지정해 부분집합 전체를 "그 원소를 포함하는 것"과 "포함하지 않는 것"으로 가른 결과다. 채점 지점은 세 곳이다 — ① 세는 대상을 문장으로 선언했는가 ② 분할이 서로소이고 빠짐이 없음을 밝혔는가 ③ 각 무리의 개수를 근거와 함께 세었는가. **풀이.** $n \ge 1$이고 $1 \le k \le n-1$인 정수라 하자. 집합 $S = \{1, 2, \dots, n\}$의 원소 $k$개짜리 부분집합의 개수를 두 가지 방법으로 센다. **세는 방법 ①.** 정의 13.1에 의해 그 개수는 $\dbinom{n}{k}$이다. **세는 방법 ②.** $S$의 원소 하나를 지정해 "갑"이라 부르자(예를 들어 원소 $n$). $S$의 모든 $k$-부분집합은 갑을 포함하거나 포함하지 않거나 둘 중 하나이며, 두 경우가 동시에 일어날 수는 없다. 따라서 이 두 무리는 서로소이고 합쳐서 전체를 덮는다. - 갑을 포함하는 $k$-부분집합: 갑이 이미 한 자리를 차지했으므로 남은 $k-1$개를 갑을 제외한 $n-1$개 원소 중에서 고르면 되고, 그 방법은 $\dbinom{n-1}{k-1}$가지다. - 갑을 포함하지 않는 $k$-부분집합: $k$개 전부를 갑을 제외한 $n-1$개 원소 중에서 골라야 하므로 $\dbinom{n-1}{k}$가지다. 덧셈 원리에 의해 방법 ②의 총계는 $\dbinom{n-1}{k-1} + \dbinom{n-1}{k}$이다. 두 방법이 같은 대상을 세었으므로 두 값은 같다. 따라서 $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$ 이다. $\blacksquare$ **복기.** 세기 증명의 형식은 "무엇을 세는가"를 선언하는 첫 문장과 "같은 대상을 세었으므로 같다"는 마지막 문장 사이에 두 개의 세기를 넣는 것이다. 분할의 서로소$\cdot$완전성을 밝히지 않으면 덧셈 원리를 쓸 자격이 확인되지 않아 논증이 성립하지 않는다. ### 문제 18 **접근.** 증명을 쓰는 것이 아니라 기법을 고르는 문항이므로, 볼 것은 가정의 모양과 결론의 모양뿐이다(23주차). 판단 규칙은 세 가지다 — ① 가정이 등식을 내어 주면 직접 ② 가정이 합성식이라 풀리지 않고 결론의 부정이 잘 풀리면 대우 ③ 결론이 "~가 아니다", "존재하지 않는다" 같은 부정형이면 귀류. 각 답에는 기법 이름과 함께 그렇게 판단한 신호를 적어야 한다. **풀이.** (a) **대우.** 신호: 가정 "$n^2 + 3n$이 홀수"가 합성식이라 정의를 풀어도 $n$ 자체의 꼴이 나오지 않는 반면, 결론의 부정 "$n$은 짝수"는 $n = 2k$라는 등식을 곧바로 내어 준다. 대우는 "$n$이 짝수이면 $n^2 + 3n$은 짝수이다"이고, $n = 2k$를 대입해 $4k^2 + 6k = 2(2k^2 + 3k)$로 전개된다. (b) **귀류.** 신호: 결론 "무리수이다"가 "유리수가 아니다"라는 부정형이라 직접 만들 대상이 없다. $\sqrt2 + \sqrt7 = r$이 유리수라 가정하고 양변을 제곱하면 $9 + 2\sqrt{14} = r^2$, 곧 $\sqrt{14} = \dfrac{r^2 - 9}{2}$이므로 $\sqrt{14}$가 유리수라는 결론이 따라 나온다. 다만 $\sqrt{14}$가 무리수라는 사실은 23주차까지 확보된 부품(2$\cdot$3$\cdot$5 버전)만으로는 곧바로 나오지 않는다 — 7 버전 부품 "$7 \mid n^2$이면 $7 \mid n$"을 먼저 만들어야 한다(21주차 §4의 "부품 갈아 끼우기" 상자). 이 문항은 기법 판정만 요구하므로, 모순의 상대가 될 사실을 따로 확보해야 한다는 점을 지적하는 데서 멈춘다. (c) **직접.** 신호: 가정 두 개 $a \mid b$와 $b \mid c$가 모두 정의 2.1로 등식을 내어 주고, 결론 $a \mid c$도 같은 꼴의 등식을 만들면 되는 목표다. 이 명제가 2주차 예제 2.1의 추이성이며, $b = ak$, $c = bl$을 이어 $c = a(kl)$을 얻는다. (d) **귀류.** 신호: "존재하지 않는다"는 부정 존재 명제이고 "가장 큰"이라는 최대성이 걸려 있어, 직접 다룰 대상이 아예 없다. 가장 큰 소수 $p$가 있다고 가정하면 소수가 유한 개라는 뜻이므로, 21주차 예제 2.3(소수는 무한히 많다)과 곧바로 충돌한다. **복기.** (a)와 (c)를 가르는 것은 가정이 등식을 내어 주는지 여부 하나다. (b)와 (d)는 둘 다 귀류지만 모순의 출처가 다르다 — (b)는 별도로 확보해야 할 사실($\sqrt{14}$의 무리수성)과 부딪히고, (d)는 이미 증명된 명제(21주차 예제 2.3)와 부딪힌다. ### 문제 19 **접근.** 진단 문항에서는 계산이 맞는지가 아니라 논리의 뼈대가 맞는지를 본다. 확인 순서는 두 단계다 — ① 답안이 대우라고 부른 문장이 정말 대우인가(원명제의 가정과 결론을 각각 부정하고 순서를 바꾼 것인가) ② 그 문장을 증명하는 부분이 가정의 모든 경우를 덮는가. 이 답안은 두 단계 모두에서 무너진다. **풀이.** 결함은 두 가지다. ① **대우가 아니라 역이다.** 원명제를 $P \Rightarrow Q$로 두면 $P$는 "$x+y$가 홀수", $Q$는 "$x$와 $y$의 홀짝이 다르다"이다. 대우 $\neg Q \Rightarrow \neg P$는 "$x$와 $y$의 홀짝이 **같으면** $x+y$는 **짝수**이다"이다. 답안이 대우라 부른 "홀짝이 다르면 $x+y$는 홀수이다"는 $Q \Rightarrow P$, 곧 **역**이다. 역은 원명제와 논리적으로 동치가 아니므로(9주차 예제 2.2), 역을 증명해도 원명제는 증명되지 않은 채로 남는다. 이 역 자체는 참이지만, 참인 별개의 명제를 증명한 것일 뿐이다. ② **케이스 누락이다.** 설령 그 역을 증명하려 했다 해도, "$x$와 $y$의 홀짝이 다르다"는 ($x$ 짝, $y$ 홀)과 ($x$ 홀, $y$ 짝)의 두 경우를 뜻한다. 답안은 $x = 2a$, $y = 2b+1$이라는 한 경우만 다루었고, 두 경우가 대칭이라는 선언(WLOG)도 없다. 따라서 가정의 절반이 검증되지 않았다. **올바른 길.** 대우 "$x$와 $y$의 홀짝이 같으면 $x+y$는 짝수이다"를 두 경우로 증명한다. 경우 1 (둘 다 짝수): $x = 2a$, $y = 2b$인 정수 $a, b$가 존재하고, $x + y = 2a + 2b = 2(a+b)$이므로 짝수이다. 경우 2 (둘 다 홀수): $x = 2a+1$, $y = 2b+1$인 정수 $a, b$가 존재하고, $x + y = 2a + 2b + 2 = 2(a+b+1)$이므로 짝수이다. 두 경우가 "홀짝이 같다"를 빠짐없이 덮으므로 대우가 증명되었고, 대우는 원명제와 동치이므로 원명제도 참이다 (19주차 문제 13). $\blacksquare$ **복기.** 대우와 역은 자리 배치가 같고(둘 다 $Q$ 쪽이 가정, $P$ 쪽이 결론) 부정을 했는지 여부만 다르므로 서로 바꿔 쓰기 쉽다. 대우를 적은 뒤에는 반드시 "둘 다 부정했는가, 그리고 자리를 바꾸었는가"를 소리 내어 확인한다 — 9주차 §1.7의 세 구절 그대로, 역은 자리만, 이는 부정만, 대우는 둘 다이다. 곧 자리를 바꾸지 않고 둘 다 부정하면 이(inverse)이고, 부정 없이 자리만 바꾸면 역이다. ### 문제 20 **접근.** 네 기법을 나열하는 것이 아니라 관계를 그려야 하므로, 축을 두 개 잡는다 — ① 각 기법이 무엇을 가정에 놓고 무엇을 목표로 삼는가 ② 어느 기법이 어느 기법을 포함하거나 그 안에서 보조로 쓰이는가. 관계의 핵심 세 가지는 대우가 귀류의 특수형이라는 포함(22주차), 케이스는 독립 기법이라기보다 모든 기법 안에서 쓰이는 분할 장치라는 점, 그리고 네 기법의 몸통이 모두 같은 기술(정의 전개$\cdot$대수 변형$\cdot$기증명 명제 인용)이라는 점이다(23주차). **풀이.** (예시 답안) 직접 증명은 $P$를 가정에 놓고 정보가 $P$에서 $Q$로 순방향으로 흐르게 하는 기본형이다. 케이스 나누기는 별개의 기법이라기보다 그 흐름 도중 가정이 여러 갈래로 갈릴 때 세계를 서로소이고 빠짐없이 쪼개는 보조 장치이며, 네 기법 어디에서나 쓰인다. 대우 증명은 $\neg Q$를 가정에 놓고 $\neg P$로 가는 직접 증명, 곧 동치인 명제로 갈아탄 것이다. 귀류법은 $P$와 $\neg Q$를 동시에 가정에 쥐고 아무 모순으로나 달리는 가장 자유로운 형태여서 대우를 특수형으로 포함한다 — 모순을 $P$와 $\neg P$의 충돌로 고정하면 그것이 곧 대우다. 네 기법의 몸통은 모두 같은 기술이며, 선택은 취향이 아니라 가정과 결론의 모양이라는 신호가 결정한다. **복기.** 이 서술을 백지에 재현할 때 관계어 세 개 — "포함한다", "안에서 쓰인다", "갈아탄다" — 가 각각 어느 쌍에 붙는지만 정확하면 문장 수는 달라도 된다. 관계를 못 적고 기법을 나열만 했다면 22주차와 23주차를 다시 읽는다. ## 통과 기준과 다음 단계 - **통과**: 문제 1 만점 + 증명 문항(9~14, 16, 17) 중 6개 이상 서식$\cdot$논리 무결 + 문제 18 신호 판정 4개 중 3개 이상. - 통과 시에는 25주차(동치 증명)로 넘어간다. 이후 파트에서는 "기법"이 아니라 **대상**(iff$\cdot$존재$\cdot$집합$\cdot$함수$\cdot$극한)이 주인공이 되고, 4대 기법은 그 대상을 다루는 도구로 쓰인다. - 미달 시에는 오답 클리닉 절차를 마친 뒤 재시험한다. 미달 상태로 25주차에 들어가면 6부의 iff$\cdot$존재 증명이 4대 기법 위에 그대로 얹히므로, 남은 결손이 다음 부에 누적된다. --- **다음 주 예고:** 6부 개막 — 동치(iff) 증명. "$P \iff Q$"가 화살표 두 개라는 사실(8주차)을 증명 서식으로 승격시키고, 방향마다 다른 기법을 조합하는 법, 그리고 "다음은 모두 동치이다(TFAE)"라는 대학 교재의 표준 서식을 다룬다.