# 17주차 — 경우 나누기 (Proof by Cases)

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: 경우는 겹쳐도 되지만, 빠뜨리면 증명이 아니다.

**이 주의 위치**: 50주 과정의 17주차. 4부(직접 증명)의 마지막 기술 — 가정이 정보를 하나로 주지 않을 때 무대를 쪼개 각각을 직접 증명으로 처리한다.

**원서 대응**: BoP(Book of Proof) 4.4 (Using Cases), 4.5 (Treating Similar Cases). 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. 경우 나누기의 논리적 근거와 채점 기준 두 가지(빠짐없음 + 각 경우 완결)를 백지에 쓰고, 각 조각이 왜 필요한지 설명할 수 있다.
1. 표준 분할 3종(짝/홀, 부호, mod $d$ 나머지)을 명제에 맞게 골라 쓸 수 있다.
1. 절댓값의 케이스 정의로 절댓값 명제를 증명한다 — 삼각부등식까지 포함한다.
1. WLOG(일반성을 잃지 않고)로 대칭인 경우를 압축하고, 그 선언이 정당한지 판정할 수 있다.

본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

## 준비 운동 (16주차 복습)

1. 차–제곱 전략 3단계를 쓰시오.
1. AM–GM 부등식을 등호 조건까지 진술하시오.
1. 1주차 문제 16(연속한 두 정수의 곱 $a(a+1)$은 짝수)을 안 보고 증명하시오.

### 자주 나오는 세 가지 답 — 3번 문항

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 한쪽만 처리.** "$a = 2k$인 정수 $k$가 존재한다"로 시작해

$a(a+1) = 2\big(k(a+1)\big)$까지 간다. 이 계산은 한 줄도 틀리지 않았다. 문제는 첫 문장이다 — 가정에는 "$a$는 정수"만 있는데 "$a$는 짝수"를 몰래 얹었다. $a$가 홀수인 상황이 통째로 남는다.

- **유형 2 — 예시 확인.** $3 \times 4 = 12$, $7 \times 8 = 56$, $10 \times 11 = 110$을

적고 "항상 짝수"라 결론짓는다. 확인한 사례에 대해서는 옳다. 남는 것은 1주차 문제 18에서 이미 확인한 간격이다 — 확인하지 않은 무한히 많은 정수는 무엇이 보장하는가.

- **유형 3 — 두 경우를 나눴으나 한 줄이 없다.** "경우 1: $a$가 짝수 … 경우 2:

$a$가 홀수 …"로 양쪽을 각각 완결했다. 계산도 구조도 옳다. 빠진 것은 "모든 정수는 짝수이거나 홀수이다"라는 한 줄이다. 이번 주 채점 기준의 절반이 정확히 그 한 줄에 걸려 있다(§1.3).

## 개념 — 무대를 쪼개는 기술

### 1 정의를 풀 수 없을 때 어디서 막히는가

이번 주의 대표 명제를 15~16주차까지의 도구만으로 밀어붙여 보자.

:::{admonition} 시도 — 정의 풀기와 대수 변형만으로
:class: quotebox

명제: 모든 정수 $n$에 대해 $3 \mid (n^3 - n)$.

"$n$을 임의의 정수라 하자. $n^3 - n = n(n-1)(n+1)$로 인수분해된다.

목표는 $n^3 - n = 3 \times (\text{정수})$ 꼴을 만드는 것이다(정의 2.1).

그런데 $n$에 대해 주어진 것은 '정수'뿐이므로 풀어 쓸 정의가 없다.

따라서 $n^3 - n = \ \dots$ "
:::

여기서 멈춘다. 1~2주차의 증명은 언제나 가정의 낱말("짝수", "$a \mid b$")을 정의로 풀어 등식을 얻는 데서 시작했는데, 이 명제의 가정에는 풀 낱말이 없다.

:::{container} quotebox
**확인 1.** 멈춘 자리에서 다음 줄이 나오려면 $n$에 대해 어떤 **종류**의 정보가

