AMC 10 · 2024 · #22

학년 8 counting

combinations-basicfactorialprime-factorizationlegendre-formula identify-subproblemsconvert-to-algebrapattern-recognition ↑ 선수 지식: combinations-basicfactorialprime-factorization

📏 긴 풀이 💡 3 개 인사이트

문제

A group of $16$ people will be partitioned into $4$ indistinguishable $4$ -person committees. Each committee will have one chairperson and one secretary. The number of different ways to make these assignments can be written as $3^{r}M$ , where $r$ and $M$ are positive integers and $M$ is not divisible by $3$ . What is $r$ ?

$\textbf{(A) }5 \qquad \textbf{(B) }6 \qquad \textbf{(C) }7 \qquad \textbf{(D) }8 \qquad \textbf{(E) }9 \qquad$

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $16$ 명을 구별되지 않는 $4$ 명짜리 위원회 $4$ 개로 나눈 뒤, 각 위원회에서 의장 한 명과 서기 한 명을 고릅니다. 이렇게 만들 수 있는 총 배정의 수를 $N$ 이라 할 때 $N = 3^{r} M$ ($M$ 은 $3$ 으로 나누어지지 않음) 꼴로 쓸 수 있습니다. $r$ 을 구하세요.

주어진 것: $16$ 명, $4$ 명짜리 위원회 $4$ 개; 위원회는 서로 구별되지 않음 (순서 없는 그룹); 각 위원회는 $4$ 명 중 의장 $1$ 명과 서기 $1$ 명을 선출; $N = 3^{r} M$, $r, M$ 은 양의 정수, $3 \nmid M$; 선택지: (A) $5$, (B) $6$, (C) $7$, (D) $8$, (E) $9$

구하는 것: 지수 $r$ — $N$ 을 나누는 $3$ 의 최대 거듭제곱

이해

계획

주요 도구: #7 작은 문제로 쪼개기

보조 도구: #13 대수로 바꾸기, #5 패턴 찾기, #8 단위 살펴보기

우리에게 필요한 건 $N$ 의 값이 아니라 $N$ 안에 든 $3$ 의 개수뿐입니다. 도구 #7(작은 문제로 쪼개기)이 $N$ 을 깔끔한 곱으로 분해합니다 — (i) 분할 수 $16!/(4!)^5$, (ii) 위원회 한 개당 역할 배정 $12^4$. 도구 #13(대수로 바꾸기)으로 $N = 16! \cdot 12^4 / (4!)^5$ 식을 얻습니다. 도구 #5(패턴 찾기)는 "$n!$ 안의 소수 $p$ 의 지수 = $p, 2p, 3p, \dots$ 가 주는 $p$ + $p^2, 2p^2, \dots$ 가 주는 여분" 이라는 르장드르 패턴을 적용합니다. 도구 #8(단위 살펴보기)은 소수 $3$ 을 "세는 단위" 로 두고 곱과 나눗셈을 따라가는 회계 기법으로 어려운 셈을 한 장의 $v_3$ 계산표로 압축합니다.

실행 — 정답: A

#7 작은 문제로 쪼개기 7.SP.C.8 단계 1

$N$ 을 깔끔한 작은 문제로 분해합니다.
(a) $16$ 명을 순서 있는 $4$ 명짜리 네 그룹으로: $\binom{16}{4}\binom{12}{4}\binom{8}{4}\binom{4}{4} = \dfrac{16!}{(4!)^4}$.
(b) 위원회가 구별되지 않으므로 $4!$ 로 나누어 순서를 지움: $\dfrac{16!}{(4!)^5}$.
(c) 각 위원회에서 의장·서기: $4 \times 3 = 12$ 가지, 네 위원회 모두는 $12^4$.
곱합니다.

$$N = \dfrac{16!}{(4!)^5} \cdot 12^4 = \dfrac{16! \cdot 12^4}{(4!)^5}$$

💡 7학년 곱셈 원리: 독립된 단계마다 곱하고, 구별되지 않는 위원회 한 번에 $4!$ 만큼 나누면 끝.

#13 대수로 바꾸기 8.EE.A.1 단계 2

필요한 건 $N$ 안의 $3$ 의 지수뿐입니다.
$v_3(x)$ 를 $x$ 의 소인수분해에서 $3$ 의 지수라 두면, 곱은 더해지고 나눗셈은 빼지므로 $v_3(N) = v_3(16!) + v_3(12^4) - v_3((4!)^5)$.

$$r = v_3(N) = v_3(16!) + v_3(12^4) - v_3((4!)^5)$$

💡 8학년 정수 지수 규칙: $v_3$ 은 단순히 "개수 세기" 이고, 지수 규칙이 곱을 덧셈으로, 나눗셈을 뺄셈으로 바꿉니다.

#5 패턴 찾기 6.NS.B.4 단계 3

$v_3(16!)$ 을 르장드르 패턴으로 셉니다.
$\{1, 2, \dots, 16\}$ 안의 $3$ 의 배수는 $3, 6, 9, 12, 15$ — 다섯 개, 각각 $3$ 한 개씩 기여.
$9$ 의 배수는 $9$ 하나 — 추가로 $3$ 한 개.
$27$ 의 배수는 없음.
합 $5 + 1 = 6$.

$$v_3(16!) = \lfloor 16/3 \rfloor + \lfloor 16/9 \rfloor + \lfloor 16/27 \rfloor + \dots = 5 + 1 + 0 = 6$$

💡 6학년 배수·인수: $3$ 의 배수, $9$ 의 배수 순서로 한 층씩 올라가며 $3$ 하나씩 더 셉니다.

#13 대수로 바꾸기 8.EE.A.1 단계 4

