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

## 예제 — 공식을 만들고 사용하기

이번 주의 예제는 증명 하나(2.1)와 계산 둘(2.2, 2.3)이다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 2.2는 설계만 함께 하고, 2.3은 설계부터 혼자 한다.

### 예제 2.1 — $|A \cup B|$ 공식의 증명

**명제.** 유한집합 $A, B$에 대해 $|A \cup B| = |A| + |B| - |A \cap B|$.

**설계 — 쓰기 전에 정하는 두 가지.** 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 먼저 정한다.

|  | **말** | **번역** |
|---|---|---|
| 가정 (주어진 것) | $A$, $B$는 유한집합 | 쓸 수 있는 도구는 덧셈 원리 — 단, **서로소인 쌍에만** 적용된다 |
| 목표 (만들 것) | $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$ | 좌변 $\lvert A \cup B \rvert$를 서로소 조각들의 크기로 표현한다 |

:::{container} quotebox
**확인 11.** 덧셈 원리를 $A$와 $B$에 곧바로 적용해 $|A \cup B| = |A| + |B|$라고

쓸 수 없는 이유는 무엇인가. 그렇다면 전략은 무엇이 되어야 하는가?
:::

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

$A$와 $B$가 서로소라는 보장이 없다 — 겹침이 있으면 §1.4에서 본 대로 등식이

어긋난다. 전략: $A \cup B$라는 **같은 집합**을 겹치지 않는 조각들로 재조립한

뒤, 그 조각들에 덧셈 원리를 적용한다. 재조립의 재료는 5주차의 집합 연산

($A - B$, $A \cap B$)이다.
:::

**1단계 — $A \cup B$를 서로소 두 조각으로.** 벤 다이어그램에서 $A \cup B$는 "초승달($A - B$) + 원($B$)"으로 쪼개진다.

:::{container} quotebox
**확인 12.** 등식 $A \cup B = (A - B) \cup B$에 대해 두 가지를 확인해 보자.

① 두 조각 $A - B$와 $B$가 서로소인 이유는? ② 두 조각을 합치면 빠짐없이

$A \cup B$ 전체가 되는 이유는?
:::

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

① $A - B$의 원소는 차집합의 정의에 의해 $B$에 **없다** — 그러므로 $B$와

겹칠 수 없다.

② $x \in A \cup B$라 하자. $x \in B$이면 둘째 조각에 있다. $x \notin B$이면

$x \in A$일 수밖에 없으므로 $x \in A - B$ — 첫째 조각에 있다. 어느 쪽이든

원소는 한 조각에 들어가므로 $A \cup B \subseteq (A - B) \cup B$다. 역으로

$A - B \subseteq A \subseteq A \cup B$이고 $B \subseteq A \cup B$이므로

$(A - B) \cup B \subseteq A \cup B$ — 양쪽 포함이 모두 성립하므로 두 집합은

같다(5주차 문제 15~20의 양방향 포함 틀).
:::

**2단계 — 덧셈 원리 1회.** 서로소 분할을 얻었으므로 더할 수 있다.

:::{container} quotebox
**확인 13.** 등식 (i)을 완성해 보자: $|A \cup B| = \underline{\quad} + |B|$ …(i).

이 등식에는 목표에 없는 양이 하나 남아 있다 — 무엇인가?
:::

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

$|A \cup B| = |A - B| + |B|$ …(i). 남은 양은 $|A - B|$ — 목표 등식의 우변에는

$|A|$, $|B|$, $|A \cap B|$만 있으므로, $|A - B|$를 이 셋으로 표현하는 일이

남는다. 그 표현을 주는 것이 두 번째 분할이다.
:::

**3단계 — $A$를 서로소 두 조각으로.** 이번에는 $A$를 "$B$와 안 겹치는 부분 + 겹치는 부분"으로 쪼갠다: $A = (A - B) \cup (A \cap B)$. 두 조각이 서로소인 이유는 1단계와 같고($A - B$의 원소는 $B$에 없는데 $A \cap B$의 원소는 $B$에 있다), 전체를 덮는 이유도 같다 — $A$의 원소는 $B$에 속하는지 아닌지에 따라 정확히 한 조각에 들어간다. 역포함도 성립한다 — $A - B \subseteq A$이고 $A \cap B \subseteq A$이므로 두 조각의 합집합은 $A$를 벗어나지 않는다. (이 등식을 5주차 문제 18에서 수치와 벤 다이어그램으로 확인해 두었다.)

:::{container} quotebox
**확인 14.** 이 분할에 덧셈 원리를 적용하고, 이항해서 (ii)를 완성해 보자:

$|A| = \underline{\quad} + \underline{\quad}$, 즉 $|A - B| = \underline{\qquad}$ …(ii).
:::

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

$|A| = |A - B| + |A \cap B|$, 이항하면(근거 ③) $|A - B| = |A| - |A \cap B|$ …(ii).

미지량 $|A - B|$가 이미 아는 양 둘로 표현되었다 — 재료가 다 모였다.
:::

**4단계 — 대입으로 완성.**

:::{container} quotebox
**확인 15.** (ii)를 (i)에 대입한 결과를 적어 보자:

$|A \cup B| = \underline{\qquad}$.
:::

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

$|A \cup B| = (|A| - |A \cap B|) + |B| = |A| + |B| - |A \cap B|$. $\blacksquare$

목표 등식 그대로다 — 증명이 끝났다.
:::

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

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| $A \cup B = (A - B) \cup B$이고, $A - B$와 $B$는 서로소다. | 덧셈 원리의 조건은 서로소 — 겹칠 수 있는 $A, B$ 대신 초승달+원으로 재조립한다. $A - B$의 원소는 정의상 $B$에 없으므로 겹침이 없다. |
| 덧셈 원리에 의해 $\lvert A \cup B \rvert = \lvert A - B \rvert + \lvert B \rvert$. …(i) | 서로소 분할이므로 그냥 더한다(근거 ④). 미지량 $\lvert A - B \rvert$가 남는다. |
| 한편 $A = (A - B) \cup (A \cap B)$이고 두 조각은 서로소다. | $A$의 원소는 $B$에 속하는지 아닌지에 따라 정확히 한 조각에 들어간다(5주차 문제 18의 등식). 미지량을 아는 양으로 바꾸기 위한 두 번째 분할이다. |
| 덧셈 원리에 의해 $\lvert A \rvert = \lvert A - B \rvert + \lvert A \cap B \rvert$, 즉 $\lvert A - B \rvert = \lvert A \rvert - \lvert A \cap B \rvert$. …(ii) | 같은 원리의 재적용. 이항은 근거 ③ — 필요한 $\lvert A - B \rvert$가 아는 양들로 표현된다. |
| (ii)를 (i)에 대입하면 $\lvert A \cup B \rvert = \lvert A \rvert - \lvert A \cap B \rvert + \lvert B \rvert$. $\blacksquare$ | 두 분할의 결과를 결합해 목표 등식을 완성한다(근거 ③ — 대입). |

**구조 읽기.** "겹치는 대상을 서로소 조각으로 재조립 $\to$ 덧셈 원리 두 번 $\to$ 대입" — 집합 항등식(5주차)이 세기 공식의 증명 도구가 되었다. 이 증명이 문제 11의 백지 재현 대상이다.

