# C16주차 · 강의 — 예제 · 연습 · 해설

## 예제 — 세기 증명을 함께 만들기

완성된 증명을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

### 예제 2.1 — 비둘기집: 존재의 보장

**명제.** 임의의 5개 정수 중에서, 차가 4의 배수인 두 개가 존재한다.

**설계 — 쓰기 전에 정하는 두 가지.** 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 먼저 세기의 언어로 옮긴다. 비둘기집 논증에서 이 번역표는 "무엇이 물건이고 무엇이 상자인가"를 정하는 표다.

|  | **말** | **세기의 언어로** |
|---|---|---|
| 가정 (주어진 것) | 정수 5개가 주어졌다 | 물건 $5$개 |
| 목표 (만들 것) | 차가 4의 배수인 두 개가 존재 | 같은 상자에 든 두 물건이 존재 — 상자는 $\underline{\quad}$ |

:::{container} quotebox
**확인 10.** 목표 칸의 빈칸을 채워 보자. "차가 4의 배수"가 "같은 상자"가 되려면 상자를 무엇으로 정의해야 하는가. §1.3 확인 3에서 세운 기준을 그대로 쓴다.
:::

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

상자는 **4로 나눈 나머지**다. 기준은 결론에서 거꾸로 세운다 — "$a - b$가 4의 배수"와

같은 말인 조건을 찾으면 "$a$와 $b$를 4로 나눈 나머지가 같다"이고(1권 25주차 예제 2.2),

그 조건이 그대로 "같은 상자"가 되도록 나머지를 상자로 삼는다.

상자의 개수는 $4$개다 — 나머지는 $0, 1, 2, 3$뿐이다(1권 33주차 나눗셈 정리).

출발점(물건 5개)과 도착점(상자 4개에서의 겹침)이 정해졌다. 그 사이가 비둘기집이다.
:::

**1단계 — 대상을 문자로 잡는다.** 명제는 "임의의 5개 정수"에 대한 주장이므로, 특정 숫자가 아니라 문자로 다섯 개를 무대에 올린다.

:::{container} quotebox
**확인 11.** 첫 문장을 완성해 보자: "$\underline{\qquad}$을 정수라 하자."
:::

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

"$a_1, a_2, a_3, a_4, a_5$를 정수라 하자." 첨자를 쓰는 이유는 개수가 다섯이기

때문이고, 서로 다른 다섯 개의 이름이면 무엇이든 좋다. 이 다섯이 서로 다른 값이어야

한다는 조건은 명제에 없다 — 같은 값이 섞여 있어도 결론은 참이다(차가 $0$이고

$4 \mid 0$이다).
:::

**2단계 — 상자를 정의하고 물건을 넣는다.** §1.3의 걸음 ①이다. 분류를 문장으로 적고, 그 분류가 서로 겹치지 않으며 모든 물건을 덮는다는 것까지 적는다.

:::{container} quotebox
**확인 12.** 둘째 문장을 완성해 보자: "각 $a_i$를 4로 나눈 $\underline{\quad}$에 따라 분류한다. 그 값은 $\underline{\qquad}$ 중 하나이므로 상자는 $\underline{\quad}$개다."
:::

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

"각 $a_i$를 4로 나눈 **나머지**에 따라 분류한다. 그 값은 $0, 1, 2, 3$ 중 하나이므로

상자는 $4$개다." 나눗셈 정리(1권 33주차)가 나머지의 **존재와 유일성**을 함께 주므로,

이 분류는 빈틈도 겹침도 없다 — 각 $a_i$가 정확히 한 상자에 들어간다. 걸음 ①의

정당성 문장이 이 한 줄이다.
:::

**3단계 — 개수를 비교하고 원리를 인용한다.** §1.3의 걸음 ②다. 두 수를 나란히 적고 부등호를 확인한 뒤 원리의 이름을 댄다.

:::{container} quotebox
**확인 13.** 셋째 문장을 완성해 보자: "물건은 $\underline{\quad}$개, 상자는 $\underline{\quad}$개이고 $\underline{\qquad}$이므로, $\underline{\qquad}$에 의해 두 개 이상이 든 상자가 존재한다."
:::

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

"물건은 $5$개, 상자는 $4$개이고 $5 > 4$이므로, **비둘기집 원리**에 의해 두 개

이상이 든 상자가 존재한다." 근거 ④의 인용이고, 이름을 대면 한 줄로 끝난다.

$5 > 4$라는 부등식을 실제로 적는 것이 이 줄의 핵심이다 — 이 비교가 없으면

12명과 12개월의 경우와 구별되지 않는다.
:::

**4단계 — 되번역한다.** §1.3의 걸음 ③이다. 상자의 언어로 얻은 결론을 명제의 언어로 옮긴다. 이 걸음에서 인용할 출처는 §1.3에서 확인해 두었다.

:::{container} quotebox
**확인 14.** 넷째 문장을 완성해 보자: "그 상자에 든 두 정수를 $a_i, a_j$ ($i \ne j$)라 하면 둘은 4로 나눈 $\underline{\qquad}$이므로 $a_i \equiv a_j \pmod 4$, 곧 $\underline{\qquad}$이다."
:::

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

"그 상자에 든 두 정수를 $a_i, a_j$ ($i \ne j$)라 하면 둘은 4로 나눈 **나머지가

같으므로** $a_i \equiv a_j \pmod 4$, 곧 $4 \mid (a_i - a_j)$이다."

"나머지가 같다"와 "합동이다"가 같은 말임은 1권 25주차 예제 2.2이고, "합동이다"와

"차가 배수다"가 같은 말임은 합동의 정의(C6주차)다. 두 출처를 대면 이 줄이 완결된다.
:::

**5단계 — 결론을 선언한다.** 명제가 요구한 문장을 그대로 적고 증명 끝 표시를 단다.

**완성본.** 방금 만든 다섯 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다.

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| $a_1, \ldots, a_5$를 정수라 하자. | 임의의 다섯 개를 다루려면 특정 숫자가 아니라 문자가 필요하다. |
| 각 $a_i$를 4로 나눈 나머지에 따라 분류한다. 나머지는 $0, 1, 2, 3$ 중 하나이므로 상자는 4개이고, 나눗셈 정리에 의해 각 $a_i$는 정확히 한 상자에 들어간다. | 걸음 ① — 상자의 정의. 겹침도 빈틈도 없다는 정당성까지 한 문장에 넣는다(근거 ④, 1권 33주차). |
| 물건은 5개, 상자는 4개이고 $5 > 4$이므로, 비둘기집 원리에 의해 두 개 이상이 든 상자가 존재한다. | 걸음 ② — 개수 비교와 원리 인용. $5 > 4$를 실제로 적는 것이 이 줄의 근거다(근거 ④). |
| 그 상자에 든 두 정수를 $a_i, a_j$ ($i \ne j$)라 하면 둘은 4로 나눈 나머지가 같으므로 $a_i \equiv a_j \pmod 4$, 곧 $4 \mid (a_i - a_j)$이다. | 걸음 ③ — 되번역. 상자의 언어를 정수의 언어로 옮긴다(1권 25주차 예제 2.2, C6주차). |
| 따라서 차가 4의 배수인 두 정수가 존재한다. $\blacksquare$ | 명제가 요구한 문장을 그대로 선언하고 마무리한다. |

**이 다섯 줄이 "임의의" 다섯 개를 처리하는 이유.** 증명의 어느 줄도 $a_1, \ldots, a_5$가 특정 정수라는 사실을 쓰지 않았다. 쓴 것은 "정수이므로 4로 나눈 나머지를 가진다"는 자격뿐이다. 그래서 §1.1에서 막혔던 것 — 겹치는 쌍의 위치가 입력마다 달라진다 — 이 문제가 되지 않는다. 증명은 위치를 말하지 않기 때문이다.

:::{container} quotebox
**확인 15.** 이 증명이 알려 주는 것과 알려 주지 않는 것을 각각 한 줄로 적어 보자.
:::

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

알려 주는 것: 차가 4의 배수인 쌍이 **존재한다**는 사실.

알려 주지 않는 것: 그 쌍이 다섯 개 중 **어느 둘인지**. 증명 안에 $i$와 $j$를

결정하는 절차가 하나도 없기 때문이다.

이것이 C7주차의 비구성적 존재 증명이고, 비둘기집은 그 대표적인 공급원이다.

증인을 짓지 않고 존재를 얻는다는 점에서 구성법과 정확히 반대편에 있다.
:::

**자주 하는 실수: 상자를 세지 않고 넘어가기.** "나머지로 분류하면 겹치는 둘이 있다"라고만 적으면 걸음 ②가 통째로 빠진 것이다. 나머지가 몇 가지인지 세지 않으면 $5 > 4$가 성립하는지 확인할 길이 없고, 물건이 4개뿐이었다면 결론은 나오지 않는다. 상자의 개수는 반드시 숫자로 적는다.

### 예제 2.2 — 이항정리 귀납 증명

**명제.** $(x + y)^n = \sum_{k=0}^n \binom nk x^{n-k} y^k$ (모든 자연수 $n$).

이번에는 설계만 함께 하고, 본문은 완성본으로 본다.

:::{container} quotebox
**확인 16.** 귀납의 번역표를 채워 보자. 무엇에 대한 귀납인가: $\underline{\quad}$ / $P(n)$은 무엇인가: $\underline{\qquad}$ / 기저에서 보일 것: $\underline{\qquad}$ / 귀납 단계에서 가정하는 것과 보일 것: $\underline{\qquad}$
:::

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

지수 $n$에 대한 귀납이다($x$와 $y$는 고정된 수이고 귀납의 대상이 아니다).

$P(n)$은 등식 "$(x+y)^n = \sum_{k=0}^n \binom nk x^{n-k}y^k$" 자체다.

기저에서 보일 것은 $P(1)$, 곧 $(x+y)^1 = \binom10 x + \binom11 y$.

귀납 단계에서는 $P(n)$을 가정하고 $P(n+1)$을 보인다 — 곧 $(x+y)^{n+1}$을

$\sum_{k=0}^{n+1}\binom{n+1}k x^{n+1-k}y^k$로 만들어야 한다. C8주차의 표준 서식이다.
:::

:::{container} quotebox
**확인 17.** 귀납 단계에서 $(x+y)^{n+1} = (x+y)(x+y)^n$을 분배하면 합이 **두 개** 나온다. 두 합을 하나로 합치려면 무엇이 필요한가. 두 가지를 적어 보자.
:::

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

① **지표 이동** — 둘째 합의 지수가 $y^{k+1}$이므로 $j = k+1$로 바꿔 두 합의

항 모양을 맞춘다. ② **파스칼 규칙** — 지수를 맞추고 나면 같은 항의 계수가

$\binom nk + \binom n{k-1}$이 되고, 이것이 $\binom{n+1}k$로 합쳐진다.

파스칼 규칙은 1권 13주차 예제 2.2에서 세기 논증으로 이미 증명했으므로 근거 ④로

인용한다 — 인정하고 쓰는 미증명 사실이 아니다. 이번 주에는 훈련 1에서 그 증명을