$v_3(12^4)$.
$12 = 4 \cdot 3 = 2^2 \cdot 3$ 이므로 $v_3(12) = 1$.
$4$ 제곱하면 지수가 $4$ 배: $v_3(12^4) = 4 \cdot 1 = 4$.

$$12 = 2^2 \cdot 3 \;\Rightarrow\; v_3(12^4) = 4 \cdot v_3(12) = 4$$

💡 8학년 지수 법칙 $(ab)^n = a^n b^n$ — 밑에 $3$ 이 하나면 $n$ 제곱에서 $n$ 개.

#13 대수로 바꾸기 8.EE.A.1 단계 5

$v_3((4!)^5)$.
$4! = 24 = 2^3 \cdot 3$ 이므로 $v_3(4!) = 1$.
$5$ 제곱: $v_3((4!)^5) = 5 \cdot 1 = 5$.

$$4! = 24 = 2^3 \cdot 3 \;\Rightarrow\; v_3((4!)^5) = 5 \cdot v_3(4!) = 5$$

💡 8학년 같은 지수 법칙을 분모에 적용.

#8 단위 살펴보기 8.EE.A.1 단계 6

세 조각을 결합합니다.

$$r = v_3(N) = 6 + 4 - 5 = 5 \;\Rightarrow\; \textbf{(A)}$$

💡 8학년 정수 지수 회계로 마무리 — 단위 추적과 똑같은 발상, 소수 $3$ 만 세었을 뿐.

[1] #7 7.SP.C.8 $N$ 을 깔끔한 작은 문제로 분해합니다. (a) $16$ 명을 순서 있는 $4$ 명짜리 네 그룹으로: $\binom{16}{4}\binom{1

[2] #13 8.EE.A.1 필요한 건 $N$ 안의 $3$ 의 지수뿐입니다. $v_3(x)$ 를 $x$ 의 소인수분해에서 $3$ 의 지수라 두면, 곱은 더해지고 나눗셈은 빼

[3] #5 6.NS.B.4 $v_3(16!)$ 을 르장드르 패턴으로 셉니다. $\{1, 2, \dots, 16\}$ 안의 $3$ 의 배수는 $3, 6, 9, 12, 15$

[4] #13 8.EE.A.1 $v_3(12^4)$. $12 = 4 \cdot 3 = 2^2 \cdot 3$ 이므로 $v_3(12) = 1$. $4$ 제곱하면 지수가 $4$

[5] #13 8.EE.A.1 $v_3((4!)^5)$. $4! = 24 = 2^3 \cdot 3$ 이므로 $v_3(4!) = 1$. $5$ 제곱: $v_3((4!)^5) =

[6] #8 8.EE.A.1 세 조각을 결합합니다.

검토

합리성 확인: 크기를 한 번 더 확인합니다. 분자 $16!$ 만으로 $3$ 이 여섯 개($3, 6, 9, 12, 15$ 에서 다섯 개 + $9 = 3^2$ 에서 하나 더), 역할 인자 $12^4$ 가 네 개 더해 분자 합 열 개. 분모 $(4!)^5$ 가 다섯 개를 회수해 남는 건 $10 - 5 = 5$. 분해된 모든 셈이 작은 정수(최대 $6$)라 답이 다섯 거듭제곱 정도임은 자연스럽고, 선택지 $5, 6, 7, 8, 9$ 도 그 근방에 몰려 있습니다. 흔한 실수는 "위원회 구별 안 됨" 의 $4!$ 나눗셈을 잊는 것 — 그러면 $v_3(4!) = 1$ 만큼 빠져 답이 $6$ 으로 한 칸 밀려나는데, 그게 바로 함정 (B).

대안 접근: 도구 #15(다르게 정리하기): $N = \dfrac{16!}{(4!)^5} \cdot 12^4 = \dfrac{16! \cdot (2^2 \cdot 3)^4}{(2^3 \cdot 3)^5} = \dfrac{16! \cdot 2^8 \cdot 3^4}{2^{15} \cdot 3^5} = \dfrac{16!}{2^7 \cdot 3}$. 그러면 $r = v_3(N) = v_3(16!) - 1 = 6 - 1 = 5$. 한 줄에 답이 보입니다.

사용된 CCSS 표준 (최저 학년 8)

7.SP.C.8 정리된 목록·표·나무그림 등으로 복합 사건의 확률을 구하고, 곱셈 원리로 경우의 수 세기 ($N$ 을 독립 단계의 곱으로 셈: 순서 있는 그룹으로 나누기 × $4!$ 나누기(구별 안 됨) × 위원회당 $12$ 가지 역할 배정.)
6.NS.B.4 100 이하 두 수의 최대공약수와 12 이하 두 수의 최소공배수 구하기 — 소인수 개수 세기로 확장 ($\{1, \dots, 16\}$ 안의 $3$ 의 배수, $9$ 의 배수를 차례로 세어 $v_3(16!) = 5 + 1 = 6$ (르장드르 패턴).)
8.EE.A.1 정수 지수의 성질을 알고 적용해 동치 수치 표현 만들기 ($v_3(a \cdot b) = v_3(a) + v_3(b)$, $v_3(a^n) = n \cdot v_3(a)$ 로 $v_3(16!) + v_3(12^4) - v_3((4!)^5) = 6 + 4 - 5 = 5$ 결합.)

⭐ 거대한 셈 문제가 "$3$ 이 몇 개 들어 있나?" 를 물으면 답을 계산하지 말고 조각마다 $3$ 만 세세요. $16!$ 에서 다섯, $12^4$ 에서 네 개 더, 그러나 $(4!)^5$ 가 다섯 개를 빼앗아 남는 건 $r = 5$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: A

검토

사용된 CCSS 표준 (최저 학년 8)

비슷한 유형 더 풀어보기