**검산.** 5주차 문제 13의 수치를 넣어 보자 — $A = \{1,2,3,4\}$, $B = \{3,4,5\}$. 좌변 $|A \cup B| = |\{1,2,3,4,5\}| = 5$, 우변 $4 + 3 - 2 = 5$ ✓.

:::{container} quotebox
**확인 16.** $A$와 $B$가 서로소인 특수한 경우, 방금 증명한 공식은 어떤 식이

되는가.
:::

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

$|A \cap B| = |\emptyset| = 0$이므로 $|A \cup B| = |A| + |B|$ — 덧셈 원리

그대로다. 포함–배제는 덧셈 원리를 특수 사례로 포함하는 일반형이다. "겹침이

없으면 뺄 것도 없다"는 당연한 말이 공식 안에 이미 들어 있다.
:::

### 예제 2.2 — 포함–배제 사용

**문제.** 1부터 100까지의 자연수 중 2의 배수이거나 5의 배수인 것은 몇 개인가?

이번에는 설계만 함께 한다.

:::{container} quotebox
**확인 17.** 번역표를 채워 보자.

① 세는 대상을 집합으로: $A = \underline{\qquad}$, $B = \underline{\qquad}$,

구하는 것은 $\lvert A \cup B \rvert$.

② 도구 선택: $A$와 $B$는 서로소인가? 아니라면 어느 원리를 쓰는가?

③ 재료: $\lvert A \rvert$, $\lvert B \rvert$, $\lvert A \cap B \rvert$는 각각

어떻게 구하는가 — 특히 $A \cap B$는 무엇의 배수 집합인가?
:::

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

① $A$ = 1~100 중 2의 배수 집합, $B$ = 1~100 중 5의 배수 집합.

② 서로소가 아니다 — $10 \in A \cap B$. 포함–배제를 쓴다.

③ 각 크기는 배수 세기 $\lfloor N/d \rfloor$(§1.5). 겹침은 2로도 5로도

나누어떨어지는 수, 곧 2와 5의 공배수 = **10의 배수** 집합이다(2와 3의

공배수가 6의 배수였던 5주차 문제 9의 감각 그대로).
:::

**풀이.** 구하는 것은 $|A \cup B|$ — $A$는 2의 배수 집합, $B$는 5의 배수 집합이다. 배수 세기에 의해 $|A| = \lfloor 100/2 \rfloor = 50$, $|B| = \lfloor 100/5 \rfloor = 20$이고, 겹침 $A \cap B$는 10의 배수 집합이므로 $|A \cap B| = \lfloor 100/10 \rfloor = 10$이다. 포함–배제(예제 2.1)에 의해

$$
|A \cup B| = 50 + 20 - 10 = 60
$$

**검산.** 1~10 구간에서 2 또는 5의 배수는 $2, 4, 5, 6, 8, 10$의 6개이고, 이 패턴이 10개 구간마다 반복되므로 $6 \times 10 = 60$ ✓.

### 예제 2.3 — 여사건: "적어도 하나"

**문제.** 5자리 숫자 비밀번호(각 자리 0~9) 중 숫자 9를 적어도 하나 포함하는 것은 몇 개인가?

이번에는 설계부터 스스로 해 보자.

:::{container} quotebox
**확인 18.** 풀이에 들어가기 전에 세 가지를 적어 보자.

① 정면 돌파(9의 개수로 경우 나누기)는 경우가 몇 개인가.

② "9를 적어도 하나 포함한다"의 부정은? (11주차 규칙)

③ 전체 $U$의 크기와 부정 쪽 집합의 크기는 각각 어떻게 계산하는가.
:::

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

① 9가 1개, 2개, 3개, 4개, 5개 — 다섯 경우, 각각에 자리 선택과 곱셈 원리

계산이 붙는다.

② "9를 **하나도** 포함하지 않는다" — 모든 자리가 9가 아니다.

③ 전체: 각 자리 10가지의 길이 5 목록 — $10^5$ (곱셈 원리). 부정: 각 자리가

0~8의 9가지 — $9^5$ (곱셈 원리). 남는 일은 여사건 공식의 뺄셈 하나다.
:::

**풀이.** 전체 집합 $U$는 5자리 비밀번호 전부 — 각 자리 10가지의 길이 5 목록이므로 곱셈 원리에 의해 $|U| = 10^5 = 100000$이다. 구하는 집합을 $A$라 하면, 그 여집합 $A^c$는 "9를 하나도 포함하지 않는" 비밀번호들 — 각 자리의 후보가 0~8의 9가지로 줄어든 길이 5 목록이므로 $|A^c| = 9^5 = 59049$이다. 여사건 공식에 의해

$$
|A| = |U| - |A^c| = 10^5 - 9^5 = 100000 - 59049 = 40951\text{개}
$$

**검산.** $9^2 = 81$, $9^4 = 81^2 = 6561$, $9^5 = 6561 \times 9 = 59049$ ✓ — $100000 - 59049 = 40951$ ✓.

### 관찰 — 세 풀이의 같은 뼈대

세 예제는 소재만 다를 뿐 걸음이 같다. 대응표의 빈칸을 채워 보자.

| **단계** | **예제 2.1** | **예제 2.2** | **예제 2.3** |
|---|---|---|---|
| ① 세는 대상을 집합의 언어로 선언한다 | 목표 등식의 좌변 $\lvert A \cup B \rvert$ | $A$ = 2의 배수, $B$ = 5의 배수, 목표는 $\lvert A \cup B \rvert$ | $\underline{\quad(1)\quad}$ |
| ② 서로소 조각으로 재조립한다 | $\underline{\quad(2)\quad}$ | 공식이 재조립을 대신한다 — 더하고 겹침을 뺀다 | $U = A \cup A^c$ — 전체에서 부정 쪽을 뺀다 |
| ③ 조각마다 원리를 인용해 세고 결합한다 | 덧셈 원리 두 번 + 대입 | $\underline{\quad(3)\quad}$ | 곱셈 원리 두 번 + 여사건 공식 |

:::{container} quotebox
**확인 19.** 대응표의 (1)(2)(3)을 채워 보자.
:::

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

(1) $U$ = 비밀번호 전체, $A$ = 9를 적어도 하나 포함하는 것들 ($A \subseteq U$).

(2) $A \cup B = (A - B) \cup B$와 $A = (A - B) \cup (A \cap B)$ — 서로소 분할 두 개.

(3) 배수 세기 세 번 + 포함–배제.

세 풀이 모두 정확히 이 세 걸음이다.
:::

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

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

**겹침 세기의 3단계**

① 세는 대상을 집합의 언어로 선언한다 (무엇의 합집합$\cdot$여집합인가) $\to$

② 서로소 조각으로 재조립한다 (분할$\cdot$포함–배제$\cdot$여사건) $\to$

③ 조각마다 원리를 인용해 세고 결합한다 (검산까지).

모의시험의 세기 문항 전부가 이 세 걸음이다.
:::

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

