# C9주차 · 강의 — 예제 · 연습 · 해설 ## 시험 규칙 - **1부 (기법 지도 + 채점 복원, 40분)**: 이 문서에는 1부의 문항 절이 따로 없다. 복원 대상은 §1 전체 — 기법 지도의 0~4단계 골격과 증명 평가 다섯 걸음, 그리고 판정 낱말 셋이다. 만점 20점(지도 골격 12점 — 0~4단계의 다섯 단계와 2단계의 여섯 갈래, 각 1점에 3단계의 다섯 무대 1점 / 평가 절차 8점 — 다섯 걸음 각 1점, 판정 낱말 셋 각 1점), **16점 이상 통과**. §1이 그대로 정답지이므로 채점은 §1과의 대조로 한다. - **2부 (종합 시험, 150분)**: 20문항. 기본 6문항 $\times$ 1점 + 표준 8문항 $\times$ 2점 + 도전 6문항 $\times$ 3점 = **40점 만점, 32점 이상 통과**. 표준과 도전에 증명 평가 문항이 여섯 개 들어간다. - 교재$\cdot$원서$\cdot$노트 참조 금지. 해설은 채점이 끝난 뒤에만 연다. - 부분 점수 — 증명 평가 문항은 판정 낱말과 근거를 따로 채점하고 각각 절반을 배정한다. 판정만 맞고 근거가 비어 있으면 절반이다. - 기준에 미치지 못하면 아래 재학습 지도의 해당 주차를 복습하고 일주일 뒤 재시험을 본다. 통과 전에는 C10주차로 넘어가지 않는다. 1부는 §1을 백지에서 복원하는 시험이므로, 복원한 종이를 §1과 대조할 때 다음 칸을 하나씩 채운다. 칸의 수가 곧 배점이다. :::{admonition} 1부 복원 체크리스트 (백지에서 채운 뒤 §1과 대조한다) :class: quotebox **지도 골격 12점.** ✓ 0단계 판 세팅 ✓ 1단계 진리 상태 점검 ✓ 2단계 구조 판독 ✓ 3단계 무대 전개 ✓ 4단계 검증 (다섯 단계 각 1점) ✓ 2단계의 여섯 갈래 — 부정형 / $\exists$ / $\forall$$\cdot$총칭 / $\lor$$\cdot$$\land$$\cdot$"정확히 하나" / 자연수 전체의 $\forall$ / 거짓인 $\forall$ (각 1점) ✓ 3단계의 다섯 무대 — 나눗셈 $\cdot$ 합동 $\cdot$ 실수 부등식 $\cdot$ 집합 포함 $\cdot$ 데카르트 곱 (다섯을 묶어 1점) **평가 절차 8점.** ✓ 걸음 ① 명제 진위 ✓ ② 논리 ✓ ③ 가정 사용 ✓ ④ 양화사와 자격 ✓ ⑤ 전달 (각 1점) ✓ 판정 낱말 셋 — 옳음 / 틀림(어느 줄이 왜) / 불완전(무엇이 빠졌는가) (각 1점) ::: 주간 배분은 다음과 같다. 새 진도가 없으므로 제2권 5일 루틴의 원서 통독 자리가 재독으로 바뀐다. | **요일** | **할 일** | |---|---| | 1일차 | C5주차$\cdot$C6주차 재독 | | 2일차 | C7주차$\cdot$C8주차 재독 | | 3일차 | §1 암기 — 기법 지도와 증명 평가 다섯 걸음 | | 4일차 | 1부 — 기법 지도 + 채점 복원 (40분) | | 5일차 | 2부 — 종합 시험 (150분) | ## 2부 — 종합 시험 (20문항) :::{admonition} 이번 주의 채점 기준 :class: quotebox 증명 평가 문항의 답안은 판정 낱말 하나로 끝나지 않는다. "틀림"으로 판정했으면 어느 줄이 왜 틀렸는지 지목하고, "불완전"으로 판정했으면 무엇이 빠졌는지 적는다. 근거 없이 판정만 적은 채점표는 근거 없이 결론만 적은 증명과 같은 결함을 갖는다. 배점이 그 요구를 그대로 옮긴다 — 증명 평가 문항은 판정 낱말과 근거를 따로 채점하고 각각 절반을 배정한다. 판정만 맞고 근거가 비어 있으면 절반이다. 답이 아니라 근거가 점수다. ::: ### 기본 ●○○ (각 1점) **1.** (판독 6연발 — 첫수 기법 이름만) 각 명제에 §1의 기법 지도를 적용해 첫수 기법을 지목하시오. (a) $\sqrt7$은 무리수이다. (b) 정수 $n$에 대해, $n$이 홀수이면 $n^2 + 1$이 짝수이다. (c) $x^2 = 5$인 실수가 존재한다. (d) 모든 자연수 $n$에 대해 $\sum_{i=1}^n i = \frac{n(n+1)}2$. (e) 모든 정수 $n$에 대해 $n^2 + n + 3$이 짝수이다. (진리 상태 점검) (f) 어떤 두 무리수의 합은 유리수이다. **2.** 자명한 증명과 공허한 증명의 정의를 쓰고, 각각의 예를 하나씩 만드시오. **3.** 증명 평가 5단계를 쓰시오. **4.** 합동의 대수 보존(덧셈$\cdot$곱셈$\cdot$거듭제곱)을 쓰고 $3^{20} \pmod 4$를 계산하시오. **5.** 반례의 서식(부정 전개 + 구성)을 쓰고, "모든 소수는 홀수"를 반증하시오. **6.** 최소 반례법 5단계를 쓰시오. ### 표준 ●●○ (각 2점) — 증명 평가 다수 **7.** (증명) 정수 $n$에 대해, $5n + 3$이 짝수이면 $n$이 홀수임을 증명하시오 (대우). **8.** (증명 평가) 다음을 평가하시오. :::{container} quotebox **Result.** 정수 $a, b$에 대해, $a + b$가 짝수이면 $a$와 $b$가 같은 홀짝이다. **증명.** $a = 2, b = 4$이면 $a + b = 6$ 짝수이고 둘 다 짝수. 따라서 성립. ::: **9.** (증명 평가) 다음을 평가하시오. :::{container} quotebox **Result.** $\sqrt3$은 무리수이다. **증명.** $\sqrt3 = \frac ab$라 하자. 그러면 $3b^2 = a^2$이다. 따라서 $a^2$은 3의 배수이고 $a$도 3의 배수이다. $a = 3c$이면 $3b^2 = 9c^2$, $b^2 = 3c^2$이라 $b$도 3의 배수. 모순. ::: **10.** (증명) 모든 자연수 $n$에 대해 $2 \mid (n^2 + 3n)$임을 증명하시오 (경우법 또는 인수분해). **11.** (증명 평가) 다음을 평가하시오. :::{container} quotebox **Result.** 모든 실수 $x$에 대해, $x^2 > 0$이면 $x \neq 0$이다. **증명.** $x = 0$이라 하자. 그러면 $x^2 = 0$이라 $x^2 > 0$이 거짓. 따라서 성립. ::: **12.** (증명) 어떤 유리수 $r$과 무리수 $t$에 대해 $r + t$가 무리수임을 증명하시오 — 정확히는 "모든 유리수 $r$과 무리수 $t$에 대해 $r + t$가 무리수" (귀류, C7주차). **13.** (증명 평가) 다음을 평가하시오. :::{container} quotebox **Result.** 모든 자연수 $n$에 대해 $n^2 + n$이 짝수이다. **증명.** 귀납. 기저 $n=1$: $2$ 짝수 ✓. 귀납: $(n+1)^2 + (n+1) = n^2 + 3n + 2 = (n^2 + n) + (2n + 2)$. $n^2 + n$은 가정으로 짝수, $2n+2$도 짝수, 합도 짝수. ✓ ::: **14.** (증명) $A \cap (B - A) = \emptyset$임을 증명하시오 (원소 추적 — 공집합 증명은 귀류 또는 "원소가 없음"). ### 도전 ●●● (각 3점) **15.** (증명 평가 대작) 다음을 평가하시오 (여러 결함 가능). :::{container} quotebox **Result.** 정수 $n$에 대해, $n^3$이 짝수이면 $n$이 짝수이다. **증명.** $n^3$이 짝수라 하자. $n^3 = 2k$. 세제곱근을 취하면 $n = \sqrt[3]{2k}$. 이것이 짝수이므로 $n$은 짝수이다. ::: **16.** (합동 종합) $n$이 양의 정수일 때 $n^7 \equiv n \pmod 7$을 $n \in \{0, 1, \ldots, 6\}$에서 확인하시오 (페르마 소정리 $p=7$ — 각 나머지 계산; 일반형은 이 과정의 범위 밖이며 필요할 때 기성 정리로 인용한다). **17.** (귀류 + 존재) $\sqrt2 + \sqrt5$가 무리수임을 증명하고, 별도로 "$x^2 = 2 + \sqrt5$인 실수가 존재한다"를 비구성적으로 논하시오 (전자: 제곱해 $\sqrt{10}$ 고립; 후자: $2 + \sqrt5 > 0$이라 양의 제곱근 존재). **18.** (강한 귀납) 모든 정수 $n \ge 12$가 $4a + 5b$ ($a, b \ge 0$ 정수) 꼴임을 증명하시오 (S14주차 문제 19$\cdot$C8주차 방식 — 기저 $12,13,14,15$, $n+1$은 $n-3$ 재활용). **19.** (증명 평가 종합) 다음 세 제시를 각각 평가하시오. :::{container} quotebox **(a) Result.** $x > 0$이면 $x^3 > 0$. **증명.** $x = 2$면 $8 > 0$ ✓, $x = 5$면 $125 > 0$ ✓. 따라서 성립. ::: :::{container} quotebox **(b) Result.** $n$이 3의 배수이면 $n^2$이 3의 배수. **증명.** $n = 3k$면 $n^2 = 9k^2 = 3(3k^2)$이라 3의 배수. ✓ ::: :::{container} quotebox **(c) Result.** $\sqrt2$는 무리수. **증명.** $\sqrt2$가 유리수면 $\frac ab$ (기약). $2b^2 = a^2$. $a$ 짝수, $a = 2c$. $2b^2 = 4c^2$, $b^2 = 2c^2$, $b$ 짝수. 기약 모순. ✓ ::: **20.** (서술) (a) Chartrand 전반부가 S17주차의 기법 선택 결정 나무를 어떻게 재조직했는지, 특히 "진리 상태 점검"(C5주차)과 "증명 평가"가 무엇을 더했는지 세 문장 이내로 쓰시오. (b) "채점 능력이 곧 자기 검증 능력"인 이유를 자신의 언어로 두 문장 이내로 쓰시오. ## 재학습 지도 | **틀린 문항** | **복습** | |---|---| | 1, 20 | 기법 지도 (이 문서 §1) | | 2, 11 | C5주차 (자명$\cdot$공허 증명, 대우의 판정) | | 3, 8, 9, 15, 19 | C5주차 (증명 평가 다섯 걸음) | | 13 | C5주차 (증명 평가) $\cdot$ C8주차 (귀납의 서식) | | 4, 16 | C6주차 (합동의 대수와 거듭제곱 보존) | | 5 | C7주차 (반례 답안의 4단 서식) | | 6, 18 | C8주차 (강한 귀납$\cdot$최소 반례법) | | 7 | C5주차 (대우 증명) | | 12, 17 | C7주차 (귀류$\cdot$존재) | | 10, 14 | C6주차 (나눗셈$\cdot$집합의 원소 추적) $\cdot$ 1권 17주차 (경우 나누기) | ## 해설 채점이 끝나기 전에는 열지 않는다. 1부의 정답지는 §1이며, 각 항목은 §1의 두 상자와 대조해 채점한다. 각 해설은 **접근**(문제 앞에서 무엇을 떠올리는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 문제 1 **접근.** 여섯 명제 각각에 §1 지도의 1단계와 2단계를 차례로 적용한다. 요구된 것은 첫수 기법의 이름뿐이므로 계산은 한 줄도 하지 않는다. 계산을 시작했다면 문항이 요구한 범위를 벗어난 것이다. 1단계를 건너뛰면 (e)에서 걸리므로, 결론의 겉모양을 읽기 전에 "결론이 무대 전체에서 참인가 거짓인가"를 먼저 묻는 순서를 지킨다. **풀이.** (a) **귀류**. 결론에 부정형 낱말 "무리수"가 박혀 있어 부정 갈래로 내려가고, 명제가 조건문이 아니어서 뒤집을 가정이 없으므로 대우를 만들 자리가 없다. $7$이 소수이므로 C7주차 예제 2.2의 결과를 근거 ④로 인용해도 된다. (b) **직접 증명**. 부정 신호가 없고 결론 "$n^2+1$이 짝수"는 숨은 $\exists$다 — $n^2 + 1 = 2k$인 정수 $k$의 존재. 가정을 정의로 펼쳐 $n = 2k+1$을 얻고 $n^2 + 1 = 4k^2 + 4k + 2 = 2(2k^2 + 2k + 1)$로 제작하면 끝난다. (c) **구성적 존재**. 결론이 $\exists$이고 증인을 손으로 내놓을 수 있다. $x = \sqrt5$로 두고 자격($\sqrt5$는 실수)과 사건($(\sqrt5)^2 = 5$)을 확인한다. (d) **약한 귀납**. 자연수 전체에 대한 $\forall$이고, $n+1$의 좌변이 $n$의 좌변에 항 하나를 더한 것이므로 직전 항에만 의존한다. (e) **반례**. 1단계에서 걸린다. $n^2 + n = n(n+1)$은 연속한 두 정수의 곱이라 언제나 짝수이고, 따라서 $n^2 + n + 3$은 언제나 홀수다. 결론이 무대의 어떤 정수에서도 거짓이므로 명제 자체가 거짓이고, 첫수는 증명이 아니라 반례다. 아무 정수 하나를 대면 된다 — $n = 1$에서 $5$는 홀수다. (f) **구성적 존재**. 결론이 $\exists$이고 증인이 손에 잡힌다. $\sqrt2$와 $-\sqrt2$가 증인이며 합은 $0$으로 유리수다. **복기.** 여섯 중 (e)만 다른 갈래로 간 이유는 1단계를 실제로 돌렸기 때문이다. (d)의 무대는 자연수 전체이고 (e)의 무대는 정수 전체이지만, 겉모양은 똑같이 "모든 … $n$에 대해 …"이므로 2단계만 돌리면 둘 다 귀납으로 읽기 쉽다 — 지도의 귀납 갈래가 "자연수 전체에 대한 $\forall$"라 적혀 있어도, 겉모양만으로는 두 무대가 구별되지 않기 때문이다. 겉모양이 같은 두 명제를 갈라 놓는 것은 진리 상태 점검 하나뿐이다. ### 문제 2 **접근.** 두 정의의 자리를 서로 대응시켜 외우면 헷갈리지 않는다. 검사 대상이 가정이면 공허, 결론이면 자명이다. 그리고 두 정의 모두 "무대 전체"를 요구한다는 조각을 빠뜨리지 않는다 — 사례 하나로는 어느 쪽도 선언할 수 없다. **풀이.** 정의는 C5주차의 정의 1.1$\cdot$1.2다. 무대 $S$의 명제 "$P(x)$이면 $Q(x)$이다"에 대해, **자명한 증명**이란 결론 $Q(x)$가 $S$의 **모든** $x$에서 참임을 보이고 그것으로 명제의 증명을 삼는 것이다. **공허한 증명**이란 가정 $P(x)$가 $S$의 **어떤** $x$에서도 거짓임을 보이고 그것으로 명제의 증명을 삼는 것이다. 회수의 근거는 둘 다 1권 8주차의 조건문 진리표이며, 자명은 결론이 참인 행을, 공허는 가정이 거짓인 행을 인용한다. 예는 무대를 반드시 밝혀 만든다. 자명의 예 — 무대 $\mathbb{R}$에서 "$x > 0$이면 $x^2 + 1 > 0$이다". 모든 실수에서 $x^2 \ge 0$이므로 $x^2 + 1 \ge 1 > 0$이고, 결론이 무대 전체에서 참이므로 가정을 쓰지 않고 명제가 증명된다. 공허의 예 — 무대 $\mathbb{R}$에서 "$x^2 < 0$이면 $x = 5$이다". 모든 실수에서 $x^2 \ge 0$이므로 가정은 무대의 어떤 실수에서도 거짓이고, 결론을 보지 않고 명제가 증명된다. **복기.** 두 예에서 실제로 논증한 문장은 각각 "모든 실수에서 $x^2 + 1 > 0$"과 "모든 실수에서 $x^2 \ge 0$" 하나뿐이다. 자명$\cdot$공허 증명의 노동은 전부 그 한 문장에 들어 있고, 나머지는 진리표 인용이다. 무대를 밝히지 않으면 이 한 문장이 무엇에 대한 주장인지 정해지지 않으므로 판정 자체가 성립하지 않는다. ### 문제 3 **접근.** 순서에 뜻이 있으므로 순서대로 외운다. 명제 자체를 먼저 재고(①), 줄 사이 연결을 보고(②), 무엇을 증명했는지 묻고(③), 일반성을 검사하고(④), 마지막에 읽힘을 본다(⑤). 문항은 "5단계"라 적었고 C5주차는 "다섯 걸음"이라 부르지만 같은 절차다. **풀이.** ① **명제 진위** — 명제 자체가 참인가. 거짓 명제에 붙은 증명은 반드시 틀렸다. ② **논리** — 각 줄이 앞 줄$\cdot$정의$\cdot$이미 증명한 명제에서 따라오는가. ③ **가정 사용** — 가정을 실제로 소비했는가. 소비하지 않았다면 자명한 증명인지, 아니면 다른 명제를 증명한 것인지 가른다. ④ **양화사와 자격** — 특정 값 몇 개로 전칭을 대신하지 않았는가, 문자에 붙은 자격을 지켰는가. ⑤ **전달** — 문자를 소개했는가, 완결된 문장인가. 판정 낱말은 셋이다. **틀림**은 명제가 거짓이거나(①), 어느 줄이 앞 줄에서 따라오지 않거나(②), 요구된 명제가 아닌 다른 명제를 증명했을 때(③) 적는다. **불완전**은 명제가 참이고 적힌 계산에 오류도 없는데 일반성이 없거나(④) 전달이 무너져(⑤) 증명이 되지 못했을 때 적는다. **옳음**은 다섯 걸음을 모두 통과했을 때 적는다. **복기.** 다섯 걸음을 한 줄로 줄이면 "무엇을, 어떻게, 무엇으로, 얼마나 넓게, 읽히게"다. 이 다섯 물음은 남의 답안에 돌리든 자기 답안에 돌리든 같으며, 지도의 4단계가 요구하는 것이 바로 후자다. ### 문제 4 **접근.** 두 부분으로 된 문항이다. 앞은 C6주차의 합동의 대수 가운데 보존 규칙을 그대로 적는 일이고, 뒤는 그것을 계산 도구로 운용하는 일이다. 계산의 요령은 하나다 — 큰 수를 그와 합동인 **작은 대표**로 갈아 끼운다. 대표는 나머지일 필요가 없고, 계산이 쉬운 쪽을 고른다. **풀이.** 보존 규칙은 다음 셋이다. 정수 $a, b, c, d$와 양의 정수 $n$에 대해, (C4) **합 보존** — $a \equiv b$이고 $c \equiv d$이면 $a + c \equiv b + d \pmod n$이다. (C5) **곱 보존** — $a \equiv b$이고 $c \equiv d$이면 $ac \equiv bd \pmod n$이다. **거듭제곱 보존** — $a \equiv b \pmod n$이면 모든 자연수 $m$에 대해 $a^m \equiv b^m \pmod n$이다. 셋째는 (C5)를 자기 자신에 반복 적용해 얻으며, 반복의 정당화는 귀납법으로 이미 끝나 있으므로 근거 ④로 인용한다. 계산은 대표를 $-1$로 잡는다. $3 - (-1) = 4$이고 $4 \mid 4$이므로 정의 6.2에 의해 $3 \equiv -1 \pmod 4$이다. 거듭제곱 보존에 의해 $$ 3^{20} \equiv (-1)^{20} = 1 \pmod 4 $$ 이다. 따라서 $3^{20}$을 $4$로 나눈 나머지는 $1$이다. **복기.** 대표를 $3$ 그대로 두면 $3^{20}$을 직접 다뤄야 하지만, $-1$로 갈아 끼우면 지수가 짝수인지만 보면 된다. 검산은 작은 지수로 한다 — $3^2 = 9 = 4 \cdot 2 + 1$이므로 $3^2 \equiv 1 \pmod 4$이고, $3^{20} = (3^2)^{10} \equiv 1^{10} = 1$이다. 두 경로가 같은 답을 준다. ### 문제 5 **접근.** 반례는 "예를 하나 들었다"가 아니라 **부정 명제의 증명**이다. 그러므로 답안의 첫 줄은 예가 아니라 무엇을 증명할지의 선언이어야 한다. C7주차의 4단 서식을 그대로 따르면 빠지는 칸이 없다. **풀이.** 서식은 네 걸음이다. ① **부정 전개** — "명제가 거짓임을 보인다. 곧 가정을 만족하면서 결론을 위반하는 대상이 존재함을 증명한다"라고 선언한다. ② **증인 제시** — 값을 실제로 내놓는다. ③ **자격 검증** — 그 증인이 무대에 있고 가정을 만족함을 계산으로 보인다. ④ **사건 검증** — 그 증인에서 결론이 위반됨을 계산으로 보인다. 이제 "모든 소수는 홀수이다"를 반증한다. ① 이 명제가 거짓임을 보인다. 곧 소수이면서 홀수가 아닌 정수가 존재함을 증명한다. ② $p = 2$로 두자. ③ $2$의 양의 약수는 $1$과 $2$뿐이므로 $2$는 소수이고, 가정을 만족한다. ④ $2 = 2 \cdot 1$이므로 $2$는 짝수이고, 따라서 홀수가 아니다. 곧 결론이 위반된다. 그러므로 명제는 거짓이다. $\blacksquare$ **복기.** 걸음 ③을 빼면 무대 밖 대상이나 가정을 만족하지 않는 대상이 반례로 통과한다. 이 문항에서 ③에 해당하는 문장은 "$2$는 소수이다"이며, 이 한 줄이 없으면 답안은 "$2$는 짝수다"라는 참인 문장을 적었을 뿐 명제를 흔들지 못한다. ### 문제 6 **접근.** 최소 반례법은 귀납의 귀류판이다. 그러므로 서식의 뼈대는 귀류의 4단(부정 가정 $\to$ 유도 $\to$ 모순 $\to$ 회수)이고, 그 안에 최소원리가 들어와 "최소 반례보다 작은 곳은 전부 참"이라는 재료를 만들어 준다. 다섯 걸음을 외울 때 이 대응을 함께 붙여 두면 순서가 흔들리지 않는다. **풀이.** ① $P(n)$이 거짓인 $n$, 곧 반례가 있다고 가정한다(귀류의 개시). ② 반례들의 모임은 공집합이 아니고 아래로 유계인 정수 집합이므로, 최소원리에 의해 **최소 반례** $m$이 존재한다(C8주차 정의 8.3의 걸음 ②). 무대가 자연수로 한정되지 않으므로 "자연수의 부분집합이라서"로 줄여 적으면 $n_0$이 $0$ 이하인 명제에서 근거가 성립하지 않는다. ③ $m > n_0$임을 보인다 — 기저에서 $n_0$은 반례가 아님이 확인되므로 최소 반례가 $n_0$일 수는 없다. 그리고 $m$의 최소성에서 $P(m-1)$(또는 $m$보다 작은 것들 전부)이 참임을 얻는다. ④ 그 재료로 $P(m)$을 유도해 "$m$이 반례"와 모순을 만든다. ⑤ 따라서 반례는 없고, 모든 $n$에 대해 $P(n)$이 참이다. **복기.** 걸음 ③이 두 가지 일을 한꺼번에 한다는 점이 이 서식의 요령이다 — 기저를 소비해 최소 반례의 위치를 $n_0$ 위로 밀어 올리고, 동시에 최소성으로부터 귀납 가정에 해당하는 재료를 얻는다. 약한 귀납의 "기저 + $P(n) \Rightarrow P(n+1)$"이 여기서 "$n_0$은 반례가 아님 + 최소 반례에서 모순"으로 뒤집혀 나타난다. ### 문제 7 **접근.** 결론 "$n$이 홀수"는 숨은 $\exists$이므로 직접 증명도 가능해 보이지만, 가정 "$5n+3$이 짝수"에서 $n$의 꼴을 뽑아내려면 나눗셈이 필요하다. 반면 대우를 잡으면 가정이 "$n$이 짝수"가 되어 $n = 2k$라는 등식이 곧바로 손에 들어온다. 가정 쪽에 정의를 펼칠 등식이 생기는 방향을 고르는 것이 판정 기준이다. **풀이.** 대우를 증명한다. 대우는 "$n$이 홀수가 아니면 $5n+3$이 짝수가 아니다", 곧 "$n$이 짝수이면 $5n+3$이 홀수이다"이다. $n$을 짝수인 정수라 하자. 정의에 의해 $n = 2k$인 정수 $k$가 존재한다. 그러면 $$ 5n + 3 = 5(2k) + 3 = 10k + 3 = 2(5k + 1) + 1 $$ 이다. $k$가 정수이므로 $5k + 1$도 정수이고(근거 ②), 따라서 $5n + 3$은 홀수의 정의를 만족한다. 대우가 증명되었으므로 원명제도 참이다. $\blacksquare$ **복기.** 핵심 변형은 $10k + 3$을 $2(5k+1) + 1$로 묶는 한 줄이다. 정의가 요구하는 꼴이 $2 \times (\text{정수}) + 1$이므로, $3$을 $2 + 1$로 쪼개 앞의 $2$를 괄호 안으로 보내는 조작이 필요하다. 검산은 $k = 3$으로 한다 — $n = 6$이면 $5n + 3 = 33 = 2 \cdot 16 + 1$이고 $5k + 1 = 16$이다. ### 문제 8 **접근.** 제시된 답안이 다룬 것은 정수 쌍 하나뿐인데 명제는 모든 정수 쌍에 대한 전칭이다. 다섯 걸음 중 ④가 정확히 이 어긋남을 잡는다. 판정 낱말을 고를 때는 "적힌 것 중 거짓이 있는가"를 먼저 묻는다 — 없으면 틀림이 아니라 불완전이다. **풀이.** 판정은 **불완전**이다. 걸린 걸음은 ④ 양화사와 자격이다. 명제는 참이고(① 통과), $a = 2, b = 4$에서 $a+b = 6$이 짝수이며 둘 다 짝수라는 계산에도 거짓인 문장은 없다(② 통과). 그러나 확인된 것은 무수히 많은 정수 쌍 가운데 한 쌍뿐이고, 나머지 전부에 대한 논증이 없다. 채점표에는 "임의의 정수 쌍을 잡는 첫 문장이 없다"라고 적는다. 올바른 답안은 대우와 경우 나누기로 만든다. 대우는 "$a$와 $b$가 다른 홀짝이면 $a+b$가 홀수이다"이다. $a$와 $b$가 다른 홀짝인 정수라 하자. 경우 1: $a$가 짝수이고 $b$가 홀수라 하자. 정의에 의해 $a = 2k$, $b = 2l+1$인 정수 $k, l$이 존재하므로 $a + b = 2k + 2l + 1 = 2(k+l) + 1$이고, $k+l$이 정수이므로 $a+b$는 홀수다. 경우 2: $a$가 홀수이고 $b$가 짝수라 하자. $a = 2k+1$, $b = 2l$이므로 $a + b = 2(k+l) + 1$로 같은 결론에 닿는다. "다른 홀짝"은 이 두 경우로 빠짐없이 덮이므로 대우가 증명되었고, 원명제도 참이다. $\blacksquare$ **복기.** 대우를 쓰지 않는 경로도 있다. $a + b = 2m$이라 하면 $a - b = (a+b) - 2b = 2m - 2b = 2(m-b)$이므로 차도 짝수이고, 차가 짝수인 두 정수는 같은 홀짝이다. 어느 경로든 답안의 첫 문장이 "임의의 정수 $a, b$를 잡자"로 시작한다는 점이 제시된 답안과의 결정적 차이다. ### 문제 9 **접근.** 귀류법 답안의 채점에서 가장 먼저 보는 자리는 마지막 줄이다 — 유도된 결과가 정말로 앞에 놓인 가정과 충돌하는가. 이 답안은 "$a$도 3의 배수, $b$도 3의 배수"를 유도한 뒤 "모순"이라 적는다. 그 두 문장이 서로 충돌하려면 시작 줄에 무엇이 있어야 했는지를 묻는다. **풀이.** 판정은 **틀림**이다. 걸린 걸음은 ②이고, 어긋난 줄은 마지막 "모순" 한 줄이다. 개시 줄에 **기약 조건**이 없다. "$\sqrt3 = \frac ab$라 하자"에는 $a$와 $b$가 서로소라는 조건이 붙어 있지 않으므로, "$a$도 3의 배수이고 $b$도 3의 배수"라는 유도 결과는 아무것과도 충돌하지 않는다. $a = 6$, $b = 6$처럼 둘 다 3의 배수인 정수 쌍은 얼마든지 있다. 곧 마지막 "모순"은 앞 줄에서 따라오지 않으며, 이것이 걸음 ②가 잡는 결함이다. 채점표에는 "어느 줄이 왜"를 적는다 — "마지막 줄 '모순'이 앞 줄에서 따라오지 않는다. 개시 줄에 기약 조건이 없으므로 'a도 3의 배수, b도 3의 배수'는 아무것과도 충돌하지 않는다." 부수 결함이 하나 더 있다. "$a^2$이 3의 배수이면 $a$도 3의 배수"는 유클리드 보조정리($p = 3$)이며 근거 ④로 인용해야 하는 기성 결과인데 아무 표시 없이 쓰였고, $b$에 대한 같은 단계도 마찬가지다. 다만 미인용 기성 정리는 그 자체로 판정을 바꾸지 않는 **근거 표시 보완**이다 — 같은 결함만 가진 문제 19(c)의 판정이 옳음(보완 필요)인 것이 그 증거다. 이 답안의 판정을 정한 것은 기약 조건 누락 하나다. 문제 8$\cdot$19(a)의 "불완전"과 갈리는 자리가 여기다. 그쪽은 적힌 줄이 모두 참이고 빠진 것이 일반 논증뿐이지만, 이 답안은 실제로 적힌 마지막 줄 자체가 근거 없는 주장이다. 앞 줄에서 따라오지 않는 줄이 답안에 남아 있으면, 빠진 것을 채우는 문제가 아니라 적힌 것을 지목하는 문제이므로 판정은 틀림이다. 결함을 고친 답안은 다음과 같다. $\sqrt3$이 유리수라 가정하자. 그러면 $\sqrt3 = \frac ab$인 정수 $a$와 0이 아닌 정수 $b$가 존재하고, 약분하여 $a$와 $b$는 서로소라 잡을 수 있다. 양변을 제곱하고 $b^2$을 곱하면 $a^2 = 3b^2$이다. 따라서 $3 \mid a^2$이고, 유클리드 보조정리($p=3$)에 의해 $3 \mid a$이다. $a = 3c$인 정수 $c$를 잡으면 $9c^2 = 3b^2$, 곧 $b^2 = 3c^2$이므로 $3 \mid b^2$이고 다시 보조정리로 $3 \mid b$이다. 그런데 $a$와 $b$를 서로소로 잡았으므로 둘이 공약수 $3$을 가질 수는 없다 — 모순이다. 따라서 $\sqrt3$은 무리수이다. $\blacksquare$ **복기.** 무리수 명제의 귀류에서 모순의 산지는 언제나 개시 줄에 심어 둔 조건이다. 기약 조건은 답안을 다듬는 장식이 아니라 마지막 줄의 근거이며, 그것을 빠뜨린 답안은 마지막 줄만 근거를 잃는 것이 아니라 증명 전체가 아무것도 결론짓지 못한다. ### 문제 10 **접근.** 결론 "$2 \mid (n^2+3n)$"은 숨은 $\exists$다 — $n^2 + 3n = 2k$인 정수 $k$의 존재. 그러므로 후진면이 요구하는 것은 "$2 \times (\text{정수})$" 꼴의 제작이다. 가정에는 $n$의 홀짝에 대한 정보가 없으므로 그 정보를 스스로 만들어야 하고, 그 장치가 경우 나누기다. **풀이.** $n$을 자연수라 하자. $n^2 + 3n = n(n+3)$이다. $n$의 홀짝으로 경우를 나눈다. 경우 1: $n$이 짝수라 하자. 정의에 의해 $n = 2k$인 정수 $k$가 존재하므로 $n(n+3) = 2k(n+3) = 2\bigl(k(n+3)\bigr)$이고, $k(n+3)$은 정수이므로(근거 ②) $2 \mid (n^2+3n)$이다. 경우 2: $n$이 홀수라 하자. $n = 2k+1$인 정수 $k$가 존재하므로 $n + 3 = 2k + 4 = 2(k+2)$이고, 따라서 $n(n+3) = 2\bigl(n(k+2)\bigr)$이며 $n(k+2)$는 정수다. 곧 $2 \mid (n^2+3n)$이다. 모든 자연수는 짝수이거나 홀수이므로 두 경우가 전체를 빠짐없이 덮고, 어느 경우든 결론이 성립한다. $\blacksquare$ **복기.** 경우를 나누지 않는 경로도 있다. $n^2 + 3n = (n^2 + n) + 2n = n(n+1) + 2n$이고 $n(n+1)$은 연속한 두 정수의 곱이라 짝수이므로, 짝수 둘의 합으로 결론이 나온다. 어느 경로를 택하든 답안에 반드시 남겨야 하는 문장은 전수성 확인 — "모든 자연수는 짝수이거나 홀수이다" — 이다. 이 한 줄이 없으면 두 계산은 두 개의 특수 사례로 읽힌다(1권 17주차). ### 문제 11 **접근.** 제시된 답안이 첫 줄에서 "$x = 0$이라 하자"라고 적은 것을 보고 곧바로 "결론을 가정했다"고 판정하기 쉽다. 그러나 $x = 0$은 결론이 아니라 **결론의 부정**이다. 걸음 ③은 "무엇을 증명했는가"를 묻는 걸음이므로, 이 답안이 실제로 증명한 명제가 무엇인지 먼저 적어 보고 그것이 원명제의 대우인지 확인한다. **풀이.** 판정은 **옳음(전달 보완 필요)**이다. 원명제는 "$x^2 > 0$이면 $x \neq 0$이다"이고, 그 대우는 "$x = 0$이면 $x^2 > 0$이 아니다"이다. 제시된 답안은 $x = 0$을 가정해 $x^2 = 0$을 얻고 그로부터 "$x^2 > 0$이 거짓"을 유도했으므로, 정확히 그 대우를 증명했다. 걸음 ①~④는 통과한다 — 명제는 참이고, 각 줄이 앞 줄에서 따라오며, 가정에 해당하는 $x = 0$을 실제로 소비했고, 특정 값 몇 개로 전칭을 대신하지도 않았다. 남는 것은 걸음 ⑤다. 답안 어디에도 "대우를 증명한다"는 선언이 없고, 마지막의 "따라서 성립"이 무엇에서 무엇으로 건너간 것인지 적혀 있지 않다. 그런데 빠진 것은 그 선언 한 줄뿐이고, 그 한 줄은 답안의 흐름에서 **유일하게** 복원된다 — 결론의 부정 $x = 0$만 가정해 $x^2 > 0$의 부정을 유도한 형태는 대우 외에 달리 읽을 수 없다. 빠진 문장을 읽는 쪽이 유일하게 복원할 수 있으므로 판정은 불완전이 아니라 옳음(보완 필요)이다(C5주차 §1.6의 판정 규칙). 복원이 유일하지 않은 경우는 다르다 — 문제 13처럼 무엇에 대한 귀납인지조차 적히지 않은 표기 결함이 여럿 겹치면 채점자가 재구성한 문장이 답안에 있는 문장과 같다는 보장이 사라진다. 보완한 형태는 다음과 같다 — "대우를 증명한다. 대우는 '$x = 0$이면 $x^2 > 0$이 아니다'이다. $x = 0$이라 하자. 그러면 $x^2 = 0$이므로 $x^2 > 0$이 거짓이다. 대우가 증명되었으므로 원명제도 참이다." **복기.** 대우 증명과 귀류 증명은 첫 줄의 겉모양이 비슷해 채점에서 자주 뒤섞인다. 가르는 기준은 하나다 — 결론의 부정만 가정했으면 대우이고, 가정과 결론의 부정을 함께 놓았으면 귀류다. 이 답안은 $x^2 > 0$을 가정 목록에 올린 적이 없으므로 대우다. ### 문제 12 **접근.** 결론 "$r+t$가 무리수"는 부정형이다. 부정형 결론에는 만들 등식이 없으므로 직접 증명이 시작되지 않는다. 지도의 2단계가 지목하는 처방은 둘 — 대우 또는 귀류다. 여기서는 부정을 가정 목록에 올리는 순간 "$r+t$는 유리수"라는 등식이 손에 들어오므로 귀류가 유리하다. **풀이.** $r$을 유리수, $t$를 무리수라 하고, 결론을 부정해 $r + t$가 유리수라 가정하자. 그러면 $$ t = (r + t) - r $$ 이고, 우변은 유리수에서 유리수를 뺀 것이다. 유리수의 차는 유리수이므로(두 유리수를 $\frac pq$와 $\frac uv$로 쓰면 차는 $\frac{pv - uq}{qv}$이고 분모가 0이 아닌 분수 꼴이다) $t$는 유리수다. 이것은 $t$가 무리수라는 가정과 충돌한다. 따라서 가정이 틀렸고, $r + t$는 무리수이다. $r$과 $t$가 임의였으므로 모든 유리수 $r$과 무리수 $t$에서 성립한다. $\blacksquare$ **복기.** 모순의 산지는 "유도한 것 $\leftrightarrow$ 원래 가정"이다 — 새로 얻은 "$t$는 유리수"가 문제에 주어진 "$t$는 무리수"와 부딪힌다. 이 형태에서 실제로 한 일은 등식 하나를 옮겨 쓴 것뿐이며, 무리수를 다루는 답안이 계산을 시작할 수 있게 만든 것은 귀류의 개시 줄이다. 곱셈판("0이 아닌 유리수 $r$과 무리수 $t$에 대해 $rt$는 무리수")도 $t = \frac{rt}r$로 같은 구조를 따르며, 이때 $r \neq 0$이라는 조건이 왜 필요한지가 그대로 드러난다. ### 문제 13 **접근.** 귀납 답안의 채점은 세 자리를 본다 — 기저가 실제로 확인되었는가, 귀납 가정이 어디서 소비되었는가, 그리고 $n+1$의 식을 $n$의 식이 드러나도록 쪼갰는가. 세 자리를 차례로 짚은 뒤에 걸음 ⑤로 넘어간다. **풀이.** 판정은 **옳음**이다. 기저는 $n = 1$에서 $1^2 + 1 = 2$가 짝수임을 확인했고, 귀납 단계는 $(n+1)^2 + (n+1) = n^2 + 3n + 2$를 $(n^2+n) + (2n+2)$로 쪼개 앞 덩어리를 귀납 가정으로 소비했다. 전개도 맞다 — $(n+1)^2 + (n+1) = n^2 + 2n + 1 + n + 1 = n^2 + 3n + 2$이고, $(n^2+n) + (2n+2)$ 역시 같은 식이다. 뒤 덩어리 $2n+2 = 2(n+1)$은 짝수이고, 짝수 둘의 합은 짝수이므로 $P(n+1)$이 얻어진다. 다섯 걸음 모두 통과한다. 보완할 곳은 걸음 ⑤ 하나다. "귀납.", "$2$ 짝수 ✓" 같은 표기는 완결된 문장이 아니고, 무엇에 대한 귀납인지($n$에 대한 귀납법인지) 선언되어 있지 않으며, 짝수 둘의 합이 짝수라는 사용된 근거도 문면에 없다. 수학은 그대로 두고 문장만 세우면 그대로 모범 답안이 된다. **복기.** 이 명제는 귀납을 쓰지 않고도 증명된다 — $n^2 + n = n(n+1)$은 연속한 두 정수의 곱이므로 짝수다. 그러나 "더 짧은 증명이 있다"는 것은 제시된 답안의 흠이 아니다. 채점은 제출된 논증이 명제를 증명하는가만 묻고, 다른 경로의 존재는 판정에 들어가지 않는다. ### 문제 14 **접근.** 결론이 "$= \emptyset$"이라는 부재 주장이므로 부정형이다. 부재를 보이는 길은 둘 — 원소를 하나 잡아 모순을 내는 귀류, 또는 "임의의 $x$에 대해 $x \notin A \cap (B-A)$"를 직접 보이는 것이다. 어느 쪽이든 3단계의 무대는 집합이고, 펼칠 정의는 교집합과 차집합의 원소 조건이다. **풀이.** 귀류로 증명한다. $A \cap (B - A) \neq \emptyset$이라 가정하면, 그 집합에 속하는 원소 $x$를 잡을 수 있다. 교집합의 정의에 의해 $x \in A$이고 $x \in B - A$이다. 차집합의 정의에 의해 $x \in B - A$는 "$x \in B$이고 $x \notin A$"를 뜻하므로, 특히 $x \notin A$이다. 그런데 앞에서 $x \in A$를 얻었다 — $x \in A$이면서 $x \notin A$인 대상이 있다는 것이므로 모순이다. 따라서 가정이 틀렸고 $A \cap (B - A) = \emptyset$이다. $\blacksquare$ **복기.** 모순의 산지는 "유도한 것 $\leftrightarrow$ 유도한 것"이다. 충돌하는 두 문장이 모두 개시 이후에 만들어졌고, 둘 다 정의를 한 번씩 펼쳐 얻은 것이다. 가정에 아무 조건도 붙지 않은 $B$가 결론에 영향을 주지 않는다는 점도 답안이 보여 준다 — $x \in B$는 한 번 얻어지고 끝까지 쓰이지 않는다. 이는 명제가 임의의 집합 $B$에서 성립함을 뜻하고, 답안이 실제로 소비한 것은 차집합 정의의 $x \notin A$ 조각뿐이다. ### 문제 15 **접근.** 결함이 여럿일 수 있다는 단서가 붙었으므로 다섯 걸음을 처음부터 끝까지 돌린다. 명제 자체는 참이므로 걸음 ①은 통과한다. 문제는 줄 사이의 연결이며, 특히 "이것이 짝수이므로"라는 구절이 어디서 왔는지를 묻는 자리에서 답안이 무너진다. **풀이.** 판정은 **틀림**이다. 걸린 걸음은 ②이고, 어긋난 줄은 마지막 줄이다. $n^3 = 2k$에서 세제곱근을 취해 $n = \sqrt[3]{2k}$를 얻은 것까지는 실수 안에서 참이다. 그러나 "이것이 짝수이므로"에는 근거가 하나도 없다. $\sqrt[3]{2k}$라는 표현이 정수인지조차 이 답안 안에서는 보장되지 않고($k = 1$이면 $\sqrt[3]{2}$는 정수가 아니다), 정수라 하더라도 그것이 짝수라는 것은 바로 이 문항이 증명하라고 요구한 결론 자체다. 곧 결론을 근거로 삼아 결론을 얻었다. 덧붙여 걸음 ⑤도 걸린다 — $k$가 어떤 자격의 수인지 소개되지 않았다. 올바른 답안은 대우로 만든다. 대우는 "$n$이 홀수이면 $n^3$이 홀수이다"이다. $n$을 홀수인 정수라 하자. 정의에 의해 $n = 2k+1$인 정수 $k$가 존재한다. 그러면 $$ n^3 = (2k+1)^3 = 8k^3 + 12k^2 + 6k + 1 = 2(4k^3 + 6k^2 + 3k) + 1 $$ 이고, $4k^3 + 6k^2 + 3k$는 정수이므로 $n^3$은 홀수다. 대우가 증명되었으므로 원명제도 참이다. $\blacksquare$ **복기.** 이 답안이 무너진 지점은 계산이 아니라 방향이다. 가정 "$n^3$이 짝수"에서 $n$의 꼴로 내려가는 통로가 없다는 것이 이 명제의 어려움이고, 대우를 잡으면 가정 쪽에 $n = 2k+1$이라는 등식이 생겨 통로가 열린다. 근호나 세제곱근으로 정수 세계를 빠져나가는 조작은, 나온 값이 다시 정수라는 보장을 답안이 스스로 대야 한다. ### 문제 16 **접근.** $2^7 = 128$부터 $6^7 = 279936$까지를 직접 나누는 것도 답이지만, 그것은 합동을 쓰지 않은 계산이다. 문항이 "합동 종합"인 이유는 큰 수를 작은 대표로 갈아 끼우는 절차를 보라는 것이다. $n^7 = n \cdot (n^3)^2$으로 쪼개면 $n^3$의 나머지만 알면 되고, $n^3$은 손으로 계산할 수 있는 크기다. 문항이 "양의 정수"라 적었으나 확인 범위에 $0$이 들어 있으므로, $0$은 나머지 $0$의 대표로 함께 확인한다. **풀이.** 쓸 근거는 C6주차의 곱 보존 (C5)와 거듭제곱 보존이다. 모든 $n$에 대해 $n^7 = n \cdot (n^3)^2$으로 쪼개고 $n^3$을 먼저 잰다. $n = 0$: $0^7 = 0 \equiv 0 \pmod 7$이다. $n = 1$: $1^7 = 1 \equiv 1 \pmod 7$이다. $n = 2$: $2^3 = 8 = 7 + 1$이므로 $2^3 \equiv 1 \pmod 7$이다. 거듭제곱 보존으로 $(2^3)^2 \equiv 1$이고, 곱 보존으로 $2^7 = 2 \cdot (2^3)^2 \equiv 2 \cdot 1 = 2 \pmod 7$이다. $n = 3$: $3^3 = 27 = 21 + 6$이므로 $3^3 \equiv 6 \equiv -1 \pmod 7$이다. 따라서 $(3^3)^2 \equiv (-1)^2 = 1$이고, $3^7 \equiv 3 \cdot 1 = 3 \pmod 7$이다. $n = 4$: $4^3 = 64 = 63 + 1$이므로 $4^3 \equiv 1 \pmod 7$이고, $4^7 \equiv 4 \cdot 1 = 4 \pmod 7$이다. $n = 5$: $5^3 = 125 = 119 + 6$이므로 $5^3 \equiv 6 \equiv -1 \pmod 7$이고, $5^7 \equiv 5 \cdot 1 = 5 \pmod 7$이다. $n = 6$: $6 \equiv -1 \pmod 7$이므로 거듭제곱 보존으로 $6^7 \equiv (-1)^7 = -1 \equiv 6 \pmod 7$이다. 일곱 나머지 전부에서 $n^7 \equiv n \pmod 7$이 확인되었다. **복기.** 검산은 직접 나눗셈으로 한다 — $2^7 = 128 = 7 \cdot 18 + 2$, $3^7 = 2187 = 7 \cdot 312 + 3$, $4^7 = 16384 = 7 \cdot 2340 + 4$, $5^7 = 78125 = 7 \cdot 11160 + 5$로 모두 일치한다. 확인한 것은 $0$부터 $6$까지 일곱 개뿐이지만, 임의의 정수는 그중 하나와 법 $7$에 대해 합동이고 거듭제곱 보존이 그 합동을 $n^7$까지 옮겨 주므로 이 일곱 줄이 실제로는 모든 정수를 덮는다. 같은 문항의 $p = 5$ 판이 C6주차 문제 12이며, 일반형 "$a^p \equiv a \pmod p$"(페르마 소정리)의 증명은 이 과정의 범위 밖이다 — 필요할 때는 기성 정리로 인용하고, 이 문항이 확인한 것은 $p = 7$ 사례 하나다. ### 문제 17 **접근.** 두 부분은 서로 다른 도구를 쓴다. 앞은 부정형 결론이므로 귀류이고, 요령은 제곱해서 무리수 조각 하나만 남기는 것이다. 뒤는 $\exists$ 결론이므로 존재 증명이며, 증인을 손으로 만들지 않고 기성 정리로 있음만 보장하는 형태다. 앞 부분에서 $\sqrt{10}$의 무리성을 인용하려면 $10$이 소수가 아니므로 C7주차 예제 2.2를 그대로 쓸 수 없고, 그 한 줄을 따로 증명해야 한다. **풀이.** 먼저 보조 사실을 증명한다. **$\sqrt{10}$은 무리수이다.** 유리수라 가정하면 $\sqrt{10} = \frac ab$인 정수 $a$와 0이 아닌 정수 $b$가 존재하고, 약분하여 서로소라 잡을 수 있다. 제곱하면 $a^2 = 10b^2$이므로 $a^2$은 짝수이고, 따라서 $a$도 짝수다(대우: $a$가 홀수면 $a^2$이 홀수). $a = 2c$를 넣으면 $4c^2 = 10b^2$, 곧 $2c^2 = 5b^2$이다. 좌변이 짝수이므로 $5b^2$이 짝수이고, $5$가 홀수이므로 $b^2$이 짝수이며 따라서 $b$도 짝수다. 그러면 $a$와 $b$가 공약수 $2$를 가져 서로소라는 설정과 모순이다. 그러므로 $\sqrt{10}$은 무리수이다. 이제 본증명이다. $s = \sqrt2 + \sqrt5$가 유리수라 가정하자. 양변을 제곱하면 $$ s^2 = 2 + 2\sqrt2\sqrt5 + 5 = 7 + 2\sqrt{10} $$ 이므로 $\sqrt{10} = \dfrac{s^2 - 7}2$이다. 우변은 유리수의 제곱에서 유리수를 뺀 뒤 유리수로 나눈 것이므로 유리수다. 그런데 방금 $\sqrt{10}$이 무리수임을 증명했으므로 모순이다. 따라서 $\sqrt2 + \sqrt5$는 무리수이다. $\blacksquare$ 존재 부분은 다음과 같다. $\sqrt5 > 0$이므로 $2 + \sqrt5 > 0$이다. "임의의 양의 실수 $a$에 대해 $x^2 = a$인 양의 실수 $x$가 존재한다"는 실수의 완비성에서 나오는 기성 정리이며, S13주차 문제 11과 S17주차 문제 18도 이 존재를 증명한 것이 아니라 같은 자격으로 인정하고 쓴 뒤 유일성만 다뤘다. 이 정리를 $a = 2 + \sqrt5$에 특수화하면 $x^2 = 2 + \sqrt5$인 양의 실수 $x$가 존재한다. $\blacksquare$ **복기.** 앞부분의 요령은 제곱 한 번으로 두 근호를 하나로 줄인 것이다 — $\sqrt2$와 $\sqrt5$를 각각 상대하려 하면 어느 쪽도 고립되지 않지만, 제곱하면 교차항에 $\sqrt{10}$ 하나만 남고 나머지는 정수가 된다. 뒷부분이 비구성적이라 불리는 이유는 존재의 근거가 값의 제시가 아니라 실수 체계의 정리이기 때문이다. 기호 $\sqrt{2+\sqrt5}$를 적을 수는 있으나, 그 기호가 가리키는 실수가 있다는 것 자체를 보장하는 것이 바로 인용한 정리다. ### 문제 18 **접근.** $n+1$을 만들려면 $4$를 더할지 $5$를 더할지 정해야 하고, $4$를 더한다면 필요한 것은 $P(n)$이 아니라 $P(n-3)$이다. 곧 $P(n+1)$을 만드는 데 쓰는 것이 $P(n)$이 아니라 $P(n-3)$, 결론에서 **네 칸 아래**의 항이므로 직전 항만 쓰는 약한 귀납이 아니라 강한 귀납이고, 참조 거리가 $4$이므로 기저도 네 개가 필요하다. 기저 개수를 정하는 근거를 답안에 적는 것까지가 이 문항의 요구다. **풀이.** $P(n)$을 "$n = 4a + 5b$인 음이 아닌 정수 $a, b$가 존재한다"로 두고, $n \ge 12$에 대해 강한 귀납법으로 증명한다. **기저.** $12 = 4 \cdot 3 + 5 \cdot 0$, $13 = 4 \cdot 2 + 5 \cdot 1$, $14 = 4 \cdot 1 + 5 \cdot 2$, $15 = 4 \cdot 0 + 5 \cdot 3$이므로 $P(12), P(13), P(14), P(15)$가 모두 참이다. **귀납 단계.** $n \ge 15$라 하고, $12$부터 $n$까지의 모든 정수에서 $P$가 참이라고 가정하자. $n \ge 15$이므로 $n - 3 \ge 12$이고, $n - 3 \le n$이므로 $n-3$은 가정의 범위 안에 있다. 강한 귀납 가정에 의해 $n - 3 = 4a + 5b$인 음이 아닌 정수 $a, b$가 존재한다. 양변에 $4$를 더하면 $$ n + 1 = 4a + 5b + 4 = 4(a+1) + 5b $$ 이고, $a + 1$과 $b$는 음이 아닌 정수이므로 $P(n+1)$이 참이다. 기저와 귀납 단계에 의해 $12$ 이상의 모든 정수 $n$에서 $P(n)$이 참이다. $\blacksquare$ **복기.** 기저를 네 개 잡은 근거는 귀납 단계가 $n-3$을 참조한다는 사실 하나다. 기저가 $12$ 하나뿐이면 $P(16)$은 $P(12)$로 만들어져 넘어가지만 $P(17)$에서 막힌다 — 그때 필요한 $P(13)$이 확보되지 않기 때문이다. 네 대응을 나란히 적으면 기저가 정확히 네 개 필요한 이유가 그대로 보인다 — $P(16) \leftarrow P(12)$, $P(17) \leftarrow P(13)$, $P(18) \leftarrow P(14)$, $P(19) \leftarrow P(15)$이고, $P(20)$부터는 앞의 넷이 재료를 대 준다. 참조 거리가 $k$인 구조에서는 기저도 $k$개가 필요하며, 이 대응이 강한 귀납 답안에서 가장 자주 비는 칸이다. 같은 명제가 S14주차 문제 19와 1권 33주차 문제 12에 있고, 검산은 $n = 23$으로 한다 — $23 - 3 = 20 = 4 \cdot 5$이므로 $24 = 4 \cdot 6$이다. ### 문제 19 **접근.** 세 제시를 같은 순서로, 각각 다섯 걸음을 돌려 판정한다. 판정 낱말을 고르기 전에 "적힌 것 중 거짓인 문장이 있는가"를 먼저 묻는다 — 없으면 틀림이 아니다. 셋 다 명제 자체는 참이므로 걸음 ①은 모두 통과하고, 갈리는 자리는 ④와 ⑤다. **풀이.** (a) 판정은 **불완전**이고, 걸린 걸음은 ④다. $x = 2$에서 $8 > 0$, $x = 5$에서 $125 > 0$은 둘 다 참인 계산이므로 거짓인 문장은 없다. 그러나 명제는 양의 실수 전체에 대한 전칭이고, 확인된 것은 두 값뿐이다. 나머지 전부에 대한 논증이 빠졌다. 올바른 답안은 임의로 잡는다 — $x > 0$인 실수 $x$를 임의로 잡자. 양수끼리의 곱은 양수이므로 $x^2 = x \cdot x > 0$이고, 다시 양수끼리의 곱이므로 $x^3 = x^2 \cdot x > 0$이다. $x$가 임의였으므로 모든 양의 실수에서 성립한다. (b) 판정은 **옳음**이다. 가정 "$n$이 3의 배수"를 정의로 펼쳐 $n = 3k$를 얻고, $n^2 = 9k^2 = 3(3k^2)$로 결론이 요구하는 "$3 \times (\text{정수})$" 꼴을 제작했다. 가정을 실제로 소비했고(③), 특정 값을 쓰지 않았으며(④), 논리에도 끊긴 자리가 없다(②). 걸음 ⑤에서 아주 작게 보완할 것은 $k$의 자격을 밝히는 일과 $3k^2$이 정수임을 한 번 적는 일이다. (c) 판정은 **옳음(보완 필요)**이다. 문제 9의 제시와 결정적으로 다른 점은 개시 줄에 "기약"이 명시되어 있다는 것이다. 그 조건이 있으므로 마지막의 "기약 모순"이 실제로 딛고 설 자리를 갖는다. $2b^2 = a^2$에서 $a$가 짝수, $a = 2c$에서 $2b^2 = 4c^2$, 곧 $b^2 = 2c^2$이므로 $b$도 짝수라는 흐름에도 끊긴 곳이 없다. 보완할 것은 "$a^2$이 짝수이면 $a$가 짝수"와 "$b^2$이 짝수이면 $b$가 짝수"라는 두 인용을 근거 ④로 표시하는 일이다. 문제 9와 달리 여기서는 미인용 두 줄이 유일한 결함이므로 판정이 바뀌지 않는다 — 미인용 기성 정리는 어느 답안에서도 근거 표시 보완일 뿐이고, 문제 9의 판정을 틀림으로 내린 것은 그 미인용이 아니라 마지막 줄이 앞 줄에서 따라오지 않는다는 사실이었다. **복기.** (a)와 (c)를 나란히 놓으면 두 판정 낱말의 경계가 보인다. 둘 다 적힌 문장 중 거짓인 것은 없지만, (a)는 다뤄야 할 대상의 대부분을 다루지 않았고 (c)는 다뤄야 할 대상을 전부 다룬 뒤 근거 표시만 생략했다. "무엇이 빠졌는가"의 크기가 판정을 가른다. ### 문제 20 **접근.** 서술 문항이므로 채점 기준을 먼저 정한다. (a)는 세 요소를 본다 — 무엇이 무엇으로 재조직되었는가, 진리 상태 점검이 더한 것, 증명 평가가 더한 것. (b)는 두 절차가 왜 같은 절차인지를 한 문장 안에 담았는지를 본다. 문장 수 제한은 요약 능력 자체를 검사하는 장치다. 넉 문장 이상으로 늘어난 답안은 재조직의 골자 대신 주차 목록을 나열한 것이 되어, 검사하려던 능력이 답안에 드러나지 않는다. **풀이.** 예시 답안은 다음과 같다. (a) Chartrand 전반부는 S17주차의 기법 선택 결정 나무를 나눗셈$\cdot$합동$\cdot$집합$\cdot$데카르트 곱이라는 네 무대 위에서 다시 배열했고, 갈래 끝에 놓인 기법은 바뀌지 않은 채 그 기법이 펼칠 정의만 무대별로 갈아 끼워졌다. 여기에 "진리 상태 점검"(C5주차)이 나무 앞에 한 단계를 더해, 가정이 언제나 거짓이거나 결론이 언제나 참인 명제를 증명 노동에 들어가기 전에 걸러 낸다. 그리고 "증명 평가"가 나무 뒤에 한 단계를 더해, 완성된 답안을 다섯 걸음으로 다시 재는 일을 절차의 일부로 만든다. (b) 남의 답안에서 결론을 가정한 줄, 특정 값 몇 개로 전칭을 대신한 줄, 가정을 한 번도 쓰지 않은 줄을 찾아내는 검사는 자기 답안에서 같은 세 가지를 찾아내는 검사와 항목이 같다. 다른 것은 채점 대상이 누구의 종이인가뿐이므로, 채점할 수 있는 항목의 수가 곧 자기 답안에서 점검할 수 있는 항목의 수다. **복기.** 이 문항의 실제 목적은 (b)에 있다. 시험장에서 마지막 5분에 할 수 있는 일은 새 증명을 쓰는 것이 아니라 이미 쓴 답안에 다섯 걸음을 돌리는 것이고, 그 5분이 회수하는 점수의 크기가 이번 주가 전반부에 더한 것이다. 자기가 자주 걸리는 걸음 번호를 적어 두면 다음 주부터의 점검이 전 범위 재독이 아니라 한두 항목의 확인으로 줄어든다. --- **다음 주 예고 (C10주차):** Chartrand 8장 — **Prove or Disprove**. 지금까지는 "증명하시오"라는 지시를 받았고, 그것은 명제가 참이라는 정보를 함께 받았다는 뜻이었다. 다음 주에는 참$\cdot$거짓이 표시되지 않은 명제를 받는다. 작은 사례로 정찰해 참$\cdot$거짓을 추측하고, 참이면 증명하고 거짓이면 반례를 댄다. 1권 29주차의 반증과 30주차의 참$\cdot$거짓 판별, 그리고 S18주차의 일반화와 반례 검문이 여기서 하나의 절차로 묶인다. 원서 8장을 통독하고 온다.