이중 세기 서식으로 다시 세우고, 문제 11에서 대수적인 두 번째 증명을 붙인다.
:::

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| **(기저)** $n = 1$일 때 좌변은 $x + y$이고, 우변은 $\binom10 x^1y^0 + \binom11 x^0y^1 = x + y$이므로 $P(1)$이 성립한다. | 귀납의 출발점. 우변을 실제로 펼쳐 좌변과 대조한다. |
| **(귀납 단계)** $P(n)$이 성립한다고 가정하자. 곧 $(x+y)^n = \sum_{k=0}^n \binom nk x^{n-k}y^k$이다. | 가정을 등식으로 명시한다. 다음 줄부터 이 등식을 대입해 쓴다. |
| $(x+y)^{n+1} = (x+y)(x+y)^n = x\sum_{k=0}^n \binom nk x^{n-k}y^k + y\sum_{k=0}^n \binom nk x^{n-k}y^k$ | 지수 하나를 떼어 내고 귀납 가정을 대입한 뒤 분배한다(근거 ③). |
| $= \sum_{k=0}^n \binom nk x^{n+1-k}y^k + \sum_{k=0}^n \binom nk x^{n-k}y^{k+1}$ | 각 합 안으로 $x$와 $y$를 넣는다. 두 합의 $y$ 지수가 어긋나 있다. |
| 둘째 합에서 $j = k+1$로 지표를 바꾸면 그 합은 $\sum_{j=1}^{n+1}\binom n{j-1}x^{n+1-j}y^j$이다. | 확인 17의 ① — 지표 이동으로 두 합의 항 모양을 맞춘다. |
| 첫째 합에서 $k=0$ 항 $x^{n+1}$을, 둘째 합에서 $j = n+1$ 항 $y^{n+1}$을 떼어 내면 $(x+y)^{n+1} = x^{n+1} + \sum_{k=1}^n\left[\binom nk + \binom n{k-1}\right]x^{n+1-k}y^k + y^{n+1}$이다. | 겹치는 범위 $1 \le k \le n$에서만 두 합을 더할 수 있으므로 양 끝 항을 먼저 분리한다. |
| 파스칼 규칙에 의해 $\binom nk + \binom n{k-1} = \binom{n+1}k$이고, $x^{n+1} = \binom{n+1}0 x^{n+1}$, $y^{n+1} = \binom{n+1}{n+1}y^{n+1}$이다. | 확인 17의 ② — 계수를 합치고, 떼어 둔 두 항도 $\binom{n+1}{\cdot}$ 꼴로 되돌린다. |
| 따라서 $(x+y)^{n+1} = \sum_{k=0}^{n+1}\binom{n+1}k x^{n+1-k}y^k$이므로 $P(n+1)$이 성립하고, 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ | 도착점의 꼴과 일치함을 선언하고 귀납법으로 마무리한다. |

**복기.** 귀납 단계의 관절은 두 곳이다 — 지표 이동과 파스칼 규칙. 둘 중 하나라도 빠지면 두 합이 하나로 합쳐지지 않는다. 그리고 파스칼 규칙 자체는 §1.4의 표에서 보았듯 조합적으로도 대수적으로도 증명된다. 곧 이 증명은 대수의 전개(귀납)와 조합의 세기(파스칼)가 맞물리는 자리이며, 계수가 왜 $\binom nk$인지를 세기의 말로 설명하는 것은 §1.5의 조합적 해석이다. 같은 정리에 두 종류의 설명이 붙어 있다.

### 예제 2.3 — 이중 세기: 조합적 증명

**명제.** $\displaystyle\sum_{k=0}^n \binom nk = 2^n$.

이번에는 설계부터 스스로 해 보자. §1.6의 3단 서식에서 걸음 ①과 ②, ③을 채우면 된다.

:::{container} quotebox
**확인 18.** 이중 세기의 설계 세 칸을 채워 보자. ① 세는 대상 $X$: $\underline{\qquad}$ / ② 방법 1(좌변이 나오는 셈): $\underline{\qquad}$ / ③ 방법 2(우변이 나오는 셈): $\underline{\qquad}$
:::

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

① $X$는 원소가 $n$개인 집합 $A$의 **부분집합 전체의 모임**이다.

② 부분집합을 **크기별로** 분류한다. 크기가 $k$인 것은 정의 1.2에 의해 $\binom nk$개이고,

크기는 $0$부터 $n$까지이므로 합은 $\sum_{k=0}^n \binom nk$.

③ 부분집합 하나를 **원소별 결정의 목록**으로 본다. 각 원소마다 "넣는다"와 "뺀다"

두 선택이 있고 선택은 서로 독립이므로 곱셈 원리에 의해 $2^n$.

확인 7에서 이미 두 셈이 같은 집합을 세고 있음을 확인해 두었다.
:::

**증명 (이중 세기).** $A$를 원소가 $n$개인 집합이라 하고, $A$의 부분집합 전체의 모임을 $X$라 하자. $X$를 두 방법으로 센다.

**방법 1 (크기별로 분류).** $X$의 원소를 크기에 따라 나눈다. 부분집합의 크기는 $0, 1, \ldots, n$ 중 정확히 하나이므로 이 분류는 서로 겹치지 않고 $X$ 전체를 덮는다. 크기가 $k$인 부분집합의 개수는 정의 1.2에 의해 $\binom nk$이므로, 합의 법칙에 의해

$$
|X| = \sum_{k=0}^n \binom nk.
$$

**방법 2 (원소별 결정).** $A = \{x_1, \ldots, x_n\}$이라 하자. 부분집합 $S \subseteq A$를 정하는 일은 각 $x_i$에 대해 "$x_i$를 $S$에 넣는가 아닌가"를 정하는 일과 같다. 결정이 다르면 부분집합도 다르고 부분집합이 다르면 결정도 다르므로, 이 대응에는 빠짐도 겹침도 없다. 각 원소마다 선택지가 2개이고 결정은 $n$번이므로, 곱셈 원리에 의해

$$
|X| = \underbrace{2 \times 2 \times \cdots \times 2}_{n \text{번}} = 2^n.
$$

**결론.** 같은 유한집합 $X$를 두 방법으로 세었으므로 두 결과는 같다. 따라서 $\sum_{k=0}^n \binom nk = 2^n$이다. $\blacksquare$

이번 증명은 표 없이 **산문**으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 처음부터 끝까지 이런 산문이다. 대수 계산이 한 줄도 없다는 점도 확인해 둔다 — 같은 등식을 이항정리에 $x = y = 1$을 넣어 얻을 수도 있지만(§1.5의 표), 그 길은 등식이 **왜** 성립하는지 말해 주지 않는다. 두 길의 차이를 답안의 말로 정리하는 것이 문제 20의 (a)다.

### 관찰 — 두 증명의 같은 뼈대

예제 2.1과 2.3은 하나는 존재를, 하나는 등식을 증명했지만 뼈대가 같다. 대응표의 빈칸을 채워 보자.

| **걸음** | **예제 2.1 (비둘기집)** | **예제 2.3 (이중 세기)** |
|---|---|---|
| ① 무엇을 다루는지 선언한다 | 물건은 정수 5개, 상자는 나머지 4개 | $X$는 부분집합 전체의 모임 |
| ② 장치의 정당성을 명시한다 | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ |
| ③ 두 수를 잇고 되번역한다 | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ |

:::{container} quotebox
**확인 19.** 빈칸 (1)~(4)를 채워 보자. 각 칸은 해당 예제의 어느 문장인가.
:::

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

(1) "나눗셈 정리에 의해 각 $a_i$는 정확히 한 상자에 들어간다" — 분류에 겹침도

빈틈도 없다는 문장.

(2) "크기별 분류는 겹치지 않고 전체를 덮는다"와 "결정과 부분집합의 대응에는 빠짐도

겹침도 없다" — 두 셈 각각의 정당성 문장.

(3) "$5 > 4$이므로 비둘기집 원리에 의해 …"와 "그 두 정수는 나머지가 같으므로

$4 \mid (a_i - a_j)$이다" — 두 수를 비교하고 상자의 말을 정수의 말로 옮긴 문장.

(4) "같은 유한집합 $X$를 두 방법으로 세었으므로 두 결과는 같다" — 두 수를 등식으로

이은 문장.

두 증명 모두 정확히 이 세 걸음이고, 다른 것은 ③에서 두 수를 **부등호**로 잇느냐

**등호**로 잇느냐뿐이다.
:::

방금 확인한 뼈대에 이름을 붙인다.

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

**세기 증명의 3단 서식**

① 무엇을 세는지 선언한다(무엇이 물건이고 무엇이 상자인가, 또는 어떤 유한집합 $X$인가) $\to$ ② 세기 장치의 정당성을 명시한다(서로소이고 전체를 덮는가, 두 셈이 같은 $X$를 세는가) $\to$ ③ 두 수를 잇고(부등호면 존재, 등호면 항등식) 원래 명제의 말로 되번역한다
:::

이 ①②③은 §1.3과 §1.6의 걸음을 다시 묶은 것이므로 번호가 그대로 대응하지는 않는다 — §1.3의 걸음 ②(개수 비교)는 여기서 걸음 ③의 앞부분에 들어가고, §1.6의 걸음 ②(방법 1과 그 정당성)는 여기서 걸음 ②의 정당성 쪽만 남는다. 어느 서식의 ③인지는 인용한 절 번호로 가린다.

이 서식이 §4의 세기 문제(3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 16, 17)의 채점표다. 예제 2.2는 이 서식이 아니라 귀납의 서식(C8주차)을 따르지만, 그 안에서 쓰이는 파스칼 규칙이 다시 이 서식으로 증명된다 — 세기가 대수의 안쪽에서도 작동한다.

## 빈칸 사다리 — 지지대를 하나씩 빼며

예제의 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다 — 다 채운 뒤에 대조한다.

### 훈련 1 ●○○ — 수식과 절차의 빈칸

**명제.** 파스칼 규칙 $\binom nr = \binom{n-1}{r-1} + \binom{n-1}r$ ($1 \le r \le n-1$)을 조합적으로 증명한다.

**증명 (이중 세기).** $A$를 원소가 $n$개인 집합이라 하고, $A$의 원소 하나를 골라 $a$라 하자. $X$를 $A$의 크기 $\underline{\quad(1)\quad}$인 부분집합 전체의 모임이라 한다.

**방법 1.** 정의 1.2에 의해 $|X| = \binom nr$이다.

**방법 2.** $X$의 원소를 "$a$를 포함하는가"에 따라 두 갈래로 나눈다. 이 두 갈래는 서로 겹치지 않고 $X$ 전체를 덮는다.

- $a$를 **포함**하는 부분집합: 나머지 $n-1$개에서 $\underline{\quad(2)\quad}$개를 더 고르면 되므로 $\binom{n-1}{r-1}$개.
- $a$를 **제외**하는 부분집합: $a$가 아닌 $n-1$개에서 $\underline{\quad(3)\quad}$개를 고르면 되므로 $\binom{n-1}r$개.

합의 법칙에 의해 $|X| = \binom{n-1}{r-1} + \binom{n-1}r$이다.

**결론.** 같은 $\underline{\quad(4)\quad}$을 두 방법으로 세었으므로 $\binom nr = \binom{n-1}{r-1} + \binom{n-1}r$이다. $\blacksquare$

**검산.** $n = 4$, $r = 2$: $\binom42 = 6$이고 $\binom31 + \binom32 = 3 + \underline{\quad(5)\quad} = 6$이다.

### 훈련 2 ●●○ — 수식과 근거를 함께

이번에는 근거 문장도 빈칸이다.

**명제.** $\displaystyle\sum_{k=0}^n \binom nk 2^k = 3^n$ (모든 자연수 $n$).

**증명 (대수).** 정리 1.3에 의해 모든 수 $x, y$에 대해 $(x+y)^n = \sum_{k=0}^n \binom nk x^{n-k}y^k$이다. 이 등식은 $x, y$에 대한 $\underline{\quad(1)\quad}$이므로 특정한 값을 대입해도 성립한다(S7주차).