모의시험 전의 마지막 다리다. 훈련 1은 포함–배제 계산, 훈련 2는 여사건 계산, 훈련 3은 3집합 — 시험에 나오는 세 종류의 일을 하나씩 예행한다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(6장)에 있다 — 다 채운 뒤에 대조한다.

### 훈련 1 ●○○ — 수식 빈칸

**과제.** 1부터 60까지의 자연수 중 4의 배수이거나 6의 배수인 것의 개수.

**풀이.** $A$ = 4의 배수 집합, $B$ = 6의 배수 집합. $|A| = \lfloor 60/4 \rfloor = \underline{\quad(1)\quad}$, $|B| = \lfloor 60/6 \rfloor = \underline{\quad(2)\quad}$. 겹침 $A \cap B$는 4와 6의 공배수, 곧 $\underline{\quad(3)\quad}$의 배수 집합이므로 $|A \cap B| = \underline{\quad(4)\quad}$. 포함–배제에 의해

$$
|A \cup B| = \underline{\quad(1)\quad} + \underline{\quad(2)\quad} - \underline{\quad(4)\quad} = \underline{\quad(5)\quad}
$$

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

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

**과제.** 동전을 6번 던진 기록(각 회 앞면/뒷면, 길이 6 목록) 중 앞면이 적어도 한 번 나오는 기록의 개수.

**풀이.** "앞면이 적어도 한 번"의 부정은 "$\underline{\quad(1)\quad}$"이다 — 근거: $\underline{\quad(2)\quad}$ (11주차). 전체 기록은 각 회 2가지의 길이 6 목록이므로 $\underline{\quad(3)\quad}$개다 — 근거: $\underline{\quad(4)\quad}$. 부정에 해당하는 기록은 $\underline{\quad(5)\quad}$개다. 따라서 구하는 개수는

$$
\underline{\quad(6)\quad} = 63
$$

— 근거: $\underline{\quad(7)\quad}$.

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

**과제.** 1부터 120까지의 자연수 중 2, 3, 5 중 적어도 하나의 배수인 것의 개수. (문제 15의 예행연습이다.)

'겹침 세기의 3단계'의 각 칸을 통째로 채운다.

- ① 집합 선언과 전략: $\underline{\quad(1)\quad}$
- ② 일곱 항의 계산: $\underline{\quad(2)\quad}$
- ③ 공식 결합과 검산: $\underline{\quad(3)\quad}$

## 연습문제 (20문항)

이 20문항은 3부(12~14주차) **총정리 모의시험**을 겸한다. 규칙은 세 줄이다.

- 노트와 본문을 덮고 90분 안에 푼다. 시험 중에는 힌트 상자를 열지 않는다.
- 다 푼 뒤 §6 해설로 채점한다. 문제 1(백지 테스트)을 하나라도 틀리면 해당 주차부터 재복습한 뒤 넘어간다.
- 채점 후 틀린 문제는 힌트 상자와 해설의 '접근'까지만 읽고 한 번 더 시도한다 — 그래도 안 되면 풀이를 읽는다.

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

답이 아니라 **근거**가 점수다. 세기 문제는 답 숫자만 쓰면 0점이다 —

"무엇을 세는지 + 어느 원리인지"(12주차 서술 규범)를 한 줄이라도 서술해야

정답으로 친다. 증명 문제(11, 16, 17)는 결론이 아니라 각 줄의 근거

(서로소 언급$\cdot$원리 인용)를 채점한다.
:::

### 기본 ●○○

**1.** [백지 테스트] (a) 곱셈 원리를 조건까지 포함해 진술하시오. (b) $\binom{n}{k}$의 정의와 공식을 쓰시오. (c) 이항정리를 쓰시오.

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

셋 다 조건$\cdot$조각이 채점 포인트다 — (a)는 "선택지의 **개수**가 앞 단계와

무관"이라는 조건, (b)는 "부분집합의 **개수**"라는 정의(공식만 쓰면 절반이다),

(c)는 일반항의 첨자($x$와 $y$의 지수 합이 $n$).
:::

**2.** 계산하시오. (a) $7!$  (b) $\dfrac{9!}{6!}$  (c) $\binom{9}{3}$  (d) $\binom{6}{3}$

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

(b)는 전부 곱하지 말고 $6!$을 약분한다. 조합은 분자에 위에서부터 $k$개만

내려 쓴다: $\binom{9}{3} = \frac{9 \cdot 8 \cdot 7}{3!}$.
:::

**3.** 다음 각각은 목록인가 집합인가 — 세기 관점에서 판정하시오. (a) 금고 비밀번호 4자리  (b) 로또 당첨 번호 6개  (c) 계주 주자 4명의 달리는 순서  (d) 회식 메뉴 3가지 선택

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

판정 기준은 두 개다(12주차) — 순서가 결과를 바꾸는가, 같은 것의 중복이

허용되는가. 각 항목에 두 물음을 던지면 판정이 끝난다.
:::

**4.** 대문자 2개 + 숫자 3개(이 순서로, 중복 허용)로 된 차량 코드는 몇 가지인가? 곱셈 원리로 서술하시오.

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

서술 규범 ①②③ 그대로 — 길이 5 목록 선언, 자리별 선택지 개수와 무관성 확인,

곱셈 원리 인용. 세 문장이면 만점이다.
:::

**5.** $\binom{7}{2} = \binom{6}{1} + \binom{6}{2}$를 수치로 확인하시오.

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

세 값을 각각 계산해 비교한다. 끝난 뒤 이 등식이 어느 공식의 어느 사례인지도

한 줄 적어 본다 — $n$과 $k$가 무엇인가.
:::

**6.** 두 사건 집합 $A = \{2$의 배수$\}$, $B = \{3$의 배수$\}$ ($U = \{1, \dots, 30\}$)는 서로소인가? 서로소가 아니라면 겹침은 무엇의 배수 집합인가?

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

서로소 판정은 $A \cap B = \emptyset$의 확인이다 — 두 목록에 다 있는 수를

하나라도 찾으면 판정이 끝난다. 2로도 3으로도 나누어떨어지는 수는 무엇의 배수인가.
:::

### 표준 ●●○

**7.** 학생 6명을 일렬로 세울 때, (a) 전체 가짓수 (b) A, B가 이웃하는 가짓수를 구하시오.

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

(b)는 묶음 기법(12주차 문제 8) — 이웃할 둘을 한 묶음으로 세면 대상이 몇 개가

되는가. 묶음 **내부**의 배열을 잊으면 절반만 세게 된다.
:::

**8.** 숫자 1~5를 한 번씩 사용한 다섯 자리 수 중 홀수는 몇 개인가?

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

제약이 가장 센 자리부터 — 홀수 조건은 일의 자리에 걸린다. 일의 자리를 먼저

정하고 나머지를 나열하면, 각 단계의 선택지 개수가 앞 선택과 무관해진다.
:::

**9.** 남자 6명, 여자 5명 중 남자 3명, 여자 2명의 위원회를 만드는 가짓수는?

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

남자 선택과 여자 선택은 "경우"가 아니라 "단계"다 — 각각 조합으로 세고 곱셈

원리로 잇는다.
:::

**10.** $(x + 2)^6$의 전개에서 $x^4$의 계수를 구하시오.

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