필요한가. "$n$은 ~다" 꼴로 한 구절 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

"$n$은 (무엇) 꼴이다" — 곧 $n$의 생김새를 주는 **등식**이다. 1주차 §1.1과 같은

자리이되, 그때는 가정이 등식을 줄 낱말을 갖고 있었고 지금은 없다. 가정이 주지

않으면 스스로 만들어야 하고, 하나로 정할 수 없다면 가능한 꼴을 **전부** 나열해

각각에서 증명하는 길이 남는다.
:::

:::{admonition} 이 주 전체의 기준
:class: quotebox

가정이 정보를 하나로 주지 않으면, 가능한 상황 전체를 빠짐없이 나눠

각 상황에서 결론을 따로 증명한다. 그 전체가 하나의 증명이 된다.
:::

### 2 나눠 보기 — 표에서 관찰로

$n^3 - n = n(n-1)(n+1)$은 연속한 세 정수의 곱이다. 세 인수 중 어느 것이 3의 배수가 되는지 몇 개 채워 보자.

| **$n$** | **세 인수** | **3의 배수인 인수** | **$n$을 3으로 나눈 나머지** |
|---|---|---|---|
| $6$ | $5,\ 6,\ 7$ | $n = 6$ | $0$ |
| $7$ | $6,\ 7,\ 8$ | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ |
| $8$ | $7,\ 8,\ 9$ | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ |
| $11$ | $10,\ 11,\ 12$ | $\underline{\quad(5)\quad}$ | $\underline{\quad(6)\quad}$ |

:::{container} quotebox
**확인 2.** 빈칸 (1)~(6)을 채우고, "3의 배수인 인수"가 무엇에 의해 결정되는지

한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $n - 1 = 6$  (2) $1$  (3) $n + 1 = 9$  (4) $2$  (5) $n + 1 = 12$  (6) $2$.

결정하는 것은 **$n$을 3으로 나눈 나머지**다. 나머지가 0이면 $n$이, 1이면

$n-1$이, 2이면 $n+1$이 3의 배수다. 결정적인 사실은 그 나머지가 0, 1, 2

세 가지뿐이라는 것이다 — 세 경우를 각각 처리하면 모든 정수를 다룬 것이 된다.
:::

이 관찰에 정식 형식과 이름을 붙인다. 식 자체에 새로운 것은 없다 — 방금 한 판정을 논리 기호로 굳혔을 뿐이다.

### 경우 나누기의 논리적 근거 [백지 암기 대상]

:::{container} quotebox
$$
(P_1 \lor P_2) \Rightarrow Q \quad\equiv\quad (P_1 \Rightarrow Q) \land (P_2 \Rightarrow Q)
$$
:::

"$P_1$ 또는 $P_2$이면 $Q$"는 "$P_1$이면 $Q$"와 "$P_2$이면 $Q$"를 모두 주장하는 것과 같은 명제다, 로 읽는다. 기호 $\lor$는 "또는", $\land$는 "그리고"(정의 7.3), $\equiv$는 논리적 동치(정의 9.1)로 읽는다. 경우가 셋 이상이어도 같은 꼴이다:

$$
(P_1 \lor P_2 \lor P_3) \Rightarrow Q \quad\equiv\quad (P_1 \Rightarrow Q) \land (P_2 \Rightarrow Q) \land (P_3 \Rightarrow Q)
$$

:::{container} quotebox
**확인 3.** 우변의 세 조각은 $\land$(그리고)로 이어져 있다. 만약 $\lor$(또는)로

이어졌다면 증명 절차가 어떻게 달라지는가.
:::

:::{admonition} 답
:class: quotebox dropdown

"경우 중 하나에서만 $Q$를 보이면 된다"가 되어, 나머지 경우는 증명되지 않은 채

남는다. 실제 동치는 $\land$이므로 **모든** 경우에서 $Q$에 도달해야 하고,

좌변의 $\lor$가 경우들이 가정 전체를 덮는다고 말하고 있다. 이 두 요구가 곧