$x = 1$, $y = \underline{\quad(2)\quad}$을 대입하면 좌변은 $(1+2)^n = 3^n$이고, 우변은 $1^{n-k} = 1$이므로

$$
\sum_{k=0}^n \binom nk \cdot 1^{n-k} \cdot 2^k = \underline{\quad(3)\quad}
$$

이다. 따라서 $\sum_{k=0}^n \binom nk 2^k = 3^n$이다. $\blacksquare$

**같은 등식의 이중 세기 증명 (뼈대).** 세는 대상 $X$는 $n$개의 칸 각각에 세 가지 색 (흰색, 검은색, 회색) 중 하나를 칠하는 방법 전체다.

- 방법 1: 칸마다 3가지씩 독립이므로 $\underline{\quad(4)\quad}$에 의해 $3^n$가지.
- 방법 2: 흰색이 아닌 칸의 집합을 먼저 고르면 크기 $k$일 때 $\binom nk$가지이고, 그 $k$개 각각을 검은색과 회색 중 하나로 칠하는 방법이 $\underline{\quad(5)\quad}$가지다. $k$에 대해 더하면 $\sum_k \binom nk 2^k$.
- 결론의 근거: $\underline{\quad(6)\quad}$.

### 훈련 3 ●●● — 뼈대만 남기고

이번에는 §2 관찰의 3단 서식 칸을 통째로 채운다. 상자가 수나 사람이 아니라 **도형의 조각**인 경우다.

**명제.** 한 변의 길이가 $2$인 정사각형 안에 임의로 $5$개의 점을 찍으면, 거리가 $\sqrt2$ 이하인 두 점이 존재한다.

**증명의 뼈대.**

- ① 무엇이 물건이고 무엇이 상자인가: $\underline{\quad(1)\quad}$
- ② 상자가 서로 겹치지 않고 전체를 덮는다는 정당성: $\underline{\quad(2)\quad}$
- ③ 개수 비교와 원리 인용: $\underline{\quad(3)\quad}$
- ④ 되번역 — 같은 상자에 든 두 점이 왜 거리 $\sqrt2$ 이하인가: $\underline{\quad(4)\quad}$

(안내: 정사각형을 한 변의 길이가 $1$인 정사각형 네 개로 자른다. 걸음 ④에서 쓸 사실은 "한 변의 길이가 $1$인 정사각형 안의 두 점 사이의 거리는 대각선의 길이 이하"이며, 이 사실은 지금은 인정하고 쓴다. 경계에 놓인 점은 어느 조각에 넣을지 규칙을 하나 정해 두어야 걸음 ②가 성립한다 — 그 규칙도 답에 적는다.)

## 연습문제 (20문항)

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다.

비둘기집 문제는 상자의 정의와 개수 비교를 반드시 답안에 적고, 조합 항등식은 대수와 이중 세기 중 어느 길을 택했는지 밝힌다. 둘 다 되는 문제는 두 길을 모두 써 보면 좋다.

:::{admonition} 이번 주의 채점 기준
:class: quotebox

답이 아니라 **근거**가 점수다. 세기 답안에는 채점 항목이 넷이다.

① 비둘기집 답안에 **상자의 정의와 개수**가 숫자로 적혀 있는가. "겹치는 둘이 있다"는 결론이지 근거가 아니다.

② **개수 비교**($n > k$)가 실제로 적혀 있는가. 이 부등식이 없으면 12명과 12개월의 경우와 구별되지 않는다.

③ **되번역**이 있는가. "같은 상자에 둘이 있다"에서 멈춘 답안이 가장 흔하다.

④ 이중 세기 답안에 **세는 대상 $X$가 하나로 선언**되어 있고, 두 셈이 같은 $X$를 센다는 문장이 있는가.

난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.
:::

### 기본 ●○○

**1.** [백지] 비둘기집 원리, 순열$\cdot$조합 공식, 이항정리, 이중 세기의 뜻을 쓰시오.

:::{admonition} 힌트
:class: quotebox dropdown

네 항목 각각에 대해 "무엇을 반드시 적어야 하는가"를 먼저 정한다. 비둘기집은

기본형과 일반형 둘 다, 순열과 조합은 정의 문장과 공식 둘 다, 이항정리는 식과

계수의 조합적 의미 둘 다, 이중 세기는 원리 한 문장과 3단 서식이다.
:::

**2.** 계산하시오. (a) $P(5, 2)$  (b) $\binom 52$  (c) $\binom 73$  (d) $(x+y)^3$ 전개

:::{admonition} 힌트
:class: quotebox dropdown

값만 적으면 어떤 세기에서 그 값이 나왔는지가 답안에 남지 않는다. (a)는 곱셈 원리로 자리마다 몇 가지인지, (b)와 (c)는

$\frac{n!}{r!(n-r)!}$의 어느 자리에 무엇이 들어갔는지, (d)는 계수 $1, 3, 3, 1$이

어떤 $\binom3k$인지를 함께 적는다.
:::

**3.** 예제 2.1(비둘기집)을 백지 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

다섯 줄이다. 문자 잡기 $\to$ 상자 정의와 정당성 $\to$ 개수 비교와 원리 인용 $\to$

되번역 $\to$ 결론 선언. 셋째 줄에 $5 > 4$가, 넷째 줄에 $4 \mid (a_i - a_j)$가

실제로 적혀 있는지 스스로 채점한다.
:::

**4.** 빈칸 훈련을 백지에서 완성하시오.

:::{admonition} 힌트
:class: quotebox dropdown

훈련 1은 파스칼 규칙의 조합적 증명이다. 대수 계산은 한 줄도 필요 없다 —

$A$의 원소 하나를 $a$로 고정하고, 크기 $r$인 부분집합을 "$a$를 포함하는가"로

두 갈래로 나누는 것이 전부다.
:::

**5.** 예제 2.3(이중 세기 $2^n$)을 백지 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

세는 대상을 먼저 한 줄로 선언하지 않으면 나머지가 흐려진다. "$A$의 부분집합

전체의 모임을 $X$라 하자"로 시작하고, 두 방법 각각에 정당성 문장을 한 줄씩

붙인다(크기별 분류는 서로소$\cdot$전체 덮기, 원소별 결정은 빠짐$\cdot$겹침 없음).
:::

**6.** "13명 중 같은 달에 태어난 두 사람이 존재한다"를 비둘기집으로 증명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

예제 2.1과 같은 다섯 줄이고, 물건과 상자만 바뀐다. 확인 4에서 지적한 대로

마지막 되번역 줄을 빠뜨리지 않는다.
:::

### 표준 ●●○

**7.** $\binom nr = \binom n{n-r}$ (대칭)을 (a) 대수 (b) 조합적(뽑기 $\leftrightarrow$ 안 뽑기)으로 증명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

(a)는 $\binom n{n-r}$의 공식을 쓴 뒤 분모의 두 팩토리얼이 무엇이 되는지만 보면

된다 — $n - (n-r)$을 계산한다. (b)는 크기 $r$인 부분집합족과 크기 $n-r$인

부분집합족 사이의 대응을 하나 만들고, 그 대응에 빠짐도 겹침도 없음을 보인다.
:::

**8.** 이항정리로 $\sum_{k=0}^n (-1)^k \binom nk = 0$ ($n \ge 1$)을 증명하시오 ($x=1, y=-1$ 대입).

**9.** 비둘기집 응용: "임의의 $n+1$개 정수 중 차가 $n$의 배수인 두 개가 존재"를 증명하시오 (나머지 $n$개 상자, 예제 2.1의 일반화).

:::{admonition} 힌트
:class: quotebox dropdown

예제 2.1에서 $5$를 $n+1$로, $4$를 $n$으로 바꾼 것이다. 다만 상자의 개수를 셀 때

나머지가 $0, 1, \ldots, n-1$의 $n$개임을 실제로 적는다. 1권 41주차 문제 14에서

함수의 언어로 한 번 만난 명제이며, 이번에는 원리의 이름을 대고 짧게 끝낼 수 있다.
:::

**10.** 다음 제시된 증명을 평가하시오 (C5주차).

:::{container} quotebox
**Result.** 임의의 3개 정수 중 합이 짝수인 두 개가 존재한다.

**증명.** 정수를 홀$\cdot$짝으로 분류하면 2개 상자. 3개를 넣으면 어떤 상자에 2개 $\to$ 같은 홀짝. 같은 홀짝 두 정수의 합은 짝수.

(옳은가? 상자$\cdot$비둘기집$\cdot$결론 점검.)
:::

:::{admonition} 힌트
:class: quotebox dropdown

평가는 취향이 아니라 항목별 점검이다. 채점 기준의 네 항목(상자의 정의와 개수,

개수 비교, 되번역, 근거의 출처)을 하나씩 대 보고, 통과한 항목과 보강할 항목을

나누어 적는다. 마지막 문장의 "합은 짝수"가 계산으로 뒷받침되어 있는지 본다.
:::

**11.** 파스칼 규칙 $\binom nr = \binom{n-1}{r-1} + \binom{n-1}r$을 대수로 증명하시오 (빈칸은 조합적; 이번엔 팩토리얼 계산).

:::{admonition} 힌트
:class: quotebox dropdown

두 분수의 분모는 $(r-1)!\,(n-r)!$과 $r!\,(n-1-r)!$이다. 공통분모를

$r!\,(n-r)!$로 잡으면 각 항에 무엇을 곱해야 하는지가 보인다 — 앞은 $r$,

뒤는 $n-r$이다. 합치고 나면 $r + (n-r)$이 나온다.
:::

:::{admonition} 문제 12가 여는 갈래 — 방데르몽드 항등식
:class: quotebox

두 그룹으로 나뉜 사람들에서 몇 명을 뽑는 상황을 세면

$\binom{m+n}{r} = \sum_{k} \binom mk \binom n{r-k}$ 꼴의 항등식이 나오고,

이것을 방데르몽드 항등식이라 한다. 문제 12는 $r = 2$인 가장 작은 경우이고,

문제 15는 $m = n$이고 $r = n$인 경우다. 두 문제의 뼈대가 같다는 것을 문제 15에서

확인하게 되므로, 문제 12의 분류 방식을 답안에 또렷이 적어 둔다.
:::

**12.** 방데르몽드 맛보기: $\binom{m+n}2 = \binom m2 + mn + \binom n2$를 조합적으로 증명하시오 ($m + n$명에서 2명 뽑기 = 둘 다 첫 그룹 / 하나씩 / 둘 다 둘째 그룹).

:::{admonition} 힌트
:class: quotebox dropdown

세는 대상은 "$m+n$명에서 뽑은 2명으로 이루어진 집합 전체"다. 분류의 기준은

"뽑힌 2명 중 첫 그룹 출신이 몇 명인가"이고, 그 값은 $2, 1, 0$ 셋 중 하나다 —

이 한 줄이 서로소와 전체 덮기를 동시에 보증한다.
:::

:::{admonition} 문제 13이 빌려 쓰는 도구 — 다항식의 미분
:class: quotebox

$\sum_k a_k x^k$의 도함수가 $\sum_k k a_k x^{k-1}$이라는 사실과, 항등식의 양변을

미분해도 항등식이라는 사실을 문제 13에서 쓴다. 미분의 정의는 이 과정에서 아직

세우지 않았으므로(C17주차에서 다룬다) **지금은 인정하고 쓴다**. 미분을 쓰지 않는

두 번째 길도 문제에 함께 적혀 있으므로, 인정하고 쓰는 것이 꺼려지면 그쪽으로 간다.
:::

**13.** 이항정리 응용: $(1 + x)^n$의 전개로 $\binom n0 + \binom n1 x + \cdots$를 쓰고, $\sum k \binom nk = n 2^{n-1}$을 유도하시오 (미분 또는 $k\binom nk = n\binom{n-1}{k-1}$).