일반항 $\binom{6}{k} x^{6-k} 2^k$에서 $x^4$이 되는 $k$를 먼저 찾는다.

$2^k$를 빠뜨리면 조합만 남는다 — 계수는 두 인수의 곱이다.
:::

**11.** [백지 재현] $|A \cup B| = |A| + |B| - |A \cap B|$를 증명하시오 (예제 2.1).

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

서로소 분할 두 개 — $A \cup B = (A-B) \cup B$, $A = (A-B) \cup (A \cap B)$ —

에 덧셈 원리를 한 번씩 쓰고 대입한다. 각 분할이 서로소임을 **말로 언급**하는

것이 채점 포인트다.
:::

**12.** 1부터 100까지 중 3의 배수이거나 7의 배수인 수는 몇 개인가?

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

예제 2.2와 같은 걸음이다. 겹침은 3과 7의 공배수 — 무엇의 배수 집합인가.

세 항 모두 $\lfloor 100/d \rfloor$로 센다.
:::

**13.** $(0,0)$에서 $(5,2)$까지의 격자 최단 경로 수를 조합으로 구하시오.

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

13주차 문제 10과 같은 대응이다 — 경로는 R(오른쪽)와 U(위)로 된 목록이고,

목록은 U가 놓일 위치의 선택으로 완전히 결정된다. 목록의 길이와 U의 개수부터

적는다.
:::

**14.** 4자리 비밀번호(0~9) 중 0을 적어도 하나 포함하는 것은 몇 개인가?

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

"적어도 하나"는 뒤집는다(§1.6) — 부정 "0이 하나도 없음"이면 각 자리의 후보는

몇 가지가 되는가. 전체에서 빼면 끝난다.
:::

### 도전 ●●●

**15.** 1부터 1000까지 중 2, 3, 5 중 적어도 하나의 배수인 수는 몇 개인가? (3집합 포함–배제; $\lfloor 1000/6 \rfloor = 166$, $\lfloor 1000/15 \rfloor = 66$ 등 몫 계산 포함)

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

훈련 3의 뼈대 그대로 — 집합 세 개를 선언하고, 단일 3항$\cdot$쌍 겹침 3항$\cdot$삼중 겹침

1항의 일곱 항을 전부 $\lfloor 1000/d \rfloor$로 계산한 뒤 부호 리듬(홀수 $+$,

짝수 $-$)으로 결합한다. 겹침의 $d$는 두 수(세 수)의 공배수다.
:::

**16.** [백지 재현] 파스칼 공식 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$의 세기 증명을 쓰시오.

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

기준 인물 "갑"의 포함/미포함으로 크기 $k$ 부분집합 전체를 나눈다. 두 부류가

**서로소**이고 **전체를 덮는다**는 두 마디를 명시해야 덧셈 원리가 작동한다 —

이번 주에 공식화한 그 원리다. 명제 조건 $1 \le k \le n-1$(13주차 예제 2.2)을

먼저 적는 것도 채점 포인트다.
:::

**17.** [백지 재현] $\sum_{k=0}^{n} \binom{n}{k} = 2^n$을 두 방법 중 하나로 증명하시오.

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

방법 1: 이항정리에 무엇을 대입하면 좌변이 $(1+1)^n$이 되는가. 방법 2: $n$원소

집합의 부분집합 전체를 크기별로 나눠 세면(덧셈 원리) 좌변, 원소별 넣음/뺌

목록으로 세면(12주차 §1.8) 우변 — 같은 대상의 두 세기.
:::

**18.** 남자 5명, 여자 4명 중 3명을 뽑을 때 여자가 적어도 1명 포함되는 경우의 수를 여사건으로 구하시오.

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

"여자 적어도 1명"의 부정은 "여자 0명" — 곧 전원 남자다. 전체 $\binom{9}{3}$에서

전원 남자인 경우를 빼면 된다.
:::

**19.** 문제 18에 대한 다음 풀이의 오류를 정확히 지적하시오: "여자 1명을 먼저 뽑고($4$가지), 나머지 2명을 남은 8명에서 뽑으면($\binom{8}{2} = 28$가지) $4 \times 28 = 112$가지다." (참값은 74 — 무엇이 몇 번씩 세어졌는가?)

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

$112 - 74 = 38$이 어디서 왔는지 추적한다 — 여자가 2명인 위원회 하나를 놓고,

이 풀이의 절차가 그 위원회를 몇 가지 서로 다른 경로로 만들어 내는지 세어 본다.

12주차 문제 17(악수)과 같은 유형의 오류다.
:::

**20.** (서술) (a) 포함–배제에서 $|A \cap B|$를 "빼는" 이유를 원소 관점(각 원소가 몇 번 세어지는가)에서 두 문장으로 설명하시오. (b) 이번 파트에서 "세기"가 "증명 훈련"이 되는 이유를 자신의 언어로 두 문장 이내로 쓰시오.

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

(a)는 확인 5의 표를 문장으로 옮기면 된다 — 겹침 원소가 $|A| + |B|$에서 몇 번

세어지는가. (b)는 채점 기준 상자("답이 아니라 근거가 점수다")와 자신의 채점

경험을 연결한다.
:::

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

권장 일정 — 1~2일차: §0~§3 학습 / 3일차: 1차 재현 / 4일차: 모의시험(§4) 90분과 채점 / 5일차: 완전 백지 재현과 오답 재시도. 재현은 두 번으로 나눈다 — 한 번에 완전 백지로 가지 않는다.

**1차 시도 (3일차) — 틀 카드 허용.** 세 원리(덧셈$\cdot$포함–배제$\cdot$여사건)와 '겹침 세기의 3단계'만 펴 놓고, 예제 2.1과 2.3을 처음부터 끝까지 적는다. 본문은 보지 않는다.

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

- [ ] 덧셈 원리를 서로소 조건까지 포함해 진술했다.
- [ ] $|A \cup B|$ 공식의 증명을 백지에 재현했다 (서로소 분할 두 개 + 덧셈 원리 두 번 + 대입).
- [ ] 3집합 포함–배제의 부호 리듬(홀수 개 교집합은 더하고, 짝수 개는 뺀다)을 썼다.
- [ ] "적어도 하나 = 전체 $-$ 하나도 없음"을 11주차 부정 규칙과 연결해 설명했다.
- [ ] 모의시험 11, 16, 17번(증명 재현)을 통과했다.
- [ ] 모의시험에서 틀린 문제를 전부 다시 풀어 통과했다.

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

| **막힌 지점** | **처방** |
|---|---|
| 덧셈 원리의 조건이 기억나지 않는다 | §1.3 해부 표 — "서로소" 삭제 실험($25 \neq 20$)과 함께 다시 외운다 |
| $\lvert A \cup B \rvert$ 증명의 첫 분할이 안 나온다 | 예제 2.1의 1단계 — 초승달+원 그림부터 다시 그린다 |
| 3집합의 부호가 헷갈린다 | 확인 6 — 원소 하나가 항별로 몇 번 세어지는지 직접 센다 |
| "적어도 하나"에서 경우 나누기부터 시작하게 된다 | §1.6 — 부정을 먼저 적는 습관 (훈련 2 재필사) |
| 배수의 개수가 바로 안 나온다 | §1.5의 $\lfloor N/d \rfloor$ — 확인 7의 검산 요령까지 |
| 곱셈과 덧셈 중 무엇을 쓸지 망설인다 | 확인 3 — "단계인가 경우인가"의 판정 연습 |

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