§1.3의 채점 기준 두 가지다. (이 동치의 진리표 증명은 문제 20에서 한다.)
:::

### 3 채점 기준 — 동치식에서 읽어 내기

§1.2의 동치식은 답안이 갖춰야 할 것 두 가지를 지정한다. 하나는 동치식의 우변에 그대로 적혀 있고, 다른 하나는 그 동치를 쓰기 위해 먼저 갚아야 하는 빚이다. 둘을 뽑아 이번 주 내내 쓰는 채점 기준으로 세운다.

### 채점 기준 두 가지 [백지 암기 대상]

:::{container} quotebox
① **빠짐없음 (exhaustive)**: 나눈 경우들이 가능한 상황 전체를 덮어야 한다.

② **각 경우 완결**: 각 경우 안에서 결론까지 도달해야 한다.
:::

기준 ②는 §1.2 동치식의 우변에서 그대로 읽힌다. 기준 ①은 동치식이 말해 주는 것이 아니라 동치식을 쓰기 위해 별도로 갚아야 하는 빚이다 — 좌변의 가정 $P_1 \lor P_2$가 실제로 성립함을 보여야 우변에서 얻은 결론을 회수할 수 있다. 조각마다 하는 일이 다르다.

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| 좌변의 "$P_1 \lor P_2$" | 가정이 그 갈래 전부임을 별도로 증명해야 함 | 기준 ① — "모든 정수는 셋 중 하나의 꼴이다" 같은 한 줄이 이 조각이다 |
| 우변의 각 "$P_i \Rightarrow Q$" | 경우 하나짜리 작은 증명 | 기준 ② — 경우마다 결론을 처음부터 다시 만든다 |
| 우변을 잇는 "$\land$" | 모든 경우가 동시에 필요 | 경우를 하나라도 증명하지 않으면 우변 전체를 얻지 못한다 — 연언은 조각이 전부 갖춰져야 손에 들어온다 |
| 세 조각에 공통인 "$Q$" | 도착점의 일치 | 경우마다 결론이 다르면 종합할 수 없다 |

**조각 삭제 실험.** 기준 ①을 지우면 무엇이 무너지는지 실제 답안으로 본다.

:::{admonition} 가짜 증명 — 빠짐없음을 지우면
:class: quotebox

명제: 모든 정수 $n$에 대해 $n^2 + 2$는 짝수이다.

"경우 1: $n = 2k$. 그러면 $n^2 + 2 = 4k^2 + 2 = 2(2k^2 + 1)$이므로 짝수이다.

경우 2: $n = 4k$. 그러면 $n^2 + 2 = 16k^2 + 2 = 2(8k^2 + 1)$이므로 짝수이다.

따라서 $n^2 + 2$는 언제나 짝수이다."
:::

:::{container} quotebox
**확인 4.** 두 경우의 계산은 각각 옳다. 그런데 결론은 거짓이다

($n = 3$이면 $n^2 + 2 = 11$). 정확히 무엇이 빠졌는가.
:::

:::{admonition} 답
:class: quotebox dropdown

두 경우가 정수 전체를 덮지 않는다 — 홀수가 통째로 새어 나갔다(경우 2는

경우 1의 일부일 뿐이라 새로 덮는 것이 없다). 덮지 못한 구간에서는 결론이

한 번도 증명되지 않았고, 그 구간에 반례($n = 3$)가 살고 있어도 이 답안은

알아채지 못한다. 각 경우의 계산이 옳은 것과 증명이 완성된 것은 다른 일이다.

이 답안도 §1.2 동치식의 정당한 인스턴스라는 점을 확인해 둔다 — $P_1$을

"$n = 2k$", $P_2$를 "$n = 4k$"로 두면 우변의 두 조건문이 각각 증명됐다.

동치식은 $P_1, P_2$가 무엇이든 성립하므로 빠짐없음을 대신 보장해 주지 않는다.

그 자리를 메우는 것이 기준 ①이다.
:::

:::{container} quotebox
**확인 5.** 위 답안에서 경우 2는 경우 1에 완전히 포함된다. 겹침 자체가

