# 12주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 세기 논증을 함께 만들기 완성된 풀이를 먼저 보이지 않는다. 서술 규범 ①②③을 따라 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 회장·부회장 뽑기 **문제.** 학생 5명 중 회장 1명, 부회장 1명을 뽑는 가짓수는? (겸직 불가) 준비 운동 4번이 바로 이 문제였다. 이번에는 규범대로 만든다. **설계 — 쓰기 전에 정하는 두 가지.** 증명의 번역표(가정 $\to$ 출발점, 목표 $\to$ 도착점)가 세기에서는 다음 꼴이 된다: 세는 대상의 구조가 출발점, 그 개수가 도착점이다. | | **말** | **번역** | |---|---|---| | 세는 대상 (출발점) | 뽑기의 결과 하나 | (회장, 부회장)의 길이 $\underline{\quad}$ 목록, 반복 $\underline{\quad}$ | | 목표 (도착점) | 가능한 결과 전부의 수 | 그런 목록의 개수 | :::{container} quotebox **확인 13.** 표의 두 빈칸을 채워 보자. 그리고 결과가 집합 {갑, 을}이 아니라 목록 (갑, 을)인 이유를 문제의 조건에서 찾아 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 길이 **2**, 반복 **금지**. 회장 자리와 부회장 자리가 구별되므로 — (갑, 을)과 (을, 갑)은 다른 인사 결과이므로 — 순서 있는 목록이고, 겸직 불가 조건이 같은 사람의 재등장을 막으므로 반복 금지다. 구조 선언(규범 ①)이 끝났다. ::: **규범 ② — 단계별 개수와 무관 확인.** :::{container} quotebox **확인 14.** 1번째 항목(회장)의 선택지는 5가지다. 2번째 항목(부회장)의 선택지는 몇 가지이고, 그 개수는 1번째 선택과 무관한가? ::: :::{admonition} 답 :class: quotebox dropdown 4가지 — 회장으로 뽑힌 1명이 빠진다. 누가 회장이 되든 빠지는 것은 정확히 1명이므로, 후보의 **내용**은 회장에 따라 달라져도 **개수**는 4로 일정하다 (§1.4 확인 6). 곱셈 원리의 조건이 충족된다. ::: **규범 ③ — 원리 인용과 계산.** :::{container} quotebox **확인 15.** 마지막 문장을 완성해 보자: "곱셈 원리에 의해 $\underline{\quad} \times \underline{\quad} = \underline{\quad}$가지이다. $\blacksquare$" ::: :::{admonition} 답 :class: quotebox dropdown $5 \times 4 = 20$가지. 준비 운동 4번의 답 20이 세 문장의 논증을 얻었다. ::: **완성본.** 방금 만든 세 줄을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 뽑기의 결과는 (회장, 부회장)의 길이 2 목록이다 — 자리가 구별되므로 순서가 있고, 겸직 불가이므로 반복 금지다. | 규범 ① 구조 선언. 세는 대상의 정체(정의 12.1)를 문제의 조건으로 확정한다. | | 회장은 5가지, 부회장은 회장을 제외한 4가지 — 누가 회장이든 개수는 4로 일정하다. | 규범 ② 단계별 개수 + 무관 확인. 곱셈 원리의 핵심 조건을 검사하는 줄이다. | | 곱셈 원리에 의해 $5 \times 4 = 20$가지이다. $\blacksquare$ | 규범 ③ 원리 인용(근거 ④)과 계산. | **이 세 줄이 옳은지 실험할 수 있다.** 학생 수를 3명으로 줄이면 전부 나열이 가능해진다 — 논증과 나열이 같은 답을 주는지 대조해 보자. :::{container} quotebox **확인 16.** 학생이 {갑, 을, 병} 3명일 때 (회장, 부회장) 목록을 전부 나열하고, 개수가 같은 논증의 답 $3 \times 2$와 일치하는지 확인해 보자. ::: :::{admonition} 답 :class: quotebox dropdown (갑,을), (갑,병), (을,갑), (을,병), (병,갑), (병,을) — 6개. $3 \times 2 = 6$ ✓. 나열은 작은 사례의 검산 도구로 남고, 논증은 나열이 불가능한 크기까지 답을 보장한다 — 1주차에서 예시 확인(검산)과 문자 증명(보장)이 나눠 맡던 역할 분담이 세기에서도 그대로다. ::: ### 예제 2.2 — 반복 허용 **문제.** 참/거짓 5문항 답안지는 몇 가지인가? 이번에는 설계(규범 ①)만 함께 하고, 서술은 완성본으로 본다. :::{container} quotebox **확인 17.** 번역표를 채워 보자. 세는 대상: T/F 두 기호로 된 길이 $\underline{\quad}$ 목록, 반복 $\underline{\quad}$. — 반복의 허용 여부는 문제의 어떤 사정에서 읽어 내는가? ::: :::{admonition} 답 :class: quotebox dropdown 길이 **5**, 반복 **허용**. 1번 문항에 T라고 답했어도 2번 문항에 다시 T라고 답할 수 있다 — 앞 문항의 답이 뒤 문항의 선택지를 줄이지 않는다. 예제 2.1(겸직 불가 = 반복 금지)과 정반대의 사정이고, 이 판단이 $n^k$와 $n(n-1)\cdots$ 중 어느 공식이 작동하는지를 가른다. ::: **풀이.** 답안지는 T/F 두 기호로 된 길이 5 목록이다(반복 허용). 매 문항 2가지씩이고 각 단계의 선택지 개수는 앞 답과 무관하다. 곱셈 원리에 의해 $2^5 = 32$가지이다. $\blacksquare$ 4주차 문제 9와 연결된다 — 크기 5인 집합의 부분집합 개수도 $2^5$였다. 우연이 아니다: 답안지 하나를 "T라고 답한 문항들의 집합"에 대응시키면 답안지와 부분집합이 1:1이다 — §1.8의 넣음/뺌 대응에서 기호의 이름만 바꾼 것이다. ### 예제 2.3 — 전부 세우기와 일부 세우기 **문제.** 책 7권 중 (a) 7권 전부를 책장에 일렬로 꽂는 가짓수, (b) 3권만 골라 일렬로 꽂는 가짓수는? 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 18.** (a)와 (b) 각각에 대해 — 세는 대상은 무슨 목록이고, §1.6 표의 어느 행이 작동하며, (b)의 3번째 항목의 선택지는 몇 가지인가? ::: :::{admonition} 답 :class: quotebox dropdown (a) 7권 전부의 반복 없는 길이 7 목록 — 반복 금지에서 $k = n$인 경우, 곧 팩토리얼이다. (b) 7권에서 고른 반복 없는 길이 3 목록 — 반복 금지 행이고, 3번째 항목은 이미 꽂힌 2권이 빠져 $7 - 2 = 5$가지다. ::: **풀이.** (a) 꽂는 결과는 7권 전부의 반복 없는 길이 7 목록이다. 정의 12.2에 의해 $7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040$가지이다. (b) 꽂는 결과는 7권에서 고른 반복 없는 길이 3 목록이다. 자리별 선택지는 $7, 6, 5$가지로 앞 선택과 개수가 무관하므로, 곱셈 원리에 의해 $7 \times 6 \times 5 = 210$가지이다. $\blacksquare$ (b)를 팩토리얼로 쓰면 $$ 7 \times 6 \times 5 = \frac{7 \times 6 \times 5 \times 4!}{4!} = \frac{7!}{4!} $$ 이다. 일반화하면 — $n$개에서 고른 반복 없는 길이 $k$ 목록의 수는 $\dfrac{n!}{(n-k)!}$이다. 이 유도를 문제 12에서 일반 문자로 완성한다. 이번 풀이는 표 없이 **산문**으로 적었다. 표는 연습 단계의 장치이고, 실전의 세기 답안은 처음부터 끝까지 이런 산문 서너 문장이다. ### 관찰 — 세 풀이의 같은 뼈대 예제 2.1, 2.2, 2.3은 소재만 다를 뿐 뼈대가 같다. 대응표의 빈칸을 채워 보자. :::{container} quotebox **확인 19.** 빈칸 (1)~(4)를 채워 보자. ① 구조 선언 — 2.1: 길이 2, 반복 금지 / 2.2: $\underline{\quad(1)\quad}$ / 2.3(b): 길이 3, 반복 금지 ② 단계별 개수 — 2.1: 5, 4 / 2.2: $\underline{\quad(2)\quad}$ / 2.3(b): $\underline{\quad(3)\quad}$ ③ 원리 인용$\cdot$계산 — 2.1: $5 \times 4 = 20$ / 2.2: $2^5 = 32$ / 2.3(b): $\underline{\quad(4)\quad}$ ::: :::{admonition} 답 :class: quotebox dropdown (1) 길이 5, 반복 허용 (2) 매 단계 2가지 (3) 7, 6, 5 (4) $7 \times 6 \times 5 = 210$. 세 풀이 모두 정확히 이 세 걸음이다 — §1.9에서 규범으로 선언한 것이 실제로 모든 풀이의 뼈대였음을 확인했다. ::: 방금 확인한 뼈대가 곧 이번 주의 틀이다. :::{admonition} 백지 암기 대상 :class: keybox **세기 서술의 3단계 틀** ① 세는 대상의 구조를 선언한다(무엇의, 길이 몇의 목록인가 — 반복 허용 여부까지) $\to$ ② 단계별 선택지의 개수를 세고, 개수가 앞 단계와 무관함을 확인한다 $\to$ ③ 곱셈 원리를 인용해 계산한다 ::: ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 공식과 조건의 빈칸 (1) 길이 $k$, 기호 $n$종, 반복 허용 목록의 수: $\underline{\quad}$ (2) $n$개 전부의 반복 없는 나열의 수: $\underline{\quad}$ (3) $0! = \underline{\quad}$ (이유: 빈 목록이 $\underline{\quad}$개 있으므로) (4) $\dfrac{9!}{7!} = \underline{\quad}$ (계산) (5) 곱셈 원리의 핵심 조건: 각 단계의 선택지 $\underline{\qquad}$가 앞 단계의 결과와 무관해야 한다. ### 훈련 2 ●●○ — 서술과 근거를 함께 이번에는 서술 규범의 문장과 근거 문구도 빈칸이다. **문제.** 숫자 0~9로 만든 세 자리 비밀번호 중 같은 숫자를 두 번 쓰지 않는 것은 몇 가지인가? **서술.** 비밀번호는 열 개의 숫자 기호로 된 길이 $\underline{\quad(1)\quad}$ 목록이고, 같은 숫자 금지 조건에 의해 반복 $\underline{\quad(2)\quad}$다. 자리별 선택지는 1번째 $10$가지, 2번째 $\underline{\quad(3)\quad}$가지, 3번째 $\underline{\quad(4)\quad}$가지이고, 각 단계의 선택지 $\underline{\quad(5)\quad}$는 앞 선택과 무관하다. $\underline{\quad(6)\quad}$에 의해 $10 \times \underline{\quad(3)\quad} \times \underline{\quad(4)\quad} = \underline{\quad(7)\quad}$가지이다. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 **명제.** $|A| = n$이면 $A$의 부분집합은 $2^n$개다. **논증의 뼈대.** 세기 서술 3단계 틀의 각 칸을 통째로 채운다. (§1.8을 보지 않고 쓴 뒤에 대조한다.) - ① 대응 제작(구조 선언): $\underline{\quad(1)\quad}$ - ② 단계별 개수와 무관 확인: $\underline{\quad(2)\quad}$ - ③ 원리 인용과 결론: $\underline{\quad(3)\quad}$ (이 훈련이 문제 13의 예행연습이다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 모든 답에 "무엇의 목록인지 + 곱셈 원리"를 한 줄이라도 서술한다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "답: 20"은 0점이고, "(회장, 부회장)의 길이 2 목록이고 자리별 5, 4가지이므로 곱셈 원리에 의해 20가지"가 만점이다. 서술 규범 ①②③(§1.9)이 채점표다. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** 다음을 계산하시오. (a) $6!$ (b) $\dfrac{8!}{6!}$ (c) $\dfrac{10!}{8! \, 2!}$ :::{admonition} 힌트 :class: quotebox dropdown 나눗셈 꼴은 전부 전개하지 않는다 — $8! = 8 \times 7 \times 6!$처럼 겹치는 꼬리를 드러내 약분부터 한다. ::: **2.** 자음 4종, 모음 3종에서 (자음, 모음, 자음) 꼴 글자를 만드는 가짓수는? (같은 자음 재사용 허용) :::{admonition} 힌트 :class: quotebox dropdown 규범 ① 구조 선언부터 — (자음, 모음, 자음)의 길이 3 목록이다. "재사용 허용"이라는 조건이 반복 허용의 신호이고, 3번째 자리의 선택지 개수를 정한다. ::: **3.** 참/거짓 4문항 + 삼지선다 2문항으로 된 시험의 답안지 가짓수는? :::{admonition} 힌트 :class: quotebox dropdown 자리마다 선택지 개수가 달라도 곱셈 원리는 그대로 작동한다 — 코드 문제 (§1.9, $26 \times 10 \times 10$)가 이미 그랬다. 답안지가 길이 몇의 목록인지부터 선언한다. ::: **4.** 다음 중 같은 것끼리 짝지으시오: $(1, 2, 2)$, $\{1, 2, 2\}$, $(2, 1, 2)$, $\{2, 1\}$, $(1, 2)$ (목록$\cdot$집합의 상등 기준을 각각 적용) :::{admonition} 힌트 :class: quotebox dropdown 목록은 길이와 위치별 항목까지, 집합은 원소만 본다(§1.3 확인 4에서 두 판정을 연습했다). 다섯 대상을 목록과 집합으로 먼저 분류하면 비교할 짝이 줄어든다. ::: **5.** $A = \{a, b, c\}$에서 길이 2 목록을 (a) 반복 허용으로 모두 나열하고 개수를 확인하시오. (b) 반복 금지로 모두 나열하고 개수를 확인하시오. :::{admonition} 힌트 :class: quotebox dropdown 빠뜨림$\cdot$겹침 없이 나열하려면 순서 규칙이 필요하다 — 1번째 항목별로 묶어 $a$로 시작하는 것부터 차례로 적는다(§1.4의 격자가 그 규칙이다). 다 센 뒤 공식($3^2$, $3 \times 2$)과 대조한다. ::: **6.** 지역번호(3자리, 0으로 시작 안 함) + 국번(4자리) 전화번호의 가짓수를 곱셈 원리로 서술해 구하시오. :::{admonition} 힌트 :class: quotebox dropdown "0으로 시작 안 함"은 첫 자리의 선택지 개수만 줄인다 — 나머지 자리는 10가지 그대로다. 자리별 개수를 각각 명시하고 곱한다. ::: ### 표준 ●●○ **7.** 학생 5명을 일렬로 세우는 가짓수를 구하고, 그중 특정 학생 A가 맨 앞에 서는 경우의 수를 구하시오. :::{admonition} 힌트 :class: quotebox dropdown 전부 세우기는 $n!$(정의 12.2). 고정 조건은 그 자리의 선택지를 1가지로 만든다 — 맨 앞이 정해지면 남는 것은 몇 명의 전부 세우기인가. ::: **8.** 학생 5명 중 A와 B가 서로 이웃하여 서는 경우의 수를 구하시오. (힌트: 둘을 한 묶음으로) :::{admonition} 힌트 :class: quotebox dropdown A와 B를 한 덩어리로 보면 배열할 대상이 [AB묶음]과 나머지 3명 — 4개가 된다. 다 센 뒤, 묶음 내부에서 A와 B의 자리를 바꾸는 경우를 잊지 않는다. ::: **9.** 세 자리 자연수는 모두 몇 개인가? 곱셈 원리 서술과 함께 구하고, "첫 자리가 특별한 이유"를 한 문장으로 쓰시오. **10.** 숫자 1, 2, 3, 4, 5를 한 번씩 써서 만든 다섯 자리 수 중 짝수는 몇 개인가? (힌트: 어느 자리를 먼저 정할지가 요령) :::{admonition} 힌트 :class: quotebox dropdown 제약이 가장 센 자리(일의 자리 — 짝수여야 한다)부터 정한다. 만의 자리부터 정하면 일의 자리의 선택지 개수가 앞 선택에 따라 달라져 곱셈 원리의 조건이 깨진다 — 순서를 바꾸는 것만으로 조건이 살아난다. ::: **11.** $|A| = 3$, $|B| = 5$일 때 $|A \times B|$와 $|B \times B \times B|$를 구하고, 각각 어떤 목록의 개수인지 쓰시오. **12.** 반복 없는 길이 $k$ 목록의 수가 $\dfrac{n!}{(n-k)!}$임을 곱셈 원리로 유도하시오. ($k$번째 항의 선택지가 몇 가지인지 명시할 것) :::{admonition} 힌트 :class: quotebox dropdown $k$번째 항의 선택지는 확인 8에서 셌다 — 이미 쓴 기호 $k-1$개가 빠진다. 곱 $n(n-1)\cdots(n-k+1)$을 팩토리얼 분수로 바꾸려면 $\frac{(n-k)!}{(n-k)!}$을 곱한다(근거 ③ — 1을 곱하는 변형). ::: **13.** $|\mathcal{P}(A)| = 2^{|A|}$의 증명(개념 절의 목록 대응)을 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 3의 뼈대 그대로다. 대응의 두 방향 — 부분집합에서 목록으로, 목록에서 부분집합으로 — 을 각각 한 문장씩 적어야 "빠짐도 겹침도 없다"가 서술된다. ::: **14.** 홀수 숫자(1, 3, 5, 7, 9)만으로 이루어진 네 자리 수는 몇 개인가? 그중 각 자리 숫자가 모두 다른 것은 몇 개인가? :::{admonition} 힌트 :class: quotebox dropdown 두 물음은 §1.6 표의 두 행(반복 허용 / 반복 금지)의 대비다 — 재료(기호 5종)와 길이(4)는 같고 조건만 다르다. ::: ### 도전 ●●● :::{admonition} 새 도구 — 전체에서 빼기 (여사건 세기) :class: quotebox "적어도 하나 ~"를 정면으로 세면 경우가 여러 갈래로 갈라진다(1개인 경우, 2개인 경우, …). 방향을 바꾼다: 조건의 부정("하나도 ~ 아님")이 한 덩어리로 세어지면, **전체에서 그 개수를 뺀 것**이 답이다. "적어도 하나"($\exists$)의 부정이 "전부 아님"($\forall\neg$)이라는 11주차 부정 규칙이 세기 전략이 되는 지점이다. 빼기의 정당화(전체 = 조건을 만족하는 것 + 만족하지 않는 것, 겹침 없이)는 14주차 덧셈 원리에서 정식화한다 — 지금은 인정하고 쓴다. ::: **15.** 길이 5의 이진 문자열(0/1) 중 **적어도 하나의 1을 포함**하는 것은 몇 개인가? (힌트: "적어도 하나"의 부정은 "하나도 없다" — 11주차 부정 규칙을 세기에 적용: 전체에서 나쁜 경우를 빼기.) :::{admonition} 힌트 :class: quotebox dropdown 전체 개수는 예제 2.2에서 셌다. "1이 하나도 없는" 문자열이 몇 개인지 — 나열해 보면 짧다. ::: **16.** 알파벳 $\{a, b, c\}$로 만든 길이 5의 회문(palindrome: 앞뒤로 읽어도 같은 문자열, 예: abcba)은 몇 개인가? (힌트: 회문은 어느 자리들이 자유로운가?) :::{admonition} 힌트 :class: quotebox dropdown abcba에서 4번째 자리는 2번째와, 5번째 자리는 1번째와 같아야 한다 — 스스로 고를 수 있는 자리가 몇 개인지부터 센다. 자유로운 자리들의 목록과 회문이 1:1로 대응한다. ::: **17.** 다음 풀이의 오류를 찾으시오: "5명 중 악수할 2명을 뽑는 가짓수는, 첫 사람 5가지, 둘째 사람 4가지이므로 $5 \times 4 = 20$가지다." (실제로 악수 쌍은 10가지이다. 무엇이 두 번씩 세어졌는가? — 13주차의 예고) :::{admonition} 힌트 :class: quotebox dropdown $5 \times 4$ 자체는 옳은 세기다 — 문제는 그것이 세는 대상의 정체다. 규범 ①로 돌아가 선언해 보자: $5 \times 4$가 세는 것은 목록인가 집합인가. 그리고 악수 쌍은 목록인가 집합인가. ::: **18.** $|A| = 3$, $|B| = 4$일 때, $A$의 각 원소에 $B$의 원소를 하나씩 배정하는 방법(= $A$에서 $B$로 가는 함수, 40주차 예고)은 몇 가지인가? 어떤 목록과 대응되는지 서술하시오. **19.** 문제 18에서 서로 다른 원소에 서로 다른 값을 배정하는 방법(= 단사함수, 41주차 예고)은 몇 가지인가? :::{admonition} 힌트 :class: quotebox dropdown "서로 다른 값" 조건이 §1.6 표의 어느 행으로 번역되는지부터 정한다 — 문제 18과 재료는 같고 조건 하나만 바뀌었다. ::: **20.** (서술) 곱셈 원리가 **적용되지 않는** 상황의 예를 하나 설계하시오: 2단계 선택인데, 1단계의 결과에 따라 2단계의 선택지 **개수**가 달라지는 상황. 그리고 그런 경우 어떻게 세야 할지(경우 나누기) 한 문장으로 제안하시오. :::{admonition} 힌트 :class: quotebox dropdown 곱셈 원리의 핵심 조건(§1.4)을 일부러 부수면 된다 — 1단계에서 무엇을 골랐는지에 따라 2단계의 가짓수 자체가 달라지는 규칙(조건부 제한)을 하나 넣는다. 격자로 그리면 행마다 칸 수가 다른 그림이 나온다. ::: ## 백지 재현 — 복습 프로토콜 권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다. **1차 시도 (4일차) — 틀 카드 허용.** 세기 서술의 3단계 틀과 §1.6의 표(반복 허용/금지)만 펴 놓고, 예제 2.1과 §1.8의 $2^n$ 논증을 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다. **2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다: - [ ] 목록의 정의(순서 있음, 중복 허용)와 상등 기준, 집합과의 차이를 썼다. - [ ] 곱셈 원리를 핵심 조건("선택지의 **개수**가 앞 단계와 무관")까지 포함해 진술했다. - [ ] $n^k$ / $\dfrac{n!}{(n-k)!}$ / $n!$이 각각 어떤 세기인지 구분해 썼다. - [ ] $0! = 1$의 이유를 빈 목록으로 설명했다. - [ ] $|\mathcal{P}(A)| = 2^n$의 논증(넣음/뺌 목록 대응)을 재현했다. - [ ] 세기 답안의 서술 규범 ①②③을 적고, 예제 2.1을 그 규범대로 다시 썼다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 구조 선언 문장이 나오지 않는다 | §1.9 규범 ①과 예제 2.1 확인 13 — 길이$\cdot$반복 여부를 문제의 조건에서 읽는다 | | 곱셈인지 아닌지 판단이 안 된다 | §1.4 격자 — 행마다 칸 수가 같은가를 묻는다. 다르면 문제 20의 상황이다 | | 반복 허용/금지 판단이 흔들린다 | 예제 2.2 확인 17 — 앞 선택이 뒤 선택지를 줄이는지를 조건에서 찾는다 | | $n - k + 1$이 자꾸 $n - k$가 된다 | §1.6 확인 8 — 빼는 것은 자리 번호가 아니라 이미 쓴 개수 $k - 1$이다 | | $2^n$ 논증이 재현되지 않는다 | §1.8 확인 10 — 구체 사례($n = 3$)의 대응부터 다시 만든다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $n^k$ (2) $n!$ (3) $1$, $1$ (4) $\dfrac{9!}{7!} = \dfrac{9 \times 8 \times 7!}{7!} = 9 \times 8 = 72$ (5) 개수(가짓수) ※ (5)가 이번 주의 급소다 — "선택지"가 아니라 "선택지의 **개수**"가 무관해야 한다. 내용은 달라져도 된다(확인 6). ### 빈칸 사다리 — 훈련 2 (1) $3$ (2) 금지 (3) $9$ (4) $8$ (5) 개수 (6) 곱셈 원리 (7) $10 \times 9 \times 8 = 720$ ※ (3)(4)에서 단계마다 1씩 줄어드는 것이 반복 금지의 표식이다. 3번째 자리는 이미 쓴 숫자 2개가 빠져 $10 - 2 = 8$가지 — 확인 8의 $k - 1$ 규칙 그대로다. ### 빈칸 사다리 — 훈련 3 (1) $A$의 원소를 $x_1, \dots, x_n$으로 나열하면, 부분집합 $X \subseteq A$마다 "각 $x_i$를 넣었는가/뺐는가"의 길이 $n$ 목록이 하나 정해지고, 거꾸로 그런 목록마다 부분집합이 정확히 하나 정해진다 — 부분집합과 넣음/뺌 목록은 1:1이다. (2) 목록의 각 자리는 넣음/뺌의 2가지이고(반복 허용), 각 자리의 선택지 개수는 앞 자리의 선택과 무관하다. (3) 곱셈 원리에 의해 목록은 $2^n$개이고, 1:1 대응에 의해 부분집합도 $2^n$개다. $\blacksquare$ ※ ①의 "거꾸로" 문장을 빠뜨리는 경우가 많다 — 그 문장이 없으면 "목록이 부분집합보다 많을(또는 적을) 가능성"이 배제되지 않아 세기가 옮겨지지 않는다. ### 문제 1 **접근.** 팩토리얼은 정의대로 전부 전개하면 수가 빠르게 커진다. 나눗셈 꼴은 분자를 분모의 팩토리얼이 나올 때까지만 전개해 꼬리를 약분하는 것이 표준 요령이다 — $8! = 8 \times 7 \times 6!$처럼. **풀이.** (a) $6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$. (b) $\dfrac{8!}{6!} = \dfrac{8 \times 7 \times 6!}{6!} = 8 \times 7 = 56$. (c) $\dfrac{10!}{8! \, 2!} = \dfrac{10 \times 9 \times 8!}{8! \times 2} = \dfrac{10 \times 9}{2} = \dfrac{90}{2} = 45$. **복기.** 꼬리 약분 — $\frac{n!}{(n-k)!}$ 꼴은 항상 $n(n-1)\cdots(n-k+1)$로 줄어든다(문제 12의 공식을 거꾸로 읽은 것). (c)의 값 45는 13주차에서 $\binom{10}{2}$라는 이름을 얻고 다시 나타난다. ### 문제 2 **접근.** 규범 ① 구조 선언부터: (자음, 모음, 자음)의 길이 3 목록이고, "재사용 허용"이 반복 허용의 신호다. 자리마다 뽑는 기호의 집합이 다르지만(자음/모음), 곱셈 원리는 자리별 개수만 정확하면 그대로 작동한다. **풀이.** 글자는 (자음, 모음, 자음)의 길이 3 목록이다(자음 재사용 허용). 1번째는 자음 4가지, 2번째는 모음 3가지, 3번째는 자음 4가지 — 재사용이 허용되므로 1번째에 무엇을 썼든 4가지 그대로이고, 각 단계의 선택지 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 $4 \times 3 \times 4 = 48$가지이다. $\blacksquare$ **복기.** 자리마다 기호의 종류가 달라도 되고(§1.9의 코드), 같은 종류가 두 번 나와도 된다(1$\cdot$3번째) — 곱셈 원리가 요구하는 것은 오직 자리별 개수다. ### 문제 3 **접근.** 답안지는 앞 4자리와 뒤 2자리의 규칙이 다른 길이 6 목록이다. 자리마다 선택지 개수가 달라도 — 2, 2, 2, 2, 3, 3 — 곱셈 원리는 각 자리의 개수를 그대로 곱하면 된다. **풀이.** 답안지는 (1번 답, …, 4번 답, 5번 답, 6번 답)의 길이 6 목록이다. 앞 4자리는 각 T/F의 2가지, 뒤 2자리는 각 3가지이고, 각 자리의 선택지 개수는 앞 답과 무관하다. 곱셈 원리에 의해 $$ 2 \times 2 \times 2 \times 2 \times 3 \times 3 = 2^4 \times 3^2 = 16 \times 9 = 144 $$ 가지이다. $\blacksquare$ **검산.** 참/거짓 4문항만이면 $2^4 = 16$(예제 2.2의 축소판), 삼지선다 2문항만이면 $3^2 = 9$ — 두 부분이 독립으로 이어 붙으므로 $16 \times 9$, 앞의 계산과 일치한다. ### 문제 4 **접근.** 다섯 대상을 먼저 목록과 집합으로 분류한다 — 소괄호 셋은 목록, 중괄호 둘은 집합. 목록끼리는 길이부터, 같으면 위치별 항목을 대조하고(정의 12.1), 집합끼리는 원소만 대조한다(3주차). 종류가 다른 것끼리는 같을 수 없다. **풀이.** 같은 것은 $\{1, 2, 2\} = \{2, 1\}$ 한 쌍뿐이다 — 집합의 상등은 원소만 보고, 둘 다 원소가 1과 2다(중복 표기는 무의미, 순서는 무관). 나머지는 전부 서로 다르다: $(1, 2, 2) \neq (2, 1, 2)$ — 길이는 3으로 같지만 1번째 항목이 $1 \neq 2$. $(1, 2)$는 길이가 2이므로 길이 3인 두 목록 어느 쪽과도 다르다(상등의 1차 관문). 집합과 목록은 종류가 다른 대상이므로 $\{2, 1\}$과 $(1, 2)$도 다르다 — 원소가 같아 보여도 한쪽은 순서를 잊고 한쪽은 기억한다. **복기.** 상등 판정의 순서: 종류(집합/목록) $\to$ 길이 $\to$ 위치별 항목. 이 순서로 검사하면 판정이 기계가 된다. ### 문제 5 **접근.** 작은 사례의 전수 나열 — 공식과 개수가 맞는지 대조하는 검산 습관이다 (예제 2.1 확인 16). 빠뜨림$\cdot$겹침을 막는 나열 규칙은 1번째 항목별로 묶기다. **풀이.** (a) 반복 허용, 1번째 항목별로 묶어 나열하면 — $$ (a,a),\ (a,b),\ (a,c),\ (b,a),\ (b,b),\ (b,c),\ (c,a),\ (c,b),\ (c,c) $$ 모두 9개. 공식으로는 매 자리 3가지의 길이 2 목록이므로 $3^2 = 9$ ✓. (b) 반복 금지 — (a)의 나열에서 같은 항목이 겹치는 $(a,a), (b,b), (c,c)$ 세 개를 지우면 $$ (a,b),\ (a,c),\ (b,a),\ (b,c),\ (c,a),\ (c,b) $$ 모두 6개. 공식으로는 $3 \times 2 = 6$ ✓. **복기.** 나열과 공식이 서로를 검사한다 — 나열은 공식의 검산이고, 공식은 나열의 빠뜨림 탐지기다. 새 유형을 만나면 작은 사례로 이 대조를 한 번 하는 습관이 세기 오류의 대부분을 걸러 낸다. ### 문제 6 **접근.** 번호 전체를 하나의 목록으로 선언한다 — 지역 3자리 + 국번 4자리 = 길이 7 목록. "0으로 시작 안 함"은 첫 자리의 선택지 개수만 9로 줄이고, 나머지 여섯 자리는 10가지 그대로다. **풀이.** 전화번호는 숫자 기호로 된 길이 7 목록이다(지역 3자리 + 국번 4자리, 반복 허용). 지역의 첫 자리는 0을 뺀 $1$~$9$의 9가지, 나머지 여섯 자리는 각 $0$~$9$의 10가지이고, 각 자리의 선택지 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 $$ 9 \times 10 \times 10 \times 10 \times 10 \times 10 \times 10 = 9 \times 10^6 = 9{,}000{,}000 $$ 가지이다. $\blacksquare$ **검산.** 제한 없는 길이 7 목록은 $10^7$개인데, 첫 자리 후보가 10 중 9로 줄었으므로 답은 그 $\frac{9}{10}$ — $10^7 \times \frac{9}{10} = 9 \times 10^6$과 일치한다. ### 문제 7 **접근.** 전반부는 전부 세우기 = $n!$(정의 12.2). 후반부의 고정 조건은 그 자리의 선택지를 1가지로 만들어 곱셈 원리에 흡수시킨다 — 맨 앞이 A로 정해지면 남는 것은 나머지 4명의 전부 세우기다. **풀이.** 세우는 결과는 5명 전부의 반복 없는 길이 5 목록이므로, 그 수는 $$ 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 $$ 가지이다. A가 맨 앞에 서는 경우 — 맨 앞은 A의 1가지, 나머지 네 자리는 남은 4명의 반복 없는 나열로 $4! = 24$가지이고, 각 단계의 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 $1 \times 4! = 24$가지이다. $\blacksquare$ **검산.** 맨 앞에 서는 사람으로 전체 120가지를 나누면 다섯 사람이 각각 같은 몫을 가지므로 한 사람 몫은 $120 \div 5 = 24$ — 일치한다. **복기.** "고정 조건 = 선택지 1가지"의 번역은 이후 모든 배치 문제에서 재사용된다. 조건은 세기를 어렵게 하는 것이 아니라 어느 자리의 개수를 바꾸는 것뿐이다. ### 문제 8 **접근.** "이웃" 조건은 자리 하나의 개수 조정으로는 번역되지 않는다 — 대상 자체를 재정의한다: A와 B를 한 덩어리로 묶으면 "이웃"이 저절로 보장되고, 배열할 대상이 [AB묶음]과 나머지 3명, 합해서 4개가 된다. 마지막에 묶음 내부의 배치를 곱하는 것을 잊지 않는다. **풀이.** A와 B를 한 묶음으로 보면, 세우는 결과는 [묶음], C, D, E 네 대상의 반복 없는 길이 4 목록 — $4! = 24$가지다. 묶음 내부의 배치는 (A, B)와 (B, A)의 2가지이고, 외부 배열이 무엇이든 내부 배치의 개수는 2로 일정하다. 곱셈 원리에 의해 $4! \times 2 = 24 \times 2 = 48$가지이다. $\blacksquare$ **검산.** 전체 $5! = 120$ 중 A$\cdot$B가 이웃하는 것이 48 — 이웃하지 않는 것은 72로, 이웃하는 쪽이 적다. 다섯 자리 중 A$\cdot$B가 앉을 자리 쌍은 이웃 4쌍 대 비이웃 6쌍이므로 비율 $48 : 72 = 4 : 6$과 정확히 맞는다. **복기.** **묶음 기법** — 붙어야 하는 대상들을 한 항목으로 재정의하고, 마지막에 묶음 내부의 배치 수를 곱한다. 조건을 "대상의 재정의"로 흡수하는 이 기술은 이후 세기 주차에서 반복해 쓴다. ### 문제 9 **접근.** 세 자리 수를 (백, 십, 일)의 길이 3 목록으로 선언하면, 첫 자리만 규칙이 다르다 — 0이 오면 세 자리 수가 아니게 되기 때문이다. 문제 6과 같은 "첫 자리 특별" 유형이다. **풀이.** 세 자리 자연수는 (백의 자리, 십의 자리, 일의 자리)의 길이 3 목록이다(반복 허용). 백의 자리는 $1$~$9$의 9가지(0이면 세 자리가 아니게 된다), 십$\cdot$일의 자리는 각 $0$~$9$의 10가지이고, 각 자리의 선택지 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 $9 \times 10 \times 10 = 900$개이다. $\blacksquare$ 첫 자리가 특별한 이유: 첫 자리에 0이 오면 자릿수 자체가 무너져 "세 자리 수"라는 세기 대상에서 벗어나기 때문이다 — 규범 ①의 구조 선언이 첫 자리의 선택지를 결정한다. **검산.** 세 자리 수는 100부터 999까지이므로 $999 - 100 + 1 = 900$ ✓. ### 문제 10 **접근.** "짝수"라는 제약은 일의 자리에만 걸린다. 제약이 가장 센 자리부터 정하는 것이 요령이다 — 그래야 각 단계의 선택지 개수가 일정해져 곱셈 원리가 깔끔히 적용된다. 만의 자리부터 정하면 일의 자리의 선택지가 "앞에서 짝수를 써 버렸는가"에 따라 달라져 조건이 깨진다. **풀이.** 만들 수는 1~5를 한 번씩 쓴 반복 없는 길이 5 목록 중 일의 자리가 짝수인 것이다. 일의 자리부터 정한다: 짝수는 2와 4의 2가지. 남은 네 자리는 남은 숫자 4개의 반복 없는 나열로 $4! = 24$가지 — 일의 자리에 무엇을 골랐든 남는 숫자는 4개이므로 개수는 일정하다. 곱셈 원리에 의해 $2 \times 4! = 2 \times 24 = 48$개이다. $\blacksquare$ **검산.** 전체는 $5! = 120$개이고, 일의 자리 후보 다섯 숫자가 대칭이므로 일의 자리가 특정 숫자인 것은 각 $24$개씩 — 짝수 두 숫자 몫은 $24 \times 2 = 48$ ✓. **복기.** 제약이 센 자리 먼저 — 단계의 **순서**를 바꾸는 것은 세는 대상을 바꾸지 않으면서 곱셈 원리의 조건을 살려 내는 설계 기술이다. ### 문제 11 **접근.** $\times$는 목록 생성 기계다 — 성분의 수가 곧 목록의 길이. 두 크기 모두 §1.5의 사실(과 그 반복)로 계산하고, "어떤 목록의 개수인가"를 규범 ①의 문장으로 붙인다. **풀이.** $|A \times B| = |A| \cdot |B| = 3 \times 5 = 15$ — ($A$의 원소, $B$의 원소)인 길이 2 목록의 개수다(§1.5). $|B \times B \times B| = 5 \times 5 \times 5 = 5^3 = 125$ — $B$의 원소로 된 길이 3 반복 허용 목록의 개수다. 세 성분이 모두 같은 집합 $B$이므로 매 자리 5가지 그대로이고(반복 허용 — $(b, b, b)$ 같은 원소도 $B^3$의 정당한 원소다), 곱셈 원리에 의해 $5^3$이다. **복기.** $A \times B$의 크기 계산은 이제 "인정하고 쓰는 사실"이 아니라 근거 ④(이번 주에 증명)다 — 6주차부터 진 빚이 이 문제로 상환 확인된다. ### 문제 12 **접근.** 단계별 선택지를 일반 문자로 센다: 1번째 $n$, 2번째 $n - 1$, …, $k$번째는 이미 쓴 $k-1$개가 빠져 $n - (k-1)$가지(확인 8). 곱을 팩토리얼 분수로 정리할 때는 1을 곱하는 변형 — $\frac{(n-k)!}{(n-k)!}$ — 을 쓴다. **풀이.** $n$개의 기호에서 반복 없이 길이 $k$ 목록을 만든다. 1번째 항목의 선택지는 $n$가지. 2번째는 이미 쓴 1개가 빠져 $n - 1$가지. 일반으로 $i$번째는 이미 쓴 $i - 1$개가 빠져 $n - (i - 1)$가지이고, 앞에서 무엇을 썼든 빠지는 개수는 정확히 $i - 1$이므로 선택지의 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 총수는 $$ n \times (n-1) \times \cdots \times (n - k + 1) $$ 이다. 여기에 $\dfrac{(n-k)!}{(n-k)!} = 1$을 곱하면(근거 ③) 분자가 $n$부터 $1$까지의 곱으로 이어져 $$ n(n-1)\cdots(n-k+1) \times \frac{(n-k)!}{(n-k)!} = \frac{n(n-1)\cdots(n-k+1) \times (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!} $$ 이다. $\blacksquare$ **검산.** $k = n$이면 $\dfrac{n!}{0!} = \dfrac{n!}{1} = n!$ — 전부 세우기와 일치한다. $0! = 1$로 정의한 덕분에 공식이 끝 사례까지 작동한다(§1.7). $n = 7$, $k = 3$이면 $\dfrac{7!}{4!} = 210$ — 예제 2.3(b)와 일치한다 ✓. **복기.** 준비 운동 유형 2의 공식 ${}_n\mathrm{P}_k$가 바로 이 값이다 — 이제 유도를 마쳤으므로 근거 ④로 등록되어, 이름이 아니라 논증으로 쓸 수 있다. ### 문제 13 **접근.** 훈련 3의 뼈대 그대로 — ① 부분집합과 넣음/뺌 목록의 1:1 대응 제작 (두 방향 모두 서술) ② 목록 쪽의 단계별 개수 ③ 곱셈 원리 인용과 결론. 세기 어려운 대상을 세기 쉬운 대상에 실어 나르는 것이 논증의 전부다. **풀이.** $|A| = n$이라 하고 $A$의 원소를 $x_1, \dots, x_n$으로 나열하자. 부분집합 $X \subseteq A$마다 길이 $n$ 목록 $(d_1, \dots, d_n)$을 다음 규칙으로 만든다: $x_i \in X$이면 $d_i = $ 넣음, $x_i \notin X$이면 $d_i = $ 뺌. 거꾸로 넣음/뺌 기호의 길이 $n$ 목록 $(d_1, \dots, d_n)$ 하나마다 부분집합 $X = \{x_i : d_i = \text{넣음}\}$이 정확히 하나 정해지고, 두 규칙은 서로 역이다 — 따라서 부분집합과 목록은 빠짐도 겹침도 없이 1:1로 대응하고, 부분집합의 수는 목록의 수와 같다. 목록의 각 자리는 넣음/뺌의 2가지이고 각 자리의 선택지 개수는 앞 자리와 무관하므로, 곱셈 원리에 의해 목록은 $2^n$개다. 따라서 $|\mathcal{P}(A)| = 2^n$이다. $\blacksquare$ **검산.** $n = 0$: 빈 목록 1개 $\leftrightarrow$ $\emptyset$ 1개 — 4주차의 $\mathcal{P}(\emptyset) = \{\emptyset\}$(크기 1)과 일치하고, $2^0 = 1$ ✓. **복기.** **대응으로 세기** — 세기 어려운 대상을 세기 쉬운 대상에 1:1로 실어 나른다. 이 발상은 문제 16(회문), 문제 18(함수)에서 곧바로 재사용되고, 41주차 (단사$\cdot$전단사)를 거쳐 48주차(대등)에서 무한집합의 크기 비교로까지 자란다. ### 문제 14 **접근.** 두 물음은 §1.6 표의 두 행 — 반복 허용과 반복 금지 — 의 대비다. 재료는 같은 기호 5종(1, 3, 5, 7, 9), 길이도 같은 4이고, 조건 하나만 다르다. 첫 자리 걱정(문제 9)은 필요 없다 — 후보에 0이 아예 없다. **풀이.** 네 자리 수는 (천, 백, 십, 일)의 길이 4 목록이고, 기호는 홀수 숫자 5종이다. 0이 후보에 없으므로 첫 자리도 5가지 전부 가능하다. 전반부(반복 허용): 매 자리 5가지, 각 자리의 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 $5^4 = 625$개이다. 후반부(모두 다름 = 반복 금지): 자리별 선택지는 $5, 4, 3, 2$가지 — $i$번째 자리에서 이미 쓴 $i-1$개가 빠진다. 곱셈 원리에 의해 $5 \times 4 \times 3 \times 2 = 120$개이다. $\blacksquare$ **복기.** 같은 재료에서 조건 하나로 $n^k$와 $n(n-1)\cdots(n-k+1)$이 갈린다 — 문제를 받으면 "앞 선택이 뒤 선택지를 줄이는가"부터 묻는 습관이 두 공식의 선택을 자동화한다. ### 문제 15 **접근.** "적어도 하나의 1"을 정면으로 세면 1이 1개인 경우, 2개인 경우, …로 경우가 다섯 갈래다. 부정 — "1이 하나도 없다" — 은 단 한 갈래다. 전체에서 나쁜 경우를 빼는 여사건 전략(§4 도입 상자)을 쓴다. "적어도 하나"($\exists$)의 부정이 "전부 아님"이라는 11주차 부정 규칙이 세기 전략으로 번역되는 자리다. **풀이.** 전체 — 길이 5의 이진 문자열은 매 자리 0/1의 2가지, 반복 허용이므로 곱셈 원리에 의해 $2^5 = 32$개다(예제 2.2와 같은 세기). 나쁜 경우 — 1이 하나도 없는 문자열은 다섯 자리가 전부 0인 $(0,0,0,0,0)$ 단 1개다. 전체는 "적어도 하나의 1을 포함"과 "1이 하나도 없음"으로 겹침 없이 나뉘므로(지금은 인정하고 쓴다 — 14주차 덧셈 원리), 구하는 개수는 $$ 32 - 1 = 31 $$ 개이다. $\blacksquare$ **검산.** 길이 2로 줄이면 전체 4개 중 $00$ 하나를 뺀 $01, 10, 11$의 3개 — 공식 $2^2 - 1 = 3$ ✓. **복기.** **전체에서 빼기** — "적어도 하나"를 만나면 부정을 먼저 세어 본다. 부정 규칙(11주차)이 계산 전략이 되는 이 전환은 14주차에서 정식 도구가 된다. ### 문제 16 **접근.** 회문의 조건 "앞뒤로 읽어도 같다"를 자리의 언어로 번역한다: 5번째 자리는 1번째와, 4번째 자리는 2번째와 같아야 한다. 그러면 스스로 고를 수 있는 자리는 몇 개인가 — 자유 자리의 목록과 회문이 1:1로 대응한다(문제 13의 대응 발상). **풀이.** 길이 5의 문자열 $(c_1, c_2, c_3, c_4, c_5)$가 회문일 조건은 $c_5 = c_1$이고 $c_4 = c_2$인 것이다($c_3$은 스스로와 같으므로 조건이 없다). 따라서 $c_1, c_2, c_3$을 정하면 $c_4, c_5$는 자동으로 결정되고, 거꾸로 회문 하나마다 그 앞쪽 세 자리가 하나로 정해진다 — 회문과 (1, 2, 3번째 자리)의 길이 3 목록이 1:1로 대응한다. 그 목록은 기호 3종($a, b, c$), 반복 허용이므로 곱셈 원리에 의해 $3^3 = 27$개 — 회문도 27개이다. $\blacksquare$ **검산.** 길이 3의 회문(자유 자리 2개)이면 $3^2 = 9$개 — $aba$, $aca$, $aaa$ 등 직접 나열로 9개가 맞는지 작은 사례에서 확인할 수 있다. **복기.** 제약 조건은 자유 자리의 개수를 줄인다 — "몇 자리가 진짜 선택인가"를 먼저 세는 것이 회문형 문제의 표준 접근이다. ### 문제 17 **접근.** $5 \times 4 = 20$이라는 계산 자체는 오류가 아니다 — 규범 ①로 돌아가 그것이 **무엇을** 세는지 선언해 보면, 세는 대상이 문제의 대상과 어긋나 있음이 드러난다. 목록과 집합의 구분(정의 12.1)이 급소다. **풀이.** $5 \times 4$가 세는 것은 (첫 사람, 둘째 사람)의 반복 없는 길이 2 **목록**의 수다. 그런데 악수 쌍은 $\{A, B\}$라는 **집합**이다 — 누가 먼저 손을 내밀었는지는 악수를 구별하지 않는다. 목록 $(A, B)$와 $(B, A)$는 서로 다르지만 같은 악수 쌍 $\{A, B\}$에 대응하므로, $5 \times 4 = 20$은 모든 쌍을 정확히 **두 번씩** 센 것이다. 각 쌍이 정확히 2번씩 세어졌으므로 실제 쌍의 수는 $20 \div 2 = 10$이다. **검산.** 5명을 1~5로 부르면 쌍은 $\{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,5\}, \{4,5\}$ — 나열해도 10개다 ✓. **복기.** **순서 지우기 나눗셈** — 목록으로 일단 세고, 각 대상이 정확히 $m$번씩 세어졌으면 $m$으로 나눈다. 이 한 수가 다음 주 조합 $\binom{n}{k}$의 탄생 원리다 — 13주차에서 $m = k!$의 일반형으로 다시 만난다. ### 문제 18 **접근.** "각 원소에 하나씩 배정"을 목록으로 번역한다 — $A = \{a_1, a_2, a_3\}$ 이라 하면 배정 결과 하나는 ($a_1$의 값, $a_2$의 값, $a_3$의 값)이라는 길이 3 목록으로 완전히 기록되고, 거꾸로 그런 목록 하나가 배정 하나를 정한다. 대응으로 세기(문제 13)의 재등장이다. **풀이.** $A = \{a_1, a_2, a_3\}$이라 하자. 배정 하나는 ($a_1$에 배정한 값, $a_2$에 배정한 값, $a_3$에 배정한 값)이라는, $B$의 원소로 된 길이 3 목록과 1:1로 대응한다. 서로 다른 원소에 같은 값을 배정해도 되므로 반복 허용이고, 각 자리의 선택지는 $|B| = 4$가지로 앞 선택과 무관하다. 곱셈 원리에 의해 $4 \times 4 \times 4 = 4^3 = 64$가지이다. $\blacksquare$ **복기.** **함수 = 출력 목록** — 입력마다 출력 하나를 정하는 것이 함수이고, 그 전모는 출력들의 목록 하나로 기록된다. 일반으로 $|A| = m$, $|B| = n$이면 함수는 $n^m$개 — 40주차에서 함수의 정의와 함께 이 세기를 회수한다. ### 문제 19 **접근.** 문제 18에서 조건 하나만 바뀌었다 — "서로 다른 원소에 서로 다른 값" 은 출력 목록에 같은 값이 두 번 나올 수 없다는 뜻, 곧 반복 금지다. §1.6 표의 행이 바뀌는 것뿐이다. **풀이.** 배정은 문제 18의 대응 그대로 $B$의 원소로 된 길이 3 목록인데, 이번엔 반복 금지다. 자리별 선택지는 $4, 3, 2$가지 — $i$번째 자리에서 이미 배정한 $i - 1$개의 값이 빠진다 — 이고 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 $4 \times 3 \times 2 = 24$가지이다. $\blacksquare$ **복기.** 일반으로 $|A| = k$, $|B| = n$이면 단사 배정은 반복 없는 길이 $k$ 목록의 수 $\dfrac{n!}{(n-k)!}$가지(문제 12의 공식)다 — 41주차에서 단사함수의 정의와 함께 재회한다. 문제 18(반복 허용)과 이 문제(반복 금지)의 대비가 "함수 대 단사함수"의 세기 버전이다. ### 문제 20 **접근.** 곱셈 원리의 핵심 조건 — 각 단계의 선택지 **개수**가 앞 단계의 결과와 무관 — 을 일부러 부수는 상황을 조작해 만든다. 1단계의 선택에 따라 2단계의 가짓수 자체가 달라지는 조건부 규칙(특정 선택 뒤의 제한이나 특전) 하나면 된다. 격자로 그리면 행마다 칸 수가 다른, 직사각형이 아닌 그림이 나온다. **풀이.** (예시 답안) 식당에서 밥 또는 빵을 고른 뒤 음료를 고르는데, 밥을 고르면 음료 3종 중에서, 빵을 고르면 음료 5종 중에서 고를 수 있다고 하자. 2단계의 선택지 개수(3 대 5)가 1단계의 결과에 의존하므로, 곱셈 원리를 전체에 통째로 적용할 수 없다 — $2 \times 3$도 $2 \times 5$도 답이 아니다. 세는 방법: **1단계의 결과별로 경우를 나눈다.** 밥인 경우는 $1 \times 3 = 3$가지, 빵인 경우는 $1 \times 5 = 5$가지 — 각 경우 안에서는 개수가 일정해 곱셈 원리가 작동한다 — 이고, 두 경우는 겹치지 않고 전체를 덮으므로 합해서 $3 + 5 = 8$가지이다. **복기.** 곱셈 원리는 "**단계**"로 쪼갤 때, 덧셈은 "**경우**"로 쪼갤 때 쓴다. 단계 쪼개기가 무너지는 지점(개수의 의존)이 곧 경우 쪼개기로 전환하는 신호다. 겹침 없이 나눠 더하기의 정당화(덧셈 원리)는 14주차에서, 경우 나누기의 본격 훈련은 17주차에서 한다. --- **다음 주 예고:** 순서를 지우면 무엇이 남는가 — 조합 $\binom{n}{k}$다. 문제 17에서 2로 나눈 "순서 지우기 나눗셈"이 $k!$로 나누는 일반 공식이 되고, 같은 대상을 두 가지 방법으로 세어 등식을 증명하는 **세기 논증**(combinatorial proof)이라는 새 증명 기법을 만난다. 파스칼 삼각형과 이항정리(고2 연계)가 전부 거기서 나온다. 이번 주의 서술 규범 — 무엇을 세는지 먼저 선언한다 — 이 그대로 다음 주의 증명 도구가 된다.