## 해설

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

### 준비 운동

1. $\binom{n}{k}$ = $n$원소 집합의 크기 $k$ 부분집합의 개수 $= \dfrac{n!}{k!(n-k)!}$.
1. $1 \le k \le n-1$이면 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

(13주차 예제 2.2의 명제 조건). 핵심: 기준 인물(갑)의 포함/미포함으로 부분집합 전체를 겹침 없이 둘로 나눠 각각 세고 더한다.

1. 일반항 $\binom{5}{k} x^{5-k} y^k$에서 $y^3$이려면 $k = 3$ — 계수는 $\binom{5}{3} = 10$.

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

(1) $15$  (2) $10$  (3) $12$ — 4와 6의 공배수는 최소공배수 12의 배수다. $4 \times 6 = 24$가 아님에 주의 — 예제 2.2의 2와 5는 곱 10이 곧 최소공배수인 경우였을 뿐이다.  (4) $\lfloor 60/12 \rfloor = 5$  (5) $15 + 10 - 5 = 20$.

※ 검산: 1~12 구간에서 4 또는 6의 배수는 $4, 6, 8, 12$의 4개, 이 패턴이 12마다 반복되어 $4 \times 5 = 20$ ✓.

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

(1) 앞면이 한 번도 없다(여섯 번 전부 뒷면) (2) "적어도 하나($\exists$)"의 부정은 "전부 아님($\forall\neg$)" — 부정 규칙 (3) $2^6 = 64$  (4) 곱셈 원리 — 각 회 2가지, 앞 결과와 무관 (5) $1$ — 전부 뒷면인 기록 단 하나 (6) $64 - 1$  (7) 여사건 공식 $|A| = |U| - |A^c|$

※ 부정 쪽이 "단 하나"로 줄어드는 이 극단이 여사건 세기가 가장 이득을 보는 경우다.

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

(1) $A_2, A_3, A_5$ = 1~120 중 2, 3, 5의 배수 집합. "적어도 하나의 배수" = $A_2 \cup A_3 \cup A_5$ — 셋은 쌍마다 겹치므로 3집합 포함–배제를 쓴다. (2) 단일: $\lfloor 120/2 \rfloor = 60$, $\lfloor 120/3 \rfloor = 40$, $\lfloor 120/5 \rfloor = 24$. 쌍 겹침(공배수): $\lfloor 120/6 \rfloor = 20$, $\lfloor 120/10 \rfloor = 12$, $\lfloor 120/15 \rfloor = 8$. 삼중 겹침: $\lfloor 120/30 \rfloor = 4$. (3) $60 + 40 + 24 - 20 - 12 - 8 + 4 = 88$. 검산 — 1~30 구간에서 어느 배수도 아닌 수는 $1, 7, 11, 13, 17, 19, 23, 29$의 8개이므로 배수인 것은 22개, 이 패턴이 30마다 반복되어 $22 \times 4 = 88$ ✓.

### 문제 1

**접근.** 정의$\cdot$원리는 유도하는 것이 아니라 암기를 확인하는 것이다. 셋 다 조건$\cdot$조각이 채점 포인트다 — (a)는 "개수가 앞 단계와 무관", (b)는 "부분집합의 개수"라는 정의 부분, (c)는 일반항의 첨자.

**풀이.** (a) 길이 $k$의 목록을 만들 때, $i$번째 자리의 선택지가 (앞 단계의 결과와 무관하게) $a_i$가지이면, 목록의 총수는 $a_1 a_2 \cdots a_k$이다. 조각 "개수가 앞 단계와 무관"이 빠지면 원리가 무너진다 — 앞 선택에 따라 개수가 달라지는 상황(12주차 문제 20)에서는 곱할 수 없다. (b) $\binom{n}{k}$ = $n$원소 집합의 크기 $k$ 부분집합의 개수 $= \dfrac{n!}{k!(n-k)!}$. 정의(부분집합의 개수)와 공식 둘 다 있어야 만점이다 — 공식만 쓰면 13주차 문제 11(순서 지우기 유도)을 되짚는다. (c) $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$. 각 항에서 $x$와 $y$의 지수 합이 $n$인지, 첨자 $k$가 0부터 $n$까지인지 확인한다.

**복기.** 이 세 진술이 3부의 뼈대 전부다. 하나라도 형식이 무너졌으면 답을 베끼지 말고 해당 주차(12$\cdot$13주차)의 해부 표로 돌아가 조각의 이유와 함께 재암기한다.

### 문제 2

**접근.** 팩토리얼은 정의대로 곱하되, 나눗셈이 있으면 곱하기 전에 약분부터 한다. 조합은 분자에 위에서부터 $k$개만 내려 쓰는 꼴이 빠르다.

**풀이.** (a) $7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5040$. (b) $\dfrac{9!}{6!} = \dfrac{9 \cdot 8 \cdot 7 \cdot 6!}{6!} = 9 \cdot 8 \cdot 7 = 504$ — $6!$을 계산하지 않고 통째로 약분한다. (c) $\binom{9}{3} = \dfrac{9 \cdot 8 \cdot 7}{3!} = \dfrac{504}{6} = 84$. (d) $\binom{6}{3} = \dfrac{6 \cdot 5 \cdot 4}{3!} = \dfrac{120}{6} = 20$.

**검산.** (c)에서 (b)의 값 $504$가 분자로 재등장한다 — $\binom{9}{3} = \frac{9!}{3! \, 6!}$이므로 당연한 재등장이고, 두 계산이 서로를 확인해 준다.

### 문제 3

**접근.** 판정 기준은 두 개다(12주차) — 순서가 결과를 바꾸는가, 중복이 가능한가. 각 항목에 두 물음을 기계처럼 적용한다.

**풀이.** (a) 목록 — $1234$와 $4321$은 다른 비밀번호(순서가 결과를 바꾼다)이고, $1122$처럼 같은 숫자의 반복도 허용된다. (b) 집합 — 당첨 번호 6개는 어느 순서로 뽑혔든 같은 당첨이고, 같은 번호가 두 번 나올 수 없다. (c) 목록 — 누가 1번 주자인지가 핵심이다. 주자 순서가 다르면 다른 배치다. (d) 집합 — 고른 메뉴 3가지에 순서가 없고, 같은 메뉴를 두 번 고르지 않는다.

**복기.** "순서 있음 = 목록(곱셈 원리$\cdot$팩토리얼), 순서 없음 = 집합(조합)" — 이 첫 판정이 12~13주차 도구 선택의 전부였다.

### 문제 4

**접근.** 서술 규범 ①②③ — 구조 선언, 자리별 개수와 무관성, 원리 인용 — 세 문장으로 끝나는 문제다.

**풀이.** 차량 코드는 (문자, 문자, 숫자, 숫자, 숫자)의 길이 5 목록이다(중복 허용). 자리별 선택지는 차례로 $26, 26, 10, 10, 10$가지이고, 각 자리의 선택지 개수는 앞 자리의 선택과 무관하다. 곱셈 원리에 의해