:::{admonition} 힌트
:class: quotebox dropdown

미분을 쓰는 길에서는 미분한 뒤에 $x$에 무엇을 넣을지가 관건이다 — 좌변에

$2^{n-1}$이 나오게 하는 값이다. 항등식 $k\binom nk = n\binom{n-1}{k-1}$을 쓰는

길에서는 그 항등식부터 팩토리얼로 확인한 뒤, 남은 합이 무엇인지 본다.
:::

:::{admonition} 문제 14가 쓰는 언어 — 관계의 두 색 분류
:class: quotebox

여섯 사람 중 두 사람을 고를 때마다 "서로 안다"와 "서로 모른다" 중 하나가 정해져

있다고 본다. 곧 상자에 들어가는 물건은 사람이 아니라 **사람의 쌍**이고, 상자는

두 종류의 관계다. 한 사람을 고정하면 그 사람이 가진 쌍이 5개이므로, 비둘기집의

일반형을 $n = 5$, $k = 2$로 쓰게 된다. 이 명제는 램지 이론의 가장 작은 사례이고,

여기서 다루는 것은 그 부등식의 한쪽뿐이다.
:::

**14.** 비둘기집 심화: "6명 중에서 서로 아는 3명 또는 서로 모르는 3명이 존재한다"(램지 $R(3,3) \le 6$)를 비둘기집으로 논하시오 (한 사람의 5개 관계 중 3개 이상이 같은 종류 — 비둘기집).

:::{admonition} 힌트
:class: quotebox dropdown

비둘기집은 시작일 뿐이고, 그 뒤에 경우 나누기가 한 번 더 온다. 같은 종류의 관계

3개를 얻은 뒤 그 세 사람 사이의 관계를 보는데, 여기서도 "그런 쌍이 하나라도

있는가 없는가"로 갈린다. 두 갈래 모두에서 결론이 나오는지 각각 확인한다.
:::

### 도전 ●●●

**15.** (이중 세기 대작) $\sum_{k=0}^n \binom nk^2 = \binom{2n}n$ (방데르몽드 특수형)을 조합적으로 증명하시오 ($2n$명을 두 그룹 $n, n$으로 나누고 $n$명 뽑기 = 첫 그룹서 $k$명$\cdot$둘째서 $n-k$명, $\binom nk \binom n{n-k} = \binom nk^2$ 합).

:::{admonition} 힌트
:class: quotebox dropdown

좌변에 제곱이 있는데 세기에는 제곱이 없다 — 제곱은 마지막에 대칭(문제 7)을

써서 만든다. 그전까지는 $\binom nk \binom n{n-k}$ 꼴로 두고 진행한다.

분류의 기준은 문제 12와 같다: 뽑힌 $n$명 중 첫 그룹 출신이 몇 명인가.
:::

**16.** (하키스틱) $\sum_{i=r}^n \binom ir = \binom{n+1}{r+1}$ (하키스틱 항등식)을 파스칼 규칙 반복 또는 조합적으로 증명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

파스칼을 반복하는 길은 $n$에 대한 귀납으로 적으면 깔끔하다 — 기저는 $n = r$이고,

귀납 단계에서 새로 더해지는 항이 파스칼의 오른쪽 두 항 중 하나가 된다.

조합적인 길에서는 $\{1, 2, \ldots, n+1\}$에서 $r+1$개를 뽑고 **최대 원소**로

분류한다. 최대 원소가 정해지면 나머지를 어디에서 뽑아야 하는지 보인다.
:::

**17.** (비둘기집 정수론) "$1$부터 $2n$까지 중 임의로 $n+1$개를 고르면, 한 수가 다른 수를 나누는 두 수가 존재한다"를 비둘기집으로 증명하시오 (각 수를 $2^a \cdot m$ ($m$ 홀수)로, 홀수 부분 $m$이 상자 — $n$개 홀수, $n+1$개 수 $\to$ 같은 $m$ 둘, 하나가 다른 것의 배수).

:::{admonition} 힌트
:class: quotebox dropdown

상자는 "$1$부터 $2n$ 사이의 홀수"다. 그 개수가 정확히 $n$개임을 세는 줄을 반드시

적는다. 그리고 같은 상자에 든 두 수를 $2^a m$과 $2^b m$으로 적었을 때 $a \ne b$인

이유를 한 줄로 밝혀야 나눗셈 결론이 나온다.
:::

**18.** (진단 종합) 다음 제시된 증명을 평가하시오.

:::{container} quotebox
**Result.** $\binom n0 + \binom n2 + \binom n4 + \cdots = 2^{n-1}$ (짝수 항 합).

**증명.** $\binom 20 + \binom 22 = 1 + 1 = 2 = 2^1$ ✓. 따라서 성립.

(특정값 $n=2$만 — 올바른 증명은 $(1+1)^n$과 $(1-1)^n$의 합/차.)
:::

:::{admonition} 힌트
:class: quotebox dropdown

결론 자체는 참이다(문제 19). 그러므로 지적할 것은 결론이 아니라 **추론**이다.

§1.7의 근거 목록에서 이 답안이 쓴 근거가 몇 번인지 찾아보고, 목록에 없다면

왜 없는지를 §0의 유형 1과 연결해 적는다. 덧붙여 $n = 0$을 넣어 보면 이 명제

자체가 어떤 조건을 필요로 하는지도 드러난다.
:::

**19.** (설계) 이항정리로 $\binom n0 + \binom n2 + \binom n4 + \cdots = 2^{n-1}$을 증명하시오 ($(1+1)^n = \sum \binom nk = 2^n$과 $(1-1)^n = \sum (-1)^k \binom nk = 0$을 더하면 짝수 항의 두 배 = $2^n$).

:::{admonition} 힌트
:class: quotebox dropdown

두 등식을 더할 때 각 항의 계수가 $1 + (-1)^k$가 된다. 이 값은 $k$의 홀짝에 따라

두 가지뿐이므로, 살아남는 항이 무엇인지가 바로 보인다. 마지막에 $n \ge 1$ 조건이

어디에서 필요했는지도 한 줄로 적는다.
:::

**20.** (서술) (a) "세는 것도 증명"임을 예제 2.3(이중 세기)으로 뒷받침하고, 조합적 증명이 대수 조작과 어떻게 다른지 세 문장 이내로. (b) 비둘기집이 "비구성적 존재 증명"(C7주차)의 대표인 이유를 예제 2.1로 두 문장 이내 설명하시오.

## 백지 재현 — 복습 프로토콜

이 과정의 한 주는 다섯 날로 나뉜다. 교안만 보는 주가 아니라 원서와 교안을 번갈아 읽는 주이므로, 백지 재현은 마지막 날에 놓인다.

| **요일** | **할 일** |
|---|---|
| 1일차 | 원서 Chartrand 13장 통독 — 모르는 문장은 표시만 하고 통과한다 |
| 2일차 | 교안 §0~§2 — 개념과 예제. 확인 상자를 연필로 먼저 채운다 |
| 3일차 | 원서 13장 재독 — 1일차에 표시한 문장을 해결하고, 원서 연습문제 몇 개를 직접 시도한다 |
| 4일차 | 교안 §3 빈칸 사다리와 §4 연습문제 20문항 |
| 5일차 | 백지 재현 1차(틀 카드)$\cdot$2차(완전 백지) + 체크리스트 |

**1차 시도 — 틀 카드 허용.** 비둘기집 논증의 3단 서식(§1.3), 이중 세기의 3단 서식(§1.6), 세기 증명의 3단 서식(§2 관찰)만 한 장에 적어 펴 놓고, 예제 2.1과 2.3을 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.

**2차 시도 — 완전 백지.** 아무것도 보지 않고 수행한다.

- [ ] 비둘기집 원리를 기본형과 일반형 둘 다 진술하고, 기본형을 귀류로 증명했다.
- [ ] 정의 1.2(순열$\cdot$조합)를 조각 그대로 쓰고, $\binom nr = \frac{n!}{r!(n-r)!}$을 순서 지우기 논증으로 유도했다.
- [ ] 이항정리를 진술하고, 계수가 $\binom nk$인 이유를 세기의 말로 한 문단 적었다.
- [ ] 이중 세기의 원리 한 문장과 3단 서식을 썼다.
- [ ] 예제 2.1을 재현했고, 상자의 개수를 숫자로 적은 줄과 되번역 줄을 손가락으로 짚었다.
- [ ] 예제 2.2를 재현했고, 지표 이동과 파스칼 규칙이 쓰인 자리를 각각 짚었다.
- [ ] 예제 2.3을 재현했고, 두 방법 각각의 정당성 문장을 빠뜨리지 않았다.
- [ ] 파스칼 규칙을 조합적(훈련 1)으로도 대수적(문제 11)으로도 증명했다.
- [ ] §1.7의 근거 목록을 재현하고, "반례를 못 찾았다"가 왜 목록 밖인지 말했다.
- [ ] 원서 13장을 두 번 읽었고, 1일차에 표시한 문장이 모두 해결되었다.

**막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다.

| **막힌 지점** | **처방** |
|---|---|
| 비둘기집 문제에서 첫 줄이 나오지 않는다 | §1.3 확인 3 — 상자는 발명하지 않고 결론을 번역해서 얻는다 |
| 상자는 잡았는데 결론이 명제의 말로 안 나온다 | §1.3의 걸음 ③과 확인 4 — 되번역 한 줄이 통째로 빠진 경우다 |
| 상자를 잡았지만 개수를 세지 못한다 | 예제 2.1의 2단계와 문제 17 — 상자의 개수는 반드시 숫자로 적는다 |
| 이중 세기에서 두 셈이 같은 것을 세는지 흐려진다 | §1.6의 걸음 ①과 삭제 실험 — 대상 $X$를 한 줄로 먼저 선언한다 |
| 경우로 나누어 더했는데 값이 어긋난다 | §1.6 확인 8 — 서로소와 전체 덮기 중 어느 쪽이 깨졌는지 확인한다 |
| 이항정리 귀납에서 두 합이 합쳐지지 않는다 | 예제 2.2 확인 17 — 지표 이동이 먼저이고 파스칼 규칙이 다음이다 |
| 조합 항등식에서 대수와 조합 중 무엇을 쓸지 못 정한다 | §2 예제 2.3의 마지막 문단과 문제 20의 (a) — 두 길의 득실을 먼저 언어화한다 |
| 무엇을 인용해도 되는지 모르겠다 | §1.7의 근거 목록 — 출처를 대면 인용, 못 대면 증명 |

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

## 해설

각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

### 빈칸 사다리 — 훈련 1

(1) $r$  (2) $r-1$  (3) $r$  (4) 유한집합 $X$ (크기 $r$인 부분집합 전체의 모임)  (5) $3$

※ 걸음 ②의 정당성이 "$a$를 포함하거나 포함하지 않거나 둘 중 하나이고 둘 다일 수는 없다"는 한 줄이다. 이 한 줄이 서로소와 전체 덮기를 동시에 준다. 그리고 $a$를 포함하는 경우에 왜 $r-1$개를 더 고르는지 — $a$가 이미 한 자리를 차지했기 때문 — 를 답안에 적어야 세기가 근거를 갖춘다.

### 빈칸 사다리 — 훈련 2

(1) 항등식  (2) $2$  (3) $3^n$  (4) 곱셈 원리  (5) $2^k$ (6) 같은 유한집합 $X$(칠하는 방법 전체)를 두 방법으로 세었으므로 두 결과는 같다

