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

내용

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

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

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

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

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

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

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

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

답

상자는 4로 나눈 나머지다. 기준은 결론에서 거꾸로 세운다 — “\(a - b\)가 4의 배수”와

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

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

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

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

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

확인 11. 첫 문장을 완성해 보자: “\(\underline{\qquad}\)을 정수라 하자.”

답

“\(a_1, a_2, a_3, a_4, a_5\)를 정수라 하자.” 첨자를 쓰는 이유는 개수가 다섯이기

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

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

\(4 \mid 0\)이다).

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

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

답

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

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

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

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

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

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

답

“물건은 \(5\)개, 상자는 \(4\)개이고 \(5 > 4\)이므로, 비둘기집 원리에 의해 두 개

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

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

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

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

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

답

“그 상자에 든 두 정수를 \(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에서 막혔던 것 — 겹치는 쌍의 위치가 입력마다 달라진다 — 이 문제가 되지 않는다. 증명은 위치를 말하지 않기 때문이다.

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

답

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

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

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

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

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

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

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

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

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

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

답

지수 \(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주차의 표준 서식이다.

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

답

① 지표 이동 — 둘째 합의 지수가 \(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단 서식에서 걸음 ①과 ②, ③을 채우면 된다.

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

답

① \(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}\)

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

답

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

빈틈도 없다는 문장.

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

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

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

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

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

이은 문장.

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

등호로 잇느냐뿐이다.

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

백지 암기 대상

세기 증명의 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\) 그래도 안 되면 풀이를 읽는다.

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

이번 주의 채점 기준

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

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

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

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

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

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

기본 ●○○#

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

힌트

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

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

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

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

힌트

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

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

어떤 \(\binom3k\)인지를 함께 적는다.

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

힌트

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

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

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

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

힌트

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

\(A\)의 원소 하나를 \(a\)로 고정하고, 크기 \(r\)인 부분집합을 “\(a\)를 포함하는가”로

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

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

힌트

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

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

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

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

힌트

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

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

표준 ●●○#

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

힌트

(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의 일반화).

힌트

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

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

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

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

Result. 임의의 3개 정수 중 합이 짝수인 두 개가 존재한다.

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

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

힌트

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

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

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

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

힌트

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

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

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

문제 12가 여는 갈래 — 방데르몽드 항등식

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

\(\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명 뽑기 = 둘 다 첫 그룹 / 하나씩 / 둘 다 둘째 그룹).

힌트

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

“뽑힌 2명 중 첫 그룹 출신이 몇 명인가”이고, 그 값은 \(2, 1, 0\) 셋 중 하나다 —

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

문제 13이 빌려 쓰는 도구 — 다항식의 미분

\(\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}\)).

힌트

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

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

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

문제 14가 쓰는 언어 — 관계의 두 색 분류

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

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

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

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

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

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

힌트

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

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\) 합).

힌트

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

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

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

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

힌트

파스칼을 반복하는 길은 \(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\) 둘, 하나가 다른 것의 배수).

힌트

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

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

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

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

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\)의 합/차.)

힌트

결론 자체는 참이다(문제 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\)).

힌트

두 등식을 더할 때 각 항의 계수가 \(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.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장을 통독하고 온다.