$$
26^2 \times 10^3 = 676 \times 1000 = 676{,}000\text{가지}
$$

**복기.** "답: 676000"만 쓰면 이번 주 채점 기준으로 0점이다 — 세 문장의 서술이 점수의 전부다.

### 문제 5

**접근.** 세 값을 각각 계산해 등식이 실제로 성립하는지 본다. 계산 뒤에는 이 등식의 정체 — 어느 공식의 어느 사례인지 — 를 지목한다.

**풀이.** 좌변: $\binom{7}{2} = \dfrac{7 \cdot 6}{2} = 21$. 우변: $\binom{6}{1} + \binom{6}{2} = 6 + \dfrac{6 \cdot 5}{2} = 6 + 15 = 21$. 좌변 $=$ 우변 ✓. 이 등식은 파스칼 공식 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$의 $n = 7$, $k = 2$ 사례다.

**복기.** 수치 확인은 공식의 증명이 아니다(1주차 문제 20) — 증명은 문제 16에서 세기 논증으로 한다. 수치는 공식을 잘못 외웠는지 잡아내는 검산 장치다.

### 문제 6

**접근.** 서로소 판정은 $A \cap B = \emptyset$의 확인 — 두 목록에 모두 있는 수를 하나라도 찾으면 서로소가 아니다. 겹침의 정체는 공배수다.

**풀이.** 서로소가 아니다 — $6 \in A \cap B$ ($6$은 2의 배수이자 3의 배수)이고, 실제로 $A \cap B = \{6, 12, 18, 24, 30\}$이다. 겹침은 2와 3의 공배수, 곧 **6의 배수** 집합이다(최소공배수 6).

**복기.** 이 $A$, $B$가 §1.3 삭제 실험의 그 집합들이다 — $|A| + |B| = 25$가 실제 $|A \cup B| = 20$과 어긋나는 이유가 바로 이 겹침 5개였다. 서로소 확인 없이 덧셈 원리를 쓰면 정확히 이만큼 초과 계상된다.

### 문제 7

**접근.** (a)는 6명 전부의 나열 — 팩토리얼. (b)는 묶음 기법(12주차 문제 8) — 이웃 조건이 붙은 둘을 한 덩어리로 만들면 나열 대상이 줄어든다.

**풀이.** (a) 6명의 나열은 $6! = 720$가지. (b) A와 B를 한 묶음으로 보면 나열 대상은 (묶음, 나머지 4명)의 5개 — 그 나열은 $5! = 120$가지다. 묶음 내부에서 A, B의 순서가 (A,B)와 (B,A)의 2가지이고, 이 개수는 바깥 나열과 무관하다. 곱셈 원리에 의해 $120 \times 2 = 240$가지.

**검산.** 이웃하는 경우 240은 전체 720의 $\frac{1}{3}$ — 명시적으로 $\frac{2 \times 5!}{6!} = \frac{240}{720} = \frac{1}{3}$이다. B의 위치를 고정하면 A가 이웃할 자리는 끝자리일 때 1곳, 중간일 때 2곳이고, A가 놓일 수 있는 자리는 언제나 5곳이다. 따라서 이웃할 확률은 끝자리에서 $\frac{1}{5}$, 중간에서 $\frac{2}{5}$이고, B의 여섯 위치에 대해 평균을 내면 $\frac{2 \cdot \frac{1}{5} + 4 \cdot \frac{2}{5}}{6} = \frac{1}{3}$이다.

### 문제 8

**접근.** 제약이 가장 센 자리(일의 자리 — 홀수 조건)부터 정한다. 그래야 각 단계의 선택지 개수가 앞 선택과 무관해져 곱셈 원리의 조건이 성립한다.

**풀이.** 다섯 자리 수는 1~5를 한 번씩 쓴 길이 5 목록(반복 없음)이다. 홀수이려면 일의 자리가 $1, 3, 5$ 중 하나 — 3가지. 일의 자리를 무엇으로 정했든 나머지 네 자리는 남은 4개 숫자의 나열이므로 $4! = 24$가지 — 개수 $4!$은 앞 선택과 무관하다. 곱셈 원리에 의해

$$
3 \times 4! = 3 \times 24 = 72\text{개}
$$

**검산.** 전체 나열은 $5! = 120$개이고 일의 자리 후보 5개 중 홀수가 3개이므로 $120 \times \frac{3}{5} = 72$ ✓.

### 문제 9

**접근.** 남자 선택과 여자 선택은 경우가 아니라 **단계**다 — 위원회 하나가 (남자 3명 선택, 여자 2명 선택)의 두 단계로 완성된다. 각 단계는 순서 없는 선택이므로 조합.

**풀이.** 남자 3명의 선택은 $\binom{6}{3} = 20$가지, 여자 2명의 선택은 $\binom{5}{2} = 10$가지이고, 여자 쪽 선택지의 개수는 남자를 누구로 뽑았는지와 무관하다. 곱셈 원리에 의해

$$
\binom{6}{3} \times \binom{5}{2} = 20 \times 10 = 200\text{가지}
$$

**복기.** "또는"이면 덧셈, "그리고-이어서"면 곱셈 — 확인 3의 판정이 조합과 결합된 전형이다. 문제 18~19의 재료이기도 하다.

### 문제 10

**접근.** 이항정리의 일반항부터 적는다 — $(x + 2)^6$의 일반항은 $\binom{6}{k} x^{6-k} 2^k$. $x^4$이 되는 $k$를 찾고, 조합과 $2^k$의 **곱**으로 계수를 얻는다.

**풀이.** $x^{6-k} = x^4$이려면 $6 - k = 4$, 곧 $k = 2$. 해당 항은

$$
\binom{6}{2} x^4 \cdot 2^2 = 15 \times 4 \times x^4 = 60x^4
$$

이므로 $x^4$의 계수는 $60$이다.

**복기.** 세기의 눈으로 — 여섯 괄호 $(x+2)$ 중 $2$를 고를 2곳을 선택하는 가짓수가 $\binom{6}{2}$이고, 고른 곳마다 2가 곱해져 $2^2$이 붙는다. $2^k$를 빠뜨리는 실수는 이 그림을 잊은 데서 온다.

### 문제 11

**접근.** 예제 2.1의 백지 재현 — 서로소 분할 2개($A \cup B = (A-B) \cup B$, $A = (A-B) \cup (A \cap B)$)에 덧셈 원리를 한 번씩 쓰고 대입한다.

**풀이.** 유한집합 $A, B$에 대해 $A \cup B = (A - B) \cup B$이고, $A - B$의 원소는 정의상 $B$에 없으므로 두 조각은 서로소다. 덧셈 원리에 의해

$$
|A \cup B| = |A - B| + |B| \quad \cdots (\mathrm{i})
$$

한편 $A = (A - B) \cup (A \cap B)$이고, $A$의 원소는 $B$에 속하는지 아닌지에 따라 정확히 한 조각에 들어가므로 두 조각은 서로소이고 합은 $A$ 전체다. 덧셈 원리에 의해 $|A| = |A - B| + |A \cap B|$이고, 이항하면