※ 대수 증명과 이중 세기 증명이 같은 등식에 나란히 붙는 사례다. 대수 쪽은 세 줄로 끝나지만 $3$이 어디서 왔는지 말하지 않고, 세기 쪽은 $3 = 1 + 2$가 "흰색이거나, 흰색이 아닌 두 색 중 하나"라는 분해임을 보여 준다. 문제 20의 (a)가 묻는 차이가 이것이다.

### 빈칸 사다리 — 훈련 3

(1) 물건은 찍은 점 5개, 상자는 정사각형을 한 변이 $1$인 정사각형 네 개로 자른 조각 4개. (2) 네 조각은 원래 정사각형을 덮고, 경계선에 놓인 점은 "왼쪽 조각$\cdot$아래쪽 조각을 우선한다"처럼 규칙을 하나 정해 정확히 한 조각에 배정한다 — 그러면 각 점이 정확히 한 상자에 들어간다. (3) 물건 $5$개, 상자 $4$개이고 $5 > 4$이므로 비둘기집 원리에 의해 두 점 이상이 든 조각이 존재한다. (4) 그 조각은 한 변의 길이가 $1$인 정사각형이고, 그 안의 두 점 사이의 거리는 대각선의 길이 $\sqrt2$ 이하다(인정하고 쓰는 사실). 따라서 거리가 $\sqrt2$ 이하인 두 점이 존재한다. $\blacksquare$

※ 상자가 수가 아니라 도형의 조각이어도 3단 서식은 그대로다. 이 문제에서 유일하게 새로운 것은 걸음 ②의 정당성 — 경계선 처리 — 이며, 이것을 빠뜨린 답안은 "한 점이 두 조각에 들어간다"는 겹침을 남긴 채 개수를 센 셈이 된다.

### 문제 1

**접근.** 백지 문항은 채점표를 먼저 정하고 시작한다. 네 항목 각각에서 "이것이 없으면 빈 답"인 조각이 무엇인지 정해 두면, 쓰다가 막혀도 어디가 비었는지 알 수 있다.

**풀이.** (모범 답안)

**비둘기집 원리.** 기본형 — $n$개의 물건을 $k$개의 상자에 넣을 때 $n > k$이면 두 개 이상이 든 상자가 존재한다. 일반형 — $n$개를 $k$개 상자에 넣으면 $\lceil n/k \rceil$개 이상이 든 상자가 존재한다. (증명은 귀류: 모든 상자가 한 개 이하이면 총수가 $k$ 이하가 되어 $n > k$와 모순.)

**순열과 조합.** 순열은 서로 다른 $n$개에서 $r$개를 순서를 따져 뽑아 나열하는 방법의 수이고 $P(n,r) = \frac{n!}{(n-r)!}$이다. 조합은 순서 없이 뽑는 방법의 수, 곧 크기 $r$인 부분집합의 개수이고 $\binom nr = \frac{n!}{r!\,(n-r)!}$이다. 두 값은 $P(n,r) = \binom nr \cdot r!$로 이어진다 — 부분집합 하나마다 나열이 $r!$개씩 있기 때문이다.

**이항정리.** $(x+y)^n = \sum_{k=0}^n \binom nk x^{n-k}y^k$이다. 계수가 $\binom nk$인 이유는, $n$개의 괄호에서 $y$를 고를 괄호 $k$개를 정하면 항 하나가 정해지기 때문이다.

**이중 세기.** 하나의 유한집합의 크기는 세는 방법과 무관하므로, 같은 집합을 두 방법으로 센 두 수는 같다. 서식은 ① 세는 대상 선언 ② 각 셈의 정당성 명시 ③ 두 수를 등식으로 이음의 세 걸음이다.

**복기.** 조각 단위로 채점한다. "비둘기집은 겹치는 게 있다는 것"처럼 뜻만 적고 $n > k$를 빠뜨리면 이 항목은 재현되지 않은 것이다 — 이번 주 답안에서 실제로 인용하는 것이 그 부등식이기 때문이다.

### 문제 2

**접근.** 값만 적으면 그 값이 어떤 세기의 결과인지 답안에서 확인할 길이 없다. 이번 주의 채점 기준대로 각 값이 어떤 세기에서 나왔는지 한 줄씩 붙인다. (b)와 (c)는 팩토리얼을 다 곱하지 말고 약분한 뒤 계산하는 편이 빠르다.

**풀이.**

(a) 5개에서 2개를 순서를 따져 뽑는다. 첫 자리에 5가지, 둘째 자리에 남은 4가지이므로 곱셈 원리에 의해 $P(5,2) = 5 \times 4 = 20$이다. 공식으로도 $P(5,2) = \frac{5!}{3!} = \frac{120}{6} = 20$이다.

(b) $\binom 52 = \frac{P(5,2)}{2!} = \frac{20}{2} = 10$이다. 공식으로는 $\binom52 = \frac{5!}{2!\,3!} = \frac{120}{2 \times 6} = 10$이다. 나눗셈 $2!$은 같은 두 원소를 두 순서로 나열한 것이 하나의 부분집합이기 때문이다.

(c) 팩토리얼을 다 곱하지 말고 약분한 뒤 계산한다.

