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

내용

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\)를 서로소 조각들의 크기로 표현한다

확인 11. 덧셈 원리를 \(A\)와 \(B\)에 곧바로 적용해 \(|A \cup B| = |A| + |B|\)라고

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

답

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

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

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

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

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

확인 12. 등식 \(A \cup B = (A - B) \cup B\)에 대해 두 가지를 확인해 보자.

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

\(A \cup B\) 전체가 되는 이유는?

답

① \(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회. 서로소 분할을 얻었으므로 더할 수 있다.

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

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

답

\(|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에서 수치와 벤 다이어그램으로 확인해 두었다.)

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

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

답

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

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

4단계 — 대입으로 완성.

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

\(|A \cup B| = \underline{\qquad}\).

답

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

확인 16. \(A\)와 \(B\)가 서로소인 특수한 경우, 방금 증명한 공식은 어떤 식이

되는가.

답

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

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

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

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

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

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

확인 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\)는 무엇의 배수 집합인가?

답

① \(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| = 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를 적어도 하나 포함하는 것은 몇 개인가?

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

확인 18. 풀이에 들어가기 전에 세 가지를 적어 보자.

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

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

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

답

① 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}\)	곱셈 원리 두 번 + 여사건 공식

확인 19. 대응표의 (1)(2)(3)을 채워 보자.

답

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

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

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

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

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

백지 암기 대상

겹침 세기의 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(백지 테스트)을 하나라도 틀리면 해당 주차부터 재복습한 뒤 넘어간다.
채점 후 틀린 문제는 힌트 상자와 해설의 ‘접근’까지만 읽고 한 번 더 시도한다 — 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

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

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

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

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

기본 ●○○#

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

힌트

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

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

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

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

힌트

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

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

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

힌트

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

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

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

힌트

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

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

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

힌트

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

한 줄 적어 본다 — \(n\)과 \(k\)가 무엇인가.

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

힌트

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

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

표준 ●●○#

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

힌트

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

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

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

힌트

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

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

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

힌트

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

원리로 잇는다.

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

힌트

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

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

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

힌트

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

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

것이 채점 포인트다.

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

힌트

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

세 항 모두 \(\lfloor 100/d \rfloor\)로 센다.

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

힌트

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

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

적는다.

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

힌트

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

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

도전 ●●●#

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

힌트

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

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

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

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

힌트

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

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

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

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

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

힌트

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

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

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

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

힌트

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

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

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

힌트

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

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

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

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

힌트

(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 — “단계인가 경우인가”의 판정 연습

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

해설#

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

준비 운동#

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

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

일반항 \(\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 \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\).

\[ 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\)세기의 언어가 전부 본편에 투입된다.