$$
|A - B| = |A| - |A \cap B| \quad \cdots (\mathrm{ii})
$$

(ii)를 (i)에 대입하면 $|A \cup B| = |A| - |A \cap B| + |B| = |A| + |B| - |A \cap B|$이다. $\blacksquare$

**채점 기준.** ① 두 분할이 각각 서로소임을 언급했는가 ② 덧셈 원리를 근거로 인용했는가 ③ 이항$\cdot$대입 단계((ii)를 (i)에)가 있는가 — 셋 다 있어야 통과다.

### 문제 12

**접근.** 예제 2.2와 같은 걸음 — 두 배수 집합은 겹치므로 포함–배제. 겹침은 3과 7의 공배수 = 21의 배수(최소공배수 21). 각 항은 배수 세기 $\lfloor 100/d \rfloor$.

**풀이.** $A$ = 3의 배수 집합, $B$ = 7의 배수 집합이라 하면 $|A| = \lfloor 100/3 \rfloor = 33$, $|B| = \lfloor 100/7 \rfloor = 14$, $|A \cap B| = \lfloor 100/21 \rfloor = 4$이다. 포함–배제에 의해

$$
|A \cup B| = 33 + 14 - 4 = 43\text{개}
$$

**검산.** 21의 배수 4개를 나열하면 $21, 42, 63, 84$ — 다음 배수 $105 > 100$이므로 정확히 4개 ✓.

### 문제 13

**접근.** 13주차 문제 10과 같은 대응 — 경로를 문자 목록으로 번역하고, 목록을 위치 선택으로 번역한다. 두 번의 번역이 끝나면 조합 하나가 남는다.

**풀이.** $(0,0)$에서 $(5,2)$까지의 최단 경로는 오른쪽 이동 R 5개와 위 이동 U 2개로 이루어진 길이 7 목록과 1:1로 대응한다. 그런 목록은 7개 자리 중 U가 놓일 2자리를 고르면 완전히 결정된다(나머지는 전부 R). 자리 선택은 순서 없는 선택이므로 조합으로

$$
\binom{7}{2} = \frac{7 \cdot 6}{2} = 21\text{가지}
$$

**복기.** "복잡한 대상(경로)을 익숙한 대상(목록 $\to$ 위치 집합)에 1:1로 옮겨 센다" — 12주차 §1.8의 넣음/뺌 목록과 같은 대응 논법이다. 대응이 1:1임을 한 마디 언급하는 것까지가 서술이다.

### 문제 14

**접근.** "적어도 하나"는 뒤집는다(§1.6) — 부정 "0이 하나도 없음"이면 각 자리 후보가 1~9의 9가지로 줄어든 목록이 된다. 전체에서 빼면 끝난다.

**풀이.** 전체 $U$는 4자리 비밀번호 전부 — 각 자리 10가지의 길이 4 목록이므로 곱셈 원리에 의해 $|U| = 10^4 = 10000$개. "0을 적어도 하나 포함"의 부정은 "어느 자리에도 0이 없음" — 각 자리 후보가 1~9의 9가지이므로 $9^4 = 6561$개(곱셈 원리). 여사건 공식에 의해

$$
10^4 - 9^4 = 10000 - 6561 = 3439\text{개}
$$

**검산.** $9^4 = (9^2)^2 = 81^2 = 6561$ ✓. 예제 2.3과 자릿수만 다른 같은 뼈대다 — 훈련 2까지 합치면 세 번째 반복이다.

### 문제 15

**접근.** 훈련 3의 뼈대 그대로 — 3집합 포함–배제. 일곱 항(단일 3 + 쌍 3 + 삼중 1)을 전부 배수 세기 $\lfloor 1000/d \rfloor$로 계산하고 부호 리듬(홀수 $+$, 짝수 $-$)으로 결합한다. 쌍 겹침의 $d$는 공배수 — $6, 10, 15$, 삼중은 $30$.

**풀이.** $A_2, A_3, A_5$를 각각 1~1000 중 2, 3, 5의 배수 집합이라 하면 구하는 것은 $|A_2 \cup A_3 \cup A_5|$이다. 단일 항: $|A_2| = \lfloor 1000/2 \rfloor = 500$, $|A_3| = \lfloor 1000/3 \rfloor = 333$, $|A_5| = \lfloor 1000/5 \rfloor = 200$. 쌍 겹침(공배수의 배수): $|A_2 \cap A_3| = \lfloor 1000/6 \rfloor = 166$, $|A_2 \cap A_5| = \lfloor 1000/10 \rfloor = 100$, $|A_3 \cap A_5| = \lfloor 1000/15 \rfloor = 66$. 삼중 겹침: $|A_2 \cap A_3 \cap A_5| = \lfloor 1000/30 \rfloor = 33$. 3집합 포함–배제에 의해

$$
500 + 333 + 200 - 166 - 100 - 66 + 33 = 734\text{개}
$$

**검산.** 부분합으로 — $500 + 333 + 200 = 1033$, $1033 - 332 = 701$, $701 + 33 = 734$ ✓. 훈련 3(1~120에서 88개)과 같은 구조이고, $\frac{88}{120}$과 $\frac{734}{1000}$이 비슷한 비율인 것도 정황 검산이 된다.

### 문제 16

**접근.** 13주차 예제 2.2의 세기 증명을 이번 주 언어로 완성한다 — "갑" 기준 분할이 서로소이고 전체를 덮음을 명시한 뒤, 이번 주에 공식화한 덧셈 원리를 인용한다.

**풀이.** $1 \le k \le n-1$인 경우를 증명한다(13주차 예제 2.2의 명제 조건 — $k = 0$이면 $\binom{n-1}{-1}$이, $k = n$이면 $\binom{n-1}{n}$이 조합의 정의 범위 $0 \le k \le n$을 벗어나 정의되지 않는다). $n$명의 사람 중 $k$명을 뽑는 방법의 수는 크기 $k$ 부분집합의 개수 $\binom{n}{k}$이다(조합의 정의). 특정 인물 "갑"을 고정하자. 크기 $k$ 부분집합 전체를 두 부류로 나눈다 — 갑을 포함하는 것과 포함하지 않는 것. 한 부분집합이 갑을 포함하면서 동시에 포함하지 않을 수는 없으므로 두 부류는 서로소이고, 모든 부분집합은 둘 중 한 부류에 속하므로 전체를 덮는다. 갑을 포함하는 부류: 갑을 미리 넣고 나머지 $n-1$명 중 $k-1$명을 고르는 것과 1:1로 대응하므로 $\binom{n-1}{k-1}$개. 갑을 포함하지 않는 부류: 갑을 제외한 $n-1$명 중 $k$명을 고르는 것과 1:1로 대응하므로 $\binom{n-1}{k}$개. 서로소 분할이므로 덧셈 원리에 의해

$$
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \qquad \blacksquare
$$

**채점 기준.** ① 세는 대상(크기 $k$ 부분집합)의 선언 ② 분할의 서로소$\cdot$완전성 언급 ③ 각 부류의 개수 논증(1:1 대응) — 셋 다 있어야 통과다.

**검산.** 문제 5의 수치($n = 7$, $k = 2$: $21 = 6 + 15$)가 이 증명의 한 사례다 ✓.