$$
\binom 73 = \frac{7!}{3!\,4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = \frac{210}{6} = 35.
$$

(d) 정리 1.3에 $n = 3$을 넣으면 $(x+y)^3 = \binom30 x^3 + \binom31 x^2y + \binom32 xy^2 + \binom33 y^3$이고, $\binom30 = 1$, $\binom31 = 3$, $\binom32 = 3$, $\binom33 = 1$이므로

$$
(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3.
$$

**검산.** (b)와 (c)는 대칭으로 확인한다: $\binom52 = \binom53 = 10$, $\binom73 = \binom74 = 35$. (d)는 $x = y = 1$을 넣으면 좌변 $2^3 = 8$, 우변 $1+3+3+1 = 8$로 맞고, 이것이 예제 2.3의 $n=3$인 경우다.

### 문제 3

**접근.** 재현의 채점은 결론이 맞았는가가 아니라 세 걸음이 다 있는가다. 특히 "$5 > 4$"와 "$4 \mid (a_i - a_j)$" 두 식이 답안 어딘가에 문자 그대로 적혀 있어야 한다.

**풀이.** $a_1, a_2, a_3, a_4, a_5$를 정수라 하자. 각 $a_i$를 4로 나눈 나머지에 따라 분류한다. 나눗셈 정리(1권 33주차)에 의해 나머지는 $0, 1, 2, 3$ 중 정확히 하나이므로 상자는 4개이고 각 $a_i$는 정확히 한 상자에 들어간다. 물건은 5개, 상자는 4개이고 $5 > 4$이므로, 비둘기집 원리에 의해 두 개 이상이 든 상자가 존재한다. 그 상자에 든 두 정수를 $a_i, a_j$ ($i \ne j$)라 하면 둘은 4로 나눈 나머지가 같으므로 $a_i \equiv a_j \pmod 4$이고, 곧 $4 \mid (a_i - a_j)$이다. 따라서 차가 4의 배수인 두 정수가 존재한다. $\blacksquare$

**복기.** 자가 채점 항목은 넷이다 — ① 문자로 다섯 개를 잡았는가 ② 상자의 개수를 숫자 4로 적었는가 ③ $5 > 4$와 원리의 이름이 함께 있는가 ④ 마지막 되번역 줄이 있는가. 셋째와 넷째가 가장 자주 빠진다.

### 문제 4

**접근.** 훈련 1은 파스칼 규칙의 조합적 증명이다. 대수 계산은 한 줄도 필요 없고, 필요한 것은 "원소 하나를 고정해 두 갈래로 나눈다"는 분류 하나뿐이다. 분류를 세운 뒤에는 각 갈래에서 남은 자리가 몇 개인지만 세면 된다.

**풀이.** $A$를 원소가 $n$개인 집합이라 하고, $a \in A$를 하나 고정하자. $X$를 $A$의 크기 $r$인 부분집합 전체의 모임이라 한다.

방법 1: 정의 1.2에 의해 $|X| = \binom nr$이다.

방법 2: $X$의 원소를 "$a$를 포함하는가"에 따라 나눈다. 임의의 부분집합은 $a$를 포함하거나 포함하지 않거나 둘 중 하나이고 둘 다일 수는 없으므로, 이 두 갈래는 서로 겹치지 않고 $X$ 전체를 덮는다.

- $a$를 포함하는 것: $a$가 이미 한 자리를 차지했으므로 나머지 $n-1$개에서 $r-1$개를 더 고른다 — $\binom{n-1}{r-1}$개.
- $a$를 포함하지 않는 것: $a$를 뺀 $n-1$개에서 $r$개를 고른다 — $\binom{n-1}{r}$개.

합의 법칙에 의해 $|X| = \binom{n-1}{r-1} + \binom{n-1}{r}$이다.

같은 유한집합 $X$를 두 방법으로 세었으므로 $\binom nr = \binom{n-1}{r-1} + \binom{n-1}{r}$이다. $\blacksquare$

**검산.** $n = 4$, $r = 2$: $\binom42 = 6$이고 $\binom31 + \binom32 = 3 + 3 = 6$이다.

### 문제 5

**접근.** 이중 세기 답안에서 가장 자주 빠지는 것은 첫 줄, 곧 세는 대상의 선언이다. $X$를 먼저 한 줄로 못 박고 시작하면 두 방법이 같은 것을 센다는 사실이 답안 안에서 저절로 유지된다.

**풀이.** $A$를 원소가 $n$개인 집합이라 하고, $A$의 부분집합 전체의 모임을 $X$라 하자.

방법 1(크기별): 부분집합의 크기는 $0, 1, \ldots, n$ 중 정확히 하나이므로 크기에 따른 분류는 서로 겹치지 않고 $X$ 전체를 덮는다. 크기 $k$인 것은 정의 1.2에 의해 $\binom nk$개이므로 합의 법칙에 의해 $|X| = \sum_{k=0}^n \binom nk$이다.

방법 2(원소별): $A = \{x_1, \ldots, x_n\}$이라 하자. 부분집합을 정하는 일은 각 $x_i$에 대해 넣을지 뺄지를 정하는 일과 같고, 결정이 다르면 부분집합이 다르며 부분집합이 다르면 결정도 다르므로 이 대응에는 빠짐도 겹침도 없다. 각 원소마다 2가지이고 결정은 $n$번이므로 곱셈 원리에 의해 $|X| = 2^n$이다.

같은 $X$를 두 방법으로 세었으므로 $\sum_{k=0}^n \binom nk = 2^n$이다. $\blacksquare$

**검산.** $n = 3$: 좌변 $1 + 3 + 3 + 1 = 8$, 우변 $2^3 = 8$이다.

### 문제 6

**접근.** 예제 2.1과 뼈대가 같고 물건과 상자만 바뀐다. 물건은 사람 13명, 상자는 태어난 달 12개다. 확인 4에서 지적한 대로 마지막 되번역 줄이 빠지기 쉬우므로 그 줄을 먼저 머릿속에 적어 두고 시작한다.

**풀이.** 13명을 태어난 달에 따라 분류한다. 달은 1월부터 12월까지 12가지이고 모든 사람은 정확히 한 달에 태어났으므로, 상자는 12개이고 각 사람은 정확히 한 상자에 들어간다. 물건은 13명, 상자는 12개이고 $13 > 12$이므로 비둘기집 원리에 의해 두 명 이상이 든 상자가 존재한다. 그 상자에 든 두 사람은 태어난 달이 같다. 따라서 같은 달에 태어난 두 사람이 존재한다. $\blacksquare$

**검산.** 경계를 확인한다 — 12명이면 각 달에 한 명씩 배정하는 배치가 실제로 있으므로 결론이 강제되지 않는다. 곧 $13 > 12$이라는 부등식이 증명의 유일한 동력이다.

### 문제 7

**접근.** (a)는 공식에 넣고 분모의 두 팩토리얼이 무엇이 되는지만 보면 끝난다 — $n - (n-r) = r$이라는 한 줄이 전부다. (b)는 세기 증명이므로 세는 대상을 두 개 선언하고 그 사이의 대응을 하나 만든다. 대응에 빠짐도 겹침도 없음을 밝히는 것이 본체다.

**풀이.**

**(a) 대수.** 조합 공식에 $r$ 자리에 $n-r$을 넣으면

$$
\binom n{n-r} = \frac{n!}{(n-r)!\,\big(n - (n-r)\big)!} = \frac{n!}{(n-r)!\,r!} = \frac{n!}{r!\,(n-r)!} = \binom nr
$$

이다. $\blacksquare$

**(b) 조합적.** $A$를 원소가 $n$개인 집합이라 하고, $\mathcal S_r$을 $A$의 크기 $r$인 부분집합 전체의 모임, $\mathcal S_{n-r}$을 크기 $n-r$인 부분집합 전체의 모임이라 하자. $\Phi(S) = A \setminus S$로 대응을 정한다.

- $\Phi$는 $\mathcal S_r$의 원소를 $\mathcal S_{n-r}$의 원소로 보낸다: $|S| = r$이면 $|A \setminus S| = n - r$이다.
- 겹침이 없다: $A \setminus S = A \setminus T$이면 양변의 여집합을 다시 취해 $S = T$이다.
- 빠짐이 없다: $T \in \mathcal S_{n-r}$이면 $S = A \setminus T$가 크기 $r$이고 $\Phi(S) = A \setminus (A \setminus T) = T$이다.

곧 $\Phi$는 두 모임을 빠짐도 겹침도 없이 짝지으므로 두 모임의 크기가 같고, 정의 1.2에 의해 $\binom nr = \binom n{n-r}$이다. $\blacksquare$

**복기.** 같은 등식에 두 증명이 붙었다. (a)는 세 줄이지만 등식이 왜 성립하는지 말하지 않고, (b)는 "$r$개를 뽑는 일과 $n-r$개를 남기는 일이 같은 일"이라는 이유를 보인다. 문제 20의 (a)에서 언어화할 차이가 이 대비다.

**검산.** $n=5$, $r=2$: $\binom52 = 10 = \binom53$이다.

### 문제 8

**접근.** 이항정리는 $x, y$에 대한 항등식이므로 아무 값이나 넣어도 된다(특수화, S7주차). 목표 식에 $(-1)^k$가 있으므로 $y$ 자리에 $-1$을 넣는다. 좌변이 무엇이 되는지를 먼저 확인하면 결론이 $0$인 이유가 보인다.

**풀이.** $n \ge 1$이라 하자. 정리 1.3에 $x = 1$, $y = -1$을 대입하면

$$
\big(1 + (-1)\big)^n = \sum_{k=0}^n \binom nk \cdot 1^{n-k} \cdot (-1)^k
$$

이다. 좌변은 $0^n$이고, $n \ge 1$이므로 $0^n = 0$이다. 우변은 $1^{n-k} = 1$이므로 $\sum_{k=0}^n (-1)^k \binom nk$이다. 따라서

$$
\sum_{k=0}^n (-1)^k \binom nk = 0. \qquad \blacksquare
$$

**복기.** $n \ge 1$ 조건이 왜 필요한지가 이 문제의 요점이다. 정리 1.3은 자연수 $n$만 다루므로 $n = 0$은 정리의 사정권 밖이고, 정리에 $n = 0$을 대입해 논하는 것부터가 근거 없는 걸음이다. 합 자체를 직접 계산하면 $\sum_{k=0}^0 (-1)^k \binom 0k = \binom00 = 1 \ne 0$ 이므로 결론이 $n = 0$에서 거짓이며, 이것이 $n \ge 1$ 조건이 붙는 이유다. 항등식에 값을 대입할 때는 그 값이 정리의 사정권 안인지부터 확인한다.

**검산.** $n = 3$: $\binom30 - \binom31 + \binom32 - \binom33 = 1 - 3 + 3 - 1 = 0$이다.

### 문제 9

**접근.** 예제 2.1에서 $5$를 $n+1$로, $4$를 $n$으로 바꾼 것이다. 달라지는 것은 상자의 개수를 세는 줄뿐이다 — 나머지가 $0$부터 $n-1$까지이므로 $n$개다. 1권 41주차 문제 14에서 함수의 언어로 만난 명제이고, 이번에는 원리의 이름을 대어 짧게 끝낼 수 있다.

**풀이.** $n$을 자연수라 하고 $a_1, \ldots, a_{n+1}$을 정수라 하자. 각 $a_i$를 $n$으로 나눈 나머지에 따라 분류한다. 나눗셈 정리에 의해 나머지는 $0, 1, \ldots, n-1$ 중 정확히 하나이므로 상자는 $n$개이고 각 $a_i$는 정확히 한 상자에 들어간다. 물건은 $n+1$개, 상자는 $n$개이고 $n + 1 > n$이므로, 비둘기집 원리에 의해 두 개 이상이 든 상자가 존재한다. 그 상자에 든 두 정수를 $a_i, a_j$ ($i \ne j$)라 하면 둘은 $n$으로 나눈 나머지가 같으므로 $a_i \equiv a_j \pmod n$이고, 곧 $n \mid (a_i - a_j)$이다. 따라서 차가 $n$의 배수인 두 정수가 존재한다. $\blacksquare$

**복기.** 이 증명은 예제 2.1을 특수한 경우로 포함한다($n = 4$). 일반형을 먼저 쓰고 특수한 경우를 그 인용으로 처리하는 것도 가능하지만, 이번 주 답안에서는 상자의 개수를 세는 줄이 매번 달라지므로 그 줄만은 문제마다 다시 적는다.

**검산.** $n = 2$: 정수 3개 중 차가 짝수인 두 개가 존재한다 — 문제 10의 명제와 같은 내용이며, 실제로 홀짝이 같은 두 수의 차는 짝수다.

### 문제 10

**접근.** 평가는 항목별 점검이다. 채점 기준의 네 항목을 하나씩 대 본다. 특히 마지막 문장의 "합은 짝수"가 계산으로 뒷받침되어 있는지 확인한다 — 이 답안은 옳지만 마지막 한 줄이 압축되어 있다.

**풀이.** **옳은 증명이다.** 항목별로 점검하면 다음과 같다.

① 상자의 정의와 개수: "홀수와 짝수" 2개로 정확히 적혀 있다. 모든 정수는 짝수이거나 홀수이고 둘 다일 수는 없으므로(1권 33주차 나눗셈 정리를 $n=2$에 적용한 결과) 이 분류에는 겹침도 빈틈도 없다. 통과.

② 개수 비교: 상자 2개와 정수 3개가 모두 적혀 있어 $3 > 2$가 읽히고, 비둘기집을 인용해 같은 상자에 두 개가 있음을 얻었다. 다만 부등식 자체는 문자로 적혀 있지 않다. 채점 기준 ②는 부등식을 명시할 것을 요구하므로 이 항목은 "통과, 다만 $3 > 2$를 한 번 적으면 완결"이다.

③ 되번역: "같은 홀짝 두 정수의 합은 짝수"로 상자의 말을 명제의 말로 옮겼다. 통과. 다만 이 마지막 문장은 계산으로 뒷받침해야 완결된다 — 둘 다 짝수이면 $2k + 2l = 2(k+l)$이고, 둘 다 홀수이면 $(2k+1) + (2l+1) = 2(k+l+1)$이므로 어느 경우든 합이 짝수다.

④ 근거의 출처: 비둘기집 원리를 이름으로 인용했고, 정수의 홀짝 분류도 목록에 있는 근거다. 통과.

**복기.** 압축된 증명과 틀린 증명은 다르다. 이 답안은 ③의 마지막 한 줄이 압축되어 있을 뿐이므로 "옳다, 다만 마지막 문장의 계산을 명시하면 완결된다"가 정확한 평가다. 평가 문제에서 "압축"을 "오류"로 적으면 평가 자체가 틀린다 — 원래 답안의 논증은 그대로 성립하는데 성립하지 않는다고 판정한 것이므로, 지적한 자리에서 실제로 무너지는 것을 하나도 제시할 수 없다. C5주차의 증명 평가 절차가 요구하는 것이 바로 그 제시다.

### 문제 11

**접근.** 훈련 1에서 조합적으로 증명한 것을 이번에는 팩토리얼로 계산한다. 두 분수의 분모가 다르므로 공통분모를 잡는 것이 전부이고, 공통분모는 좌변의 분모 $r!\,(n-r)!$로 잡는다. $1 \le r \le n-1$이어야 모든 팩토리얼이 정의된다.

**풀이.** $1 \le r \le n-1$이라 하자. $(n-1) - (r-1) = n - r$이므로

$$
\binom{n-1}{r-1} = \frac{(n-1)!}{(r-1)!\,(n-r)!}, \qquad \binom{n-1}{r} = \frac{(n-1)!}{r!\,(n-1-r)!}.
$$

첫 항의 분모 $(r-1)!\,(n-r)!$에 $r$을 곱하면 $r!\,(n-r)!$이 되고, 둘째 항의 분모 $r!\,(n-1-r)!$에 $n-r$을 곱하면 $r!\,(n-r)!$이 된다. 그러므로

$$
\binom{n-1}{r-1} + \binom{n-1}{r} = \frac{(n-1)!\,r}{r!\,(n-r)!} + \frac{(n-1)!\,(n-r)}{r!\,(n-r)!} = \frac{(n-1)!\,\big(r + (n-r)\big)}{r!\,(n-r)!}
$$

이고, $r + (n-r) = n$이므로

$$
= \frac{(n-1)!\,n}{r!\,(n-r)!} = \frac{n!}{r!\,(n-r)!} = \binom nr. \qquad \blacksquare
$$

**복기.** 계산의 관절은 한 곳이다 — 두 분자에 각각 $r$과 $n-r$이 붙고 그 합이 $n$이 되어 $(n-1)! \cdot n = n!$이 완성되는 자리. 훈련 1의 조합적 증명에서 이 $r$과 $n-r$에 해당하는 것이 "$a$를 포함하는 갈래"와 "포함하지 않는 갈래"다. 두 증명이 같은 분기를 다른 언어로 적고 있다.

**검산.** $n = 6$, $r = 3$: 우변의 두 항은 $n-1 = 5$를 위 첨자로 가지므로 $\binom{5}{2} + \binom53 = 10 + 10 = 20$이고, 좌변은 $\binom63 = 20$이다. 위 첨자를 $n$ 그대로 두고 $\binom62 + \binom63$을 계산하는 실수가 잦으므로, 검산에서 첨자가 $n-1$로 내려갔는지 한 번 더 확인한다.

### 문제 12

**접근.** 세는 대상은 "$m+n$명에서 뽑은 2명으로 이루어진 집합 전체"다. 우변이 세 항이므로 분류도 세 갈래여야 하고, 갈래를 가르는 기준은 "뽑힌 2명 중 첫 그룹 출신이 몇 명인가"다. 그 값이 $2, 1, 0$ 셋 중 정확히 하나라는 한 줄이 서로소와 전체 덮기를 동시에 준다.

**풀이.** 서로소인 두 집합 $A$($m$명)와 $B$($n$명)를 합친 $m+n$명에서 2명을 뽑아 만든 집합 전체를 $X$라 하자.

방법 1: 정의 1.2에 의해 $|X| = \binom{m+n}{2}$이다.

방법 2: $X$의 원소를 "그 2명 중 $A$ 출신이 몇 명인가"로 분류한다. 그 수는 $2, 1, 0$ 중 정확히 하나이므로 세 갈래는 서로 겹치지 않고 $X$ 전체를 덮는다.

- 둘 다 $A$ 출신: $A$에서 2명을 고르므로 $\binom m2$개.
- 하나씩: $A$에서 1명, $B$에서 1명을 고르므로 곱셈 원리에 의해 $m \times n = mn$개.
- 둘 다 $B$ 출신: $B$에서 2명을 고르므로 $\binom n2$개.

합의 법칙에 의해 $|X| = \binom m2 + mn + \binom n2$이다.

같은 $X$를 두 방법으로 세었으므로 $\binom{m+n}2 = \binom m2 + mn + \binom n2$이다. $\blacksquare$

**검산.** 대수로도 확인한다. 좌변은 $\frac{(m+n)(m+n-1)}{2}$이고, 우변은

$$
\frac{m(m-1)}{2} + mn + \frac{n(n-1)}{2} = \frac{m^2 - m + 2mn + n^2 - n}{2} = \frac{(m+n)^2 - (m+n)}{2} = \frac{(m+n)(m+n-1)}{2}
$$

로 같다. $m = 2$, $n = 3$이면 양변이 $10 = 1 + 6 + 3$이다.

**복기.** 이 분류의 기준("한쪽 그룹 출신이 몇 명인가")이 문제 15에서 그대로 재사용된다. 다른 것은 뽑는 인원이 2명이 아니라 $n$명이라는 점뿐이고, 그래서 갈래가 세 개가 아니라 $n+1$개가 된다.

### 문제 13

**접근.** 이항정리에서 $y$ 자리에 $x$를, $x$ 자리에 $1$을 두면 한 문자짜리 항등식 $(1+x)^n = \sum \binom nk x^k$가 나온다. 목표 식에는 계수 $k$가 붙어 있는데, 항등식의 항에 지수만큼의 계수를 붙이는 조작이 곧 미분이다. 미분을 쓰지 않는 길도 있으므로 두 길을 모두 적는다.

**풀이.**

**전개.** 정리 1.3에 $x$ 자리에 $1$, $y$ 자리에 $x$를 넣으면

$$
(1+x)^n = \sum_{k=0}^n \binom nk 1^{n-k}x^k = \binom n0 + \binom n1 x + \binom n2 x^2 + \cdots + \binom nn x^n.
$$

**길 1 (미분).** 위 등식은 $x$에 대한 항등식이므로 양변을 $x$로 미분해도 항등식이다.

$$
n(1+x)^{n-1} = \sum_{k=1}^n k \binom nk x^{k-1}.
$$

여기에 $x = 1$을 대입하면 좌변은 $n \cdot 2^{n-1}$이고 우변은 $\sum_{k=1}^n k\binom nk$이다. $k = 0$ 항은 $0 \cdot \binom n0 = 0$이므로 합의 시작을 $k=0$으로 늘려도 값이 변하지 않는다. 따라서 $\sum_{k=0}^n k \binom nk = n\,2^{n-1}$이다. $\blacksquare$

**길 2 (계수 항등식).** 먼저 $1 \le k \le n$에 대해

$$
k\binom nk = k \cdot \frac{n!}{k!\,(n-k)!} = \frac{n!}{(k-1)!\,(n-k)!} = n \cdot \frac{(n-1)!}{(k-1)!\,\big((n-1)-(k-1)\big)!} = n\binom{n-1}{k-1}
$$

이다. 그러므로 $j = k-1$로 지표를 옮기면

$$
\sum_{k=0}^n k\binom nk = \sum_{k=1}^n n\binom{n-1}{k-1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = n\,2^{n-1}
$$

이다. 마지막 등호는 예제 2.3을 $n-1$에 적용한 것이다. $\blacksquare$

**복기 (세 번째 길 — 이중 세기).** 같은 등식을 세기로도 얻는다. $n$명에서 위원회를 하나 뽑고 그 안에서 위원장 한 명을 정하는 방법 전체를 $X$라 하자. 위원회의 크기 $k$로 분류하면 $\sum_k \binom nk \cdot k$이고, 위원장을 먼저 정하면 $n$가지이며 나머지 $n-1$명 각각이 위원회에 들어가는지 아닌지를 정하면 $2^{n-1}$가지이므로 $n\,2^{n-1}$이다. 같은 $X$를 두 방법으로 세었으므로 두 수는 같다. 미분을 쓰지 않고도 등식이 나온다.

**검산.** $n = 3$: 좌변은 $0 \cdot 1 + 1 \cdot 3 + 2 \cdot 3 + 3 \cdot 1 = 12$이고 우변은 $3 \cdot 2^2 = 12$이다.

### 문제 14

**접근.** 비둘기집은 시작일 뿐이다. 한 사람을 고정해 그 사람이 가진 5개의 관계를 2종류의 상자에 넣으면 일반형에 의해 $\lceil 5/2 \rceil = 3$개 이상이 같은 종류다. 그다음 그 3명 사이의 관계를 보는데, 여기서 다시 "그런 쌍이 하나라도 있는가"로 갈린다. 두 갈래 모두에서 결론이 나오는지 각각 확인해야 증명이 끝난다.

**풀이.** 여섯 사람 중 한 사람을 $A$라 하자. $A$와 나머지 5명 사이의 관계 5개를 "서로 안다"와 "서로 모른다" 2개의 상자에 넣는다. 물건이 5개, 상자가 2개이므로 비둘기집 원리의 일반형에 의해 $\lceil 5/2 \rceil = 3$개 이상이 든 상자가 존재한다. 곧 $A$가 같은 종류의 관계를 맺은 세 사람이 있다. 그들을 $B, C, D$라 하자.

**경우 1: $A$가 $B, C, D$를 모두 안다.** $B, C, D$ 중 서로 아는 두 사람이 있다고 하자. 그 두 사람을 $X, Y$라 하면 $A$는 $X$도 $Y$도 알고 $X$와 $Y$도 서로 아므로, $A, X, Y$가 서로 아는 3명이다. 그런 두 사람이 없다고 하자. 그러면 $B$와 $C$, $C$와 $D$, $B$와 $D$가 모두 서로 모르므로 $B, C, D$가 서로 모르는 3명이다. 어느 쪽이든 결론이 성립한다.

**경우 2: $A$가 $B, C, D$를 모두 모른다.** $B, C, D$ 중 서로 모르는 두 사람이 있다고 하자. 그 두 사람을 $X, Y$라 하면 $A$는 $X$도 $Y$도 모르고 $X$와 $Y$도 서로 모르므로, $A, X, Y$가 서로 모르는 3명이다. 그런 두 사람이 없다고 하자. 그러면 $B$와 $C$, $C$와 $D$, $B$와 $D$가 모두 서로 아므로 $B, C, D$가 서로 아는 3명이다. 어느 쪽이든 결론이 성립한다.

두 경우는 상자가 두 종류뿐이므로 전체를 덮고, 각 경우에서 결론이 나왔다. 따라서 6명 중에는 서로 아는 3명 또는 서로 모르는 3명이 존재한다. $\blacksquare$

**복기.** 비둘기집이 만든 것은 "$B, C, D$"라는 무대이고, 결론을 낳은 것은 그 무대 위에서의 경우 나누기다. 존재 증명이 한 번의 인용으로 끝나지 않고 두 단계로 이어지는 전형적인 형태이며, 두 경우를 모두 적어야 하는 이유는 "안다"와 "모른다"가 대칭이지만 결론의 두 선택지도 함께 뒤바뀌기 때문이다.

**검산.** 사람이 5명이면 결론이 성립하지 않는 배치가 존재한다 — 다섯 사람을 원형으로 놓고 이웃끼리만 아는 것으로 정하면 서로 아는 3명도 서로 모르는 3명도 없다. 곧 6이라는 수가 필요하다.

### 문제 15

**접근.** 좌변에 제곱이 있는데 세기 자체에는 제곱이 나오지 않는다. 제곱은 마지막에 대칭(문제 7)으로 만들고, 그전까지는 $\binom nk\binom n{n-k}$ 꼴로 둔다. 분류의 기준은 문제 12와 같다 — 뽑힌 사람 중 첫 그룹 출신이 몇 명인가. 다른 것은 갈래의 수뿐이다.

**풀이.** $2n$명을 서로소인 두 그룹 $X_1$($n$명)과 $X_2$($n$명)로 나눈다. $2n$명에서 $n$명을 뽑아 만든 집합 전체를 $X$라 하자.

방법 1: 정의 1.2에 의해 $|X| = \binom{2n}{n}$이다.

방법 2: $X$의 원소를 "뽑힌 $n$명 중 $X_1$ 출신이 몇 명인가"로 분류한다. 그 수는 $0, 1, \ldots, n$ 중 정확히 하나이므로 이 $n+1$개의 갈래는 서로 겹치지 않고 $X$ 전체를 덮는다. $X_1$ 출신이 $k$명인 갈래에서는 $X_1$에서 $k$명을 고르고 $X_2$에서 나머지 $n-k$명을 고르므로, 곱셈 원리에 의해 $\binom nk \binom n{n-k}$개다. 합의 법칙에 의해

$$
|X| = \sum_{k=0}^n \binom nk \binom n{n-k}.
$$

같은 $X$를 두 방법으로 세었으므로 $\binom{2n}n = \sum_{k=0}^n \binom nk \binom n{n-k}$이다. 여기에 대칭(문제 7)을 써서 $\binom n{n-k} = \binom nk$로 바꾸면

$$
\sum_{k=0}^n \binom nk^2 = \binom{2n}n. \qquad \blacksquare
$$

**복기.** 문제 12와 뼈대가 완전히 같다 — 두 그룹으로 나누고, 뽑힌 것 중 한쪽 출신의 수로 분류하고, 각 갈래에서 곱셈 원리를 쓰고, 더한다. 방데르몽드 항등식 $\binom{m+n}r = \sum_k \binom mk\binom n{r-k}$의 두 특수한 경우가 문제 12($r=2$)와 이 문제($m=n=r$)다.

**검산.** $n = 2$: 좌변 $\binom20^2 + \binom21^2 + \binom22^2 = 1 + 4 + 1 = 6$이고 우변 $\binom42 = 6$이다.

### 문제 16

**접근.** 두 길이 다 열려 있다. 파스칼을 반복하는 길은 $n$에 대한 귀납으로 적으면 "반복"이 정확한 논증이 된다. 조합적인 길은 $\{1, \ldots, n+1\}$에서 $r+1$개를 뽑고 **최대 원소**로 분류하는 것이다 — 최대 원소가 정해지면 나머지를 어디에서 뽑아야 하는지가 따라 나온다.

**풀이.**

**길 1 (파스칼 반복 — $n$에 대한 귀납).** $r$을 고정하고 $n \ge r$에 대해 귀납한다.

기저 $n = r$: 좌변은 $\binom rr = 1$이고 우변은 $\binom{r+1}{r+1} = 1$이므로 성립한다.

귀납 단계: $\sum_{i=r}^n \binom ir = \binom{n+1}{r+1}$이 성립한다고 가정하자. 그러면

$$
\sum_{i=r}^{n+1}\binom ir = \left(\sum_{i=r}^{n}\binom ir\right) + \binom{n+1}{r} = \binom{n+1}{r+1} + \binom{n+1}{r}
$$

이고, 파스칼 규칙을 $\binom{n+2}{r+1} = \binom{n+1}{r} + \binom{n+1}{r+1}$의 꼴로 쓰면 이 값은 $\binom{n+2}{r+1}$이다. 곧 $n+1$에 대해서도 성립한다. 귀납법에 의해 모든 $n \ge r$에서 성립한다. $\blacksquare$

**길 2 (조합적).** $\{1, 2, \ldots, n+1\}$의 크기 $r+1$인 부분집합 전체를 $X$라 하자.

방법 1: 정의 1.2에 의해 $|X| = \binom{n+1}{r+1}$이다.

방법 2: $X$의 원소를 **최대 원소**로 분류한다. 부분집합마다 최대 원소는 정확히 하나이므로 이 분류에는 겹침도 빈틈도 없다. 최대 원소가 $i+1$인 부분집합은 나머지 $r$개를 $\{1, \ldots, i\}$에서 고른 것이므로 $\binom ir$개다. 크기가 $r+1$이려면 최대 원소는 $r+1$ 이상이어야 하고 $n+1$ 이하이므로, $i$는 $r$부터 $n$까지다. 합의 법칙에 의해 $|X| = \sum_{i=r}^n \binom ir$이다.

같은 $X$를 두 방법으로 세었으므로 $\sum_{i=r}^n \binom ir = \binom{n+1}{r+1}$이다. $\blacksquare$

**검산.** $r = 1$, $n = 3$: 좌변 $\binom11 + \binom21 + \binom31 = 1 + 2 + 3 = 6$이고 우변 $\binom42 = 6$이다.

**복기.** "최대 원소로 분류한다"는 이 문제의 핵심 장치이며, 순서가 있는 집합에서 부분집합을 셀 때 되풀이해 쓰인다. 분류의 기준을 고를 때는 그 기준이 각 대상에 대해 **정확히 하나의 값**을 주는지부터 확인한다 — 최대 원소는 그 조건을 만족한다.

### 문제 17

**접근.** 상자를 "홀수 부분"으로 잡는 것이 이 문제의 전부다. 모든 자연수는 2를 최대한 뽑아내어 $2^a m$($m$ 홀수)로 쓸 수 있고 그 표현은 유일하다. $1$부터 $2n$ 사이의 홀수가 정확히 $n$개임을 세는 줄을 반드시 적는다. 마지막에 두 지수가 다른 이유도 한 줄 필요하다.

**풀이.** $S$를 $\{1, 2, \ldots, 2n\}$에서 고른 $n+1$개의 수의 집합이라 하자. 각 $x \in S$를 $x = 2^{a}m$($a \ge 0$은 정수, $m$은 홀수)의 꼴로 쓴다. 이런 표현은 존재하고 유일하다 — $x$에서 2를 나눌 수 있을 때까지 나누면 홀수 $m$이 남고, 나눈 횟수가 $a$다(C15주차의 소인수분해에서도 같은 결론이 나온다).

$x$의 홀수 부분 $m$에 따라 $S$의 원소를 분류한다. $x \le 2n$이고 $m \le x$이므로 $m$은 $1$부터 $2n$ 사이의 홀수이고, 그런 홀수는 $1, 3, 5, \ldots, 2n-1$의 $n$개다. 곧 상자는 $n$개이고, 표현의 유일성에 의해 각 $x$는 정확히 한 상자에 들어간다.

물건은 $n+1$개, 상자는 $n$개이고 $n+1 > n$이므로, 비둘기집 원리에 의해 두 개 이상이 든 상자가 존재한다. 그 상자에 든 두 수를 $x = 2^{a}m$, $y = 2^{b}m$이라 하자. $x \ne y$이므로 $a \ne b$이고, 필요하면 이름을 바꾸어 $a < b$라 해도 된다. 그러면

$$
y = 2^{b}m = 2^{b-a}\cdot 2^{a}m = 2^{b-a}x
$$

이고 $b - a \ge 1$이므로 $2^{b-a}$는 정수다. 따라서 $x \mid y$이고, 한 수가 다른 수를 나누는 두 수가 존재한다. $\blacksquare$

**검산.** $n = 3$이면 $\{1, \ldots, 6\}$에서 4개를 고른다. 예를 들어 $\{2,3,4,5\}$에서는 $2 \mid 4$다. 그리고 $n$개만 고르면 결론이 강제되지 않는다 — $\{4,5,6\}$은 어느 수도 다른 수를 나누지 않는다. 곧 $n+1$이라는 개수가 필요하다.

**복기.** 상자를 "수 자체"가 아니라 "수에서 뽑아낸 불변량"으로 잡은 것이 이 문제의 전환점이다. 예제 2.1의 나머지도 같은 종류의 불변량이며, 두 문제 모두 결론 ("차가 배수", "하나가 다른 것의 배수")을 같은 값으로 번역해 주는 양을 상자로 삼았다.

### 문제 18

**접근.** 결론 자체는 참이므로(문제 19), 지적할 것은 결론이 아니라 **추론**이다. §1.7의 근거 목록에 "몇 개의 값에서 확인했다"는 항목이 없다는 사실이 지적의 근거다. 덧붙여 $n = 0$을 넣어 보면 명제 자체가 조건을 필요로 한다는 것도 드러난다.

**풀이.** **틀린 증명이다(결론은 참이지만 논증이 성립하지 않는다).**

① 명제는 모든 $n$에 대한 전칭 주장인데, 이 답안은 $n = 2$ 하나에서 좌변과 우변이 같음을 확인했을 뿐이다. 특수화는 반증에는 쓸 수 있지만 전칭 명제의 증명에는 쓸 수 없다 — 확인하지 않은 $n$이 무한히 많이 남는다.

② §1.7의 근거 목록에 "유한 개의 값에서 확인했다"는 항목은 없다. 확인 9의 (나)가 바로 이 형태이며, 목록 밖의 근거는 근거가 아니다.

③ "따라서 성립"이라는 마지막 문장이 아무 규칙에도 대응하지 않는다. $n=2$에서의 참에서 모든 $n$에서의 참으로 넘어가는 추론 규칙은 존재하지 않는다. 귀납법이라면 $P(n) \Rightarrow P(n+1)$을 보여야 하는데 이 답안에는 그 단계가 없다.

④ 명제의 진술 자체도 조건이 빠져 있다. $n = 0$이면 좌변은 $\binom00 = 1$이고 우변은 $2^{-1} = \frac12$이므로 등식이 성립하지 않는다. 곧 $n \ge 1$ 조건이 필요하다.

올바른 증명은 문제 19에 있다.

**복기.** 이 답안이 그럴듯해 보이는 이유는 계산이 하나도 틀리지 않았다는 데 있다. $\binom20 + \binom22 = 2 = 2^1$은 참이다. 오류는 계산이 아니라 계산에서 결론으로 넘어가는 한 걸음에 있으며, 증명 검사는 계산 검사이기 전에 추론 검사다.

### 문제 19

**접근.** 목표는 짝수 $k$의 항만 남기는 것이다. 이항정리에서 얻은 두 등식 중 하나는 모든 항을 $+$로, 다른 하나는 홀수 항을 $-$로 만든다. 두 등식을 더하면 홀수 항이 상쇄되고 짝수 항만 두 배로 남는다. 어느 쪽을 더할지는 목표가 정해 준다.

**풀이.** $n \ge 1$이라 하자. 정리 1.3에 $x = y = 1$을 대입하면

$$
\sum_{k=0}^n \binom nk = (1+1)^n = 2^n
$$

이고, $x = 1$, $y = -1$을 대입하면 문제 8에 의해

$$
\sum_{k=0}^n (-1)^k \binom nk = (1-1)^n = 0
$$

이다. 두 등식을 더하면 좌변에서 $k$번째 항의 계수가 $1 + (-1)^k$가 되므로

$$
2^n + 0 = \sum_{k=0}^n \big(1 + (-1)^k\big)\binom nk
$$

이다. $k$가 홀수이면 $1 + (-1)^k = 0$이고 $k$가 짝수이면 $1 + (-1)^k = 2$이므로, 살아남는 것은 짝수 $k$의 항뿐이고 그 계수는 2다. 따라서

$$
2^n = 2\sum_{k \text{ 짝수}} \binom nk, \qquad \sum_{k \text{ 짝수}} \binom nk = 2^{n-1}. \qquad \blacksquare
$$

$n \ge 1$ 조건은 둘째 등식에서 필요했다 — 문제 8에서 본 대로 $n = 0$이면 $(1-1)^0 = 1 \ne 0$이다.

**검산.** $n = 4$: $\binom40 + \binom42 + \binom44 = 1 + 6 + 1 = 8 = 2^3$이다. $n = 3$: $\binom30 + \binom32 = 1 + 3 = 4 = 2^2$이다.

**복기.** 두 특수값의 합과 차로 항을 걸러 내는 기법이다. 차를 쓰면 같은 방식으로 홀수 항의 합도 나온다: $2^n - 0 = 2\sum_{k \text{ 홀수}}\binom nk$이므로 홀수 항의 합도 $2^{n-1}$이다. 곧 짝수 항의 합과 홀수 항의 합이 같고, 둘을 더하면 예제 2.3의 $2^n$이 된다.

### 문제 20

**접근.** (a)는 예제 2.3과 문제 7을 나란히 놓고 두 증명이 각각 무엇을 보여 주는지 비교하면 문장이 나온다. (b)는 확인 15에서 정리한 "알려 주는 것과 알려 주지 않는 것"을 그대로 문장으로 옮기면 된다. 두 물음 모두 답이 아니라 **구분의 기준**을 묻는다.

**풀이.** (예시 답안)

**(a)** 예제 2.3은 $\sum_k \binom nk = 2^n$을 대수 조작 없이 증명했다 — 좌변은 부분집합을 크기별로 센 수이고 우변은 같은 부분집합들을 원소별 결정으로 센 수이므로, 같은 유한집합의 크기가 둘로 적힌 것뿐이라는 사실이 등식의 전부다. 대수 증명이 기호를 변형해 좌변을 우변으로 옮겨 간다면, 조합적 증명은 양변이 **같은 것을 센다는 이야기**를 만들어 등식을 세운다. 그래서 대수 증명은 등식이 참임을 확정하고 조합적 증명은 등식이 왜 참인지를 함께 준다.

**(b)** 예제 2.1은 5개 정수 중 차가 4의 배수인 두 개가 존재함을 개수 비교 ($5 > 4$) 하나로 보장했지만, 증명의 어느 줄에도 그 두 개를 결정하는 절차가 없다. 곧 비둘기집은 증인을 짓지 않고 존재만 확립하므로 비구성적 존재 증명(C7주차)의 대표적인 공급원이다.

**복기.** 채점 항목은 세 가지다 — ① (a)에서 "같은 것을 센다"는 문구가 있는가 ② (a)에서 대수와의 차이를 "무엇이 더 보이는가"로 말했는가 ③ (b)에서 "증인을 제시하지 않는다"는 점을 예제 2.1의 구체적 자리로 뒷받침했는가. 세 항목 모두 결론이 아니라 근거를 묻는다.

---

**다음 주 예고 (C17):** Chartrand 14장 — 해석학의 증명. 세기를 떠나 극한으로 간다. 1권 45~47주차에서 세운 $\varepsilon$-N과 $\varepsilon$-$\delta$를 Chartrand의 언어로 다시 조직하고, 1권이 빚으로 남긴 **미분의 정의와 미분가능성**을 정식으로 세운다. 이번 주 문제 13에서 인정하고 쓴 다항식의 미분도 거기서 근거를 얻는다. 1학기 S8주차의 중첩 양화사가 해석학의 언어로 실전 운용되는 주이기도 하다. 원서 14장을 통독하고 온다.