증명을 무너뜨리는가.
:::

:::{admonition} 이 주의 길잡이
:class: keybox

**답**

무너뜨리지 않는다. 겹치는 상황은 두 경우에서 각각 결론이 증명되므로 두 번

증명한 셈이고, 낭비일 뿐 논리적 결함은 아니다. 이 답안이 무너진 이유는

겹침이 아니라 **빠짐**이다. 이번 주의 핵심 문장이 이것을 한 줄로 압축한다 —

경우는 겹쳐도 되지만, 빠뜨리면 증명이 아니다.
:::

### 4 표준 분할 3종

실전에서 쓰는 분할은 대개 다음 셋 중 하나다. 셋째 열이 기준 ①을 담당한다.

| **분할** | **경우** | **빠짐없음의 근거** |
|---|---|---|
| 짝/홀 | $n = 2k$ 또는 $n = 2k + 1$ | 나눗셈 정리(나누는 수 2) |
| 부호 | $x \ge 0$ 또는 $x < 0$ (필요하면 $>,\ =,\ <$ 셋) | 실수의 삼분법 |
| mod $d$ (나누는 수 $d$) | 나누는 수가 3이면 $3q,\ 3q+1,\ 3q+2$ | 나눗셈 정리(나누는 수 3) |

:::{admonition} 지금은 인정하고 쓰는 두 사실
:class: quotebox

**나눗셈 정리 (Division Algorithm).** 정수 $a$와 자연수 $d$에 대해

$a = dq + r$, $0 \le r < d$인 정수 $q, r$이 유일하게 존재한다.

증명 없이 인정하고 쓴다(33주차 최소원리에서 증명한다). 나누는 수를 $d$로

적는 것은 이번 주의 명제들이 나뉘는 수 쪽을 $n$으로 쓰기 때문이다 —

예제 2.1의 $n$은 여기의 $a$ 자리에 들어간다.

**실수의 삼분법 (trichotomy).** 임의의 실수 $x$에 대해 $x > 0$, $x = 0$,

$x < 0$ 중 정확히 하나가 성립한다. 실수의 순서에 관한 기본 성질로 인정하고 쓴다.

두 사실이 하는 일은 같다 — 분할이 전체를 덮는다는 근거 문장을 제공한다.
:::

"mod $d$"는 "모듈로 디"로 읽고 "$d$로 나눈 나머지로 분류한 것"을 뜻한다. 합동 기호 자체는 20주차에서 다루고, 이번 주에는 나머지에 따라 $3q$, $3q+1$, $3q+2$로 적는 표기만 쓴다.

:::{container} quotebox
**확인 6.** 다음 분할은 정수 전체에 대해 빠짐없는가.

(가) $n \ge 1$ / $n \le -1$   (나) $n$이 3의 배수 / $n$이 3의 배수가 아님
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 빠짐이 있다 — $n = 0$이 어느 쪽에도 속하지 않는다.

(나) 빠짐이 없다 — 어떤 명제 $P$에 대해서든 "$P$ 또는 $\neg P$"는 참이다

(7주차 진리표에서 확인한 사실). 분할이 반드시 나눗셈 정리에서만 나오는 것은

아니고, "그렇다 / 그렇지 않다"의 이분법도 빠짐없음을 만족하는 정당한 분할이다.
:::

### 5 절댓값 — 정의가 이미 케이스인 개념

절댓값을 "부호를 뗀 값"이라는 말로만 두면 §1.1과 같은 자리에서 막힌다. 말은 계산이 되지 않는다. 절댓값의 정의는 처음부터 두 경우로 갈려 있다.

### 정의 17.1 — 절댓값 (absolute value) [백지 암기 대상]

:::{container} quotebox
실수 $x$에 대해

$$
\begin{aligned}|x| = \begin{cases} x & (x \ge 0) \\ -x & (x < 0) \end{cases}\end{aligned}
$$
:::