### 문제 17

**접근.** 두 방법 중 하나면 통과다 — 방법 1은 이항정리에 수를 대입하는 한 줄, 방법 2는 "같은 대상을 두 방법으로 센다"는 세기 논증이다. 여기서는 둘 다 적는다.

**풀이 1 (이항정리 대입).** 이항정리 $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$에 $x = 1$, $y = 1$을 대입하면

$$
2^n = (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} \cdot 1^{n-k} \cdot 1^k = \sum_{k=0}^{n} \binom{n}{k} \qquad \blacksquare
$$

**풀이 2 (두 방법으로 세기).** $n$원소 집합의 부분집합 전체를 두 방법으로 센다. 방법 ① — 크기별로: 크기 $k$인 부분집합은 $\binom{n}{k}$개(조합의 정의)이고, 크기가 다른 부류끼리는 서로소이며 $k = 0, 1, \dots, n$이 전체를 덮으므로 덧셈 원리에 의해 총수는 $\sum_{k=0}^{n} \binom{n}{k}$. 방법 ② — 원소별로: 부분집합 하나는 원소마다 넣음/뺌을 정한 길이 $n$ 목록과 1:1로 대응하므로(12주차 §1.8) 곱셈 원리에 의해 총수는 $2^n$. 같은 집합의 개수를 두 방법으로 센 것이므로 두 값은 같다: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$. $\blacksquare$

**복기.** 풀이 2가 "세기 논증"의 표준형이다 — 같은 대상을 두 방법으로 세면 등식이 증명된다(13주차 문제 20). 좌변의 덧셈 원리 인용이 이번 주의 보강 지점이다.

### 문제 18

**접근.** "여자 적어도 1명"의 부정은 "여자 0명" — 곧 전원 남자다. 전체에서 전원 남자인 경우를 빼는 여사건 세기.

**풀이.** 전체 $U$는 9명 중 3명을 뽑는 위원회 전부 — $|U| = \binom{9}{3} = \dfrac{9 \cdot 8 \cdot 7}{3!} = 84$가지. "여자 적어도 1명"의 부정은 "여자가 한 명도 없음", 곧 3명 전원을 남자 5명에서 뽑는 경우 — $\binom{5}{3} = 10$가지. 여사건 공식에 의해

$$
\binom{9}{3} - \binom{5}{3} = 84 - 10 = 74\text{가지}
$$

**검산.** 정면 돌파와 대조 — 여자 1명: $\binom{4}{1}\binom{5}{2} = 4 \times 10 = 40$, 여자 2명: $\binom{4}{2}\binom{5}{1} = 6 \times 5 = 30$, 여자 3명: $\binom{4}{3} = 4$. 서로소 세 경우의 합 $40 + 30 + 4 = 74$ ✓ — 문제 19에서 이 셈이 다시 쓰인다.

### 문제 19

**접근.** $4 \times 28$이 세는 대상의 정체부터 밝힌다 — 그것은 ("지정된 여자 1명", 나머지 2명)의 **쌍**이지 위원회가 아니다. 위원회 하나가 이 절차로 몇 번 만들어지는지, 여자 수별로 추적한다. 12주차 문제 17(악수 $5 \times 4 = 20$)과 같은 유형의 오류다.

**풀이.** 오류: 이 절차는 위원회가 아니라 (먼저 뽑은 여자, 나머지 2명의 집합)의 쌍을 센다. 여자가 $j$명인 위원회는 "먼저 뽑는 여자"를 그중 누구로 하느냐에 따라 $j$가지 서로 다른 경로로 만들어지므로 **$j$번씩** 세어진다. 실제로 — 여자 1명인 위원회 $\binom{4}{1}\binom{5}{2} = 40$개는 1번씩, 여자 2명인 위원회 $\binom{4}{2}\binom{5}{1} = 30$개는 2번씩, 여자 3명인 위원회 $\binom{4}{3} = 4$개는 3번씩 세어져

$$
40 \times 1 + 30 \times 2 + 4 \times 3 = 40 + 60 + 12 = 112
$$

가 된 것이다. 각 위원회를 정확히 한 번씩 세는 참값은 74(문제 18)다.

**복기.** "각 대상이 **정확히 한 번** 세어지는가?" — 모든 세기의 점검 기준이다. 포함–배제(두 번 센 것을 빼기), 순서 지우기(같은 집합을 $k!$번 센 것을 나누기), 그리고 이 문제(대상 아닌 쌍을 센 것) 전부가 이 한 물음으로 진단된다.

### 문제 20

**접근.** (a)는 확인 5의 원소별 세기 표를 두 문장으로 옮기는 일이다. (b)는 이번 파트 내내 답이 아니라 서술을 요구받은 경험 — 채점 기준 상자 — 을 일반화한다.

**풀이.** (예시 답안) (a) $|A| + |B|$라는 계산에서 $A \cap B$의 원소는 $A$의 명단에서 한 번, $B$의 명단에서 한 번 — 합계 두 번 세어지고, 나머지 원소는 한 번씩만 세어진다. 각 원소가 정확히 한 번씩 세어지게 만들려면, 두 번 세어진 원소의 개수만큼 — 곧 $|A \cap B|$를 — 한 번 빼야 한다. (b) 세기의 답은 "가짓수가 그 값일 수밖에 없는 이유"를 대응$\cdot$분할$\cdot$원리 인용으로 서술해야 완성되므로, 모든 세기 문제가 작은 증명 문제다. 특히 "같은 대상을 두 방법으로 센다"(문제 17)와 "각 대상이 정확히 한 번 세어지는지 검사한다"(문제 19)는 그대로 증명 전략의 훈련이다.

**복기.** (a)를 3집합으로 확장하면 확인 6의 항별 추적이 되고, 그 추적을 일반 $n$집합으로 밀면 일반 포함–배제가 된다 — 이 확장은 31주차 귀납법 이후의 일이다.

### 채점 가이드

- 문제 1(백지 테스트) 만점 + 11, 16, 17번 중 2개 이상 통과 $\to$ 통과. 15주차로 간다.
- 세기 답은 맞는데 서술이 없음 $\to$ 12주차 서술 규범(§1.9) 재독 후, 7~10번을 서술 포함으로 재작성한다.
- 12, 14, 15번에서 틀림 $\to$ 이번 주 §1.4~1.6과 훈련 1~3을 재복습한다.
- 19번을 설명하지 못함 $\to$ 13주차 문제 11(순서 지우기)과 12주차 문제 17을 재복습한다 — "몇 번씩 세어지는가"가 이 파트 전체의 점검 기준이다.
- 6, 11번에서 서로소 언급이 빠짐 $\to$ §1.3 해부 표와 예제 2.1을 재필사한다.

---

**다음 주 예고:** 4부 '직접 증명'이 시작된다. 1~2주차에서 몸으로 익힌 3단계 틀을 공식 규격 — 정리$\cdot$명제$\cdot$보조정리라는 용어, 증명의 서식 — 으로 정비하고, 소수$\cdot$유리수까지 소재를 넓힌다. 지금까지 준비한 집합$\cdot$논리$\cdot$세기의 언어가 전부 본편에 투입된다.