$|x|$는 "엑스의 절댓값"으로 읽는다. 중괄호로 묶은 두 줄은 "조건에 따라 값이 갈린다"는 표기이고, "$x$가 0 이상이면 $|x|$는 $x$, $x$가 0보다 작으면 $|x|$는 $-x$"로 읽는다. 읽는 법까지가 정의다.

이 정의는 네 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다.

| **조각** | **하는 일** | **판정에서의 역할** |
|---|---|---|
| 두 줄로 갈린 형태 | 값을 경우별로 지정 | $\lvert x \rvert$를 만나면 먼저 $x$의 부호를 판정한다 — 절댓값 증명이 경우 나누기가 되는 이유 |
| 첫 줄의 조건 "$x \ge 0$" | 첫 가지의 적용 범위 | 등호가 이 줄에 붙어 있어 $x = 0$이 첫 가지에서 처리된다 |
| 둘째 줄의 조건 "$x < 0$" | 둘째 가지의 적용 범위 | 첫 줄과 겹치지 않고, 둘을 합치면 실수 전체 — 빠짐없음이 정의 안에 들어 있다 |
| 둘째 줄의 값 "$-x$" | 부호 반전 | "마이너스를 붙인다"가 아니라 반대 부호를 취한다 — $x < 0$이므로 $-x > 0$이다 |

**조각 삭제 실험.** 둘째 줄의 조건을 "$x \le 0$"으로 바꾸면 $x = 0$이 두 줄에 동시에 걸린다. 그런데 값은 $0$과 $-0 = 0$으로 같으므로 아무 일도 일어나지 않는다 — 겹침은 무해하다. 반대로 첫 줄을 "$x > 0$"으로 바꾸고 둘째 줄을 "$x < 0$"으로 두면 $x = 0$에서 값이 **정의되지 않는다**. $|0|$이 등장하는 순간 증명이 멈춘다. 정의에서도 겹침은 무해하고 빠짐은 치명적이다.

:::{container} quotebox
**확인 7.** $|-3|$과 $|0|$을 정의의 어느 가지로 계산하는지 밝히고 값을 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$-3 < 0$이므로 둘째 가지다: $|-3| = -(-3) = 3$.

$0 \ge 0$이므로 첫 가지다: $|0| = 0$.

어느 가지인지 먼저 밝히는 것이 답안의 필수 부분이다 — 부호 판정 없이 값만

적으면 근거가 비어 있다. 애매하면 정의로 돌아간다는 1주차 §1.5의 습관이

여기서도 그대로 작동한다.
:::

정의에서 곧바로 따라 나오는 파생 사실 세 개는 이번 주 내내 재료로 쓰인다.

$$
|x| \ge 0, \qquad x \le |x|, \qquad -x \le |x|
$$

:::{container} quotebox
**확인 8.** 셋째 사실 $-x \le |x|$는 문제 5에서 둘째 사실과 같은 분할로 함께

증명한다(§6 문제 5의 복기). 이것과 둘째 사실을 합치면 왜

$-|x| \le x \le |x|$가 되는가.
:::

:::{admonition} 답
:class: quotebox dropdown

$-x \le |x|$의 양변에 $-1$을 곱하면 부등호 방향이 뒤집혀(16주차 (W3))

$x \ge -|x|$, 곧 $-|x| \le x$가 된다. 이것을 $x \le |x|$와 이어 쓰면

$-|x| \le x \le |x|$이다. 이 두 줄짜리 사실이 문제 12(삼각부등식)의 재료다.
:::

### 6 WLOG — 반복을 생략하는 장치

:::{admonition} 백지 암기 대상
:class: keybox

**WLOG — 일반성을 잃지 않고 (Without Loss Of Generality)**

남은 경우가 다룬 경우와 **문자의 역할 교환만으로** 같은 증명이 될 때,

"일반성을 잃지 않고 (조건)이라 하자"라고 선언하고 한 경우만 쓴다.
:::

WLOG는 경우를 없애는 장치가 아니라 **같은 글을 두 번 쓰지 않기 위한 장치**다. 생략의 대가로 반드시 남겨야 하는 것이 있다 — 두 경우가 실제로 이름 교환으로 서로 옮겨진다는 근거 한 줄이다. 그 줄이 없으면, 경우 하나를 정당하게 생략한 답안과 그냥 빠뜨린 답안을 구별할 방법이 없다.

:::{container} quotebox
**확인 9.** 다음 두 선언 중 WLOG가 정당한 것은 어느 쪽인가.

(가) 명제 "정수 $x, y$ 중 적어도 하나가 짝수이면 $xy$는 짝수" —

"일반성을 잃지 않고 $x$가 짝수라 하자"

(나) 명제 "모든 정수 $x, y$에 대해 $x^2 + y^2 \ge 2xy$" —

"일반성을 잃지 않고 $x = y$라 하자"
:::

:::{admonition} 답
:class: quotebox dropdown

(가)만 정당하다. (가)에서 남은 경우("$y$가 짝수")는 $x$와 $y$의 이름을 맞바꾸면

다룬 경우와 글자 그대로 같은 증명이 된다. (나)에서 남은 경우("$x \neq y$")는

이름을 어떻게 바꿔도 "$x = y$"로 옮겨지지 않는다 — 다룬 것은 전체 중 한

특수한 상황이고, 나머지가 통째로 남는다. (나)의 오류는 문제 19에서 정식으로

진단한다.
:::

### 7 근거 목록 갱신 — 칸은 그대로 네 개

1~2주차에서 세운 근거 목록의 칸은 이번 주에도 네 개다. 이번 주가 채우는 것은 ①과 ④다.

| **근거** | **이번 주에 추가되는 것** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | **정의 17.1**(절댓값) | 절댓값을 만나면 $x$의 부호로 갈라 값을 확정한다 |
| ② 닫힘성 | 변화 없음 — 16주차에서 등록한 (W4)(양수의 합$\cdot$곱은 양수)를 계속 쓴다 | "$3q^2 + 2q$는 정수이므로"를 별도 설명 없이 쓴다 |
| ③ 등식$\cdot$부등식의 성질 | 변화 없음 (부등식의 양변 연산은 16주차 (W2)(W3)) | 양변에 같은 값 더하기$\cdot$빼기(W2), 두 부등식의 변끼리 덧셈(16주차 문제 2(c) — (W2) 두 번 + 추이성), 음수를 곱할 때의 방향 반전(W3) |
| ④ 이미 증명한 명제 | 16주차 (W1)($x^2 \ge 0$)이 여기 있고, 나눗셈 정리$\cdot$삼분법(인정하고 사용), 경우 나누기의 동치(문제 20에서 증명)가 더해진다 | 분할이 전체를 덮는다는 근거를 한 줄로 인용한다 |

경우 나누기의 동치는 9주차 §1.6의 동치 목록 여덟 개에 들어 있지 않다. 문제 20에서 진리표로 증명하는 순간 근거 ④에 등록된다. 그 전까지 이번 주의 증명들은 동치를 인용하는 대신, 동치가 요구하는 두 조건(빠짐없음$\cdot$각 경우 완결)을 답안 안에서 직접 지키는 방식으로 정당화된다.

:::{container} quotebox
**확인 10.** 다음 두 문장은 각각 몇 번 근거인가.

(가) "나눗셈 정리에 의해 $n$은 $3q$, $3q+1$, $3q+2$ 중 정확히 하나의 꼴이다."

(나) "$x < 0$이므로 정의에 의해 $|x| = -x$이다."
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 근거 ④ — 인정하고 쓰는 기존 사실의 인용이다. 이 한 줄이 분할의

빠짐없음을 담당하므로, 생략하면 채점 기준 ①이 비게 된다.

(나) 근거 ① — 정의 17.1의 둘째 가지를 적용했다. 어느 가지인지 정하려면 그

앞에 부호 판정("$x < 0$이므로")이 반드시 있어야 한다. 부호 판정과 가지 적용은

한 몸이다.
:::