AMC 10 · 2005 · #22

학년 7 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint

factorialprime-numberstriangular-numbersdivisibility-rules complementary-countingpattern-recognition ↑ 선수 지식: factorialprime-numberstriangular-numbers

📏 긴 풀이 💡 3 개 인사이트

문제

$24$ 이하의 양의 정수 $n$ 중에서 $n!$ 이 $1 + 2 + \cdots + n$ 으로 나누어떨어지는 것은 몇 개입니까?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 10 2005 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $1 \le n \le 24$ 인 양의 정수 $n$ 중에서 $n!$ 이 합 $1 + 2 + \cdots + n$ 으로 나누어떨어지는 것이 몇 개인지 세세요.

주어진 것: $n$ 은 $1$ 부터 $24$ 까지의 양의 정수; 나누는 수는 누적합 $1 + 2 + \cdots + n$; 나누어지는 수는 $n! = 1 \cdot 2 \cdot 3 \cdots n$; 선택지: (A) $8$, (B) $12$, (C) $16$, (D) $17$, (E) $21$

구하는 것: $24$ 개의 $n$ 값 중에서 $n!$ 이 $1 + 2 + \cdots + n$ 으로 나누어떨어지는 것의 개수

이해

문제 재정리: $1 \le n \le 24$ 인 양의 정수 $n$ 중에서 $n!$ 이 합 $1 + 2 + \cdots + n$ 으로 나누어떨어지는 것이 몇 개인지 세세요.

계획

주요 도구: #16 관점 바꾸기

보조 도구: #4 변수 도입하기, #5 패턴 찾기

$24$ 개 값을 하나씩 확인하는 것은 느리므로, 먼저 도구 #4(변수 도입하기)로 합을 공식 $\frac{n(n+1)}{2}$ 로 바꾸고 몫을 하나의 깔끔한 분수로 정리합니다 — 그러면 $n!$ 에 대한 나눗셈 문제가 단 하나의 인수 $n+1$ 에 대한 질문으로 바뀝니다. 이어서 도구 #5(패턴 찾기)로 어떤 $n+1$ 이 나눗셈을 깨뜨리는지 시험하면 패턴이 뚜렷합니다: $n+1$ 이 홀수 소수일 때만 실패하고 나머지는 모두 성공합니다. 실패가 드문 경우이므로, 도구 #16(관점 바꾸기 — 여집합 세기)이 효율적인 마무리입니다 — 성공하는 많은 경우를 뒤지는 대신, 실패하는 홀수 소수를 세어 $24$ 에서 빼면 됩니다.

실행 — 정답: C

#4 변수 도입하기 6.EE.A.2 단계 1

합을 공식으로 바꾸기

나누는 수 $1 + 2 + \cdots + n$ 은 등차수열의 합이고, 이는 $\dfrac{n(n+1)}{2}$ 와 같습니다.
그래서 문제는 $\dfrac{n!}{\,n(n+1)/2\,}$ 이 정수가 되는 때를 묻는 것이 됩니다.
합을 $n$ 에 대한 하나의 식으로 쓰면 $24$ 번의 나눗셈을 힘겹게 하는 대신 약분할 수 있습니다.

$$1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$$

💡 $1$ 부터 $n$ 까지의 누적합은 닫힌 형태가 있으니, 긴 덧셈을 하나의 깔끔한 식으로 바꿉니다.

#4 변수 도입하기 6.EE.A.3 단계 2

몫 간단히 하기

$n!$ 을 $\dfrac{n(n+1)}{2}$ 로 나눕니다: 분수로 나누는 것은 뒤집어 곱하는 것이므로 $\dfrac{2 \cdot n!}{n(n+1)}$ 이 됩니다.
$n! = n \cdot (n-1)!$ 이므로 $n$ 이 약분되어 $\dfrac{2\,(n-1)!}{\,n+1\,}$ 이 남습니다.
따라서 $n!$ 이 합으로 나누어떨어지는 것은 정확히 $n+1$ 이 $2\,(n-1)!$ 을 나눌 때입니다.
이제 문제 전체가 단 하나의 수 $n+1$ 에 달려 있습니다.

$$\dfrac{n!}{n(n+1)/2} = \dfrac{2\,n!}{n(n+1)} = \dfrac{2\,(n-1)!}{n+1}$$

💡 공통 인수 $n$ 을 약분하여 오직 $n+1$ 만 신경 쓰도록 만듭니다.

#5 패턴 찾기 7.NS.A.2 단계 3

실패하는 때 알아보기: n+1 이 홀수 소수

$n+1$ 이 홀수 소수 $p$ 라고 합시다.
그러면 $p$ 는 $2$ 와 공통 인수가 없고, $(n-1)! = 1 \cdot 2 \cdots (p-2)$ 안의 모든 수는 $p$ 보다 작으므로 소수 $p$ 는 그 곱도 나눌 수 없습니다.
$p$ 가 $2$ 도 $(n-1)!$ 도 나누지 못하므로 $2\,(n-1)!$ 도 나눌 수 없고, 따라서 몫은 정수가 아닙니다.
작은 경우로 확인하면 패턴이 맞습니다: $n+1 = 3, 5, 7$ (즉 $n = 2, 4, 6$) 은 모두 실패합니다.

$$p \text{ 소수, } p > 2 \ \Rightarrow\ p \nmid 2 \text{ 이고 } p \nmid (p-2)! \ \Rightarrow\ p \nmid 2\,(n-1)!$$

💡 소수는 자기 자신과 같은 인수에서만 나올 수 있는데, 그보다 작은 인수는 모두 너무 작습니다.

#5 패턴 찾기 7.NS.A.2 단계 4

성공하는 때 알아보기: 나머지 전부

$n+1$ 이 합성수이고 $6$ 이상이면, 서로 다른 두 인수 $a \ne b$ 로 쪼개지며 둘 다 $n-1$ 이하이므로 이미 $(n-1)!$ 안에 들어 있고 그 곱 $n+1$ 이 이를 나눕니다.
$9$ 나 $25$ 같은 소수의 제곱도 성공합니다 — 그 소수의 서로 다른 두 배수(예: $9$ 의 경우 $3$ 과 $6$)가 $n-1$ 아래에 있기 때문입니다.
작은 나머지 경우도 처리됩니다: $n+1 = 4$ 는 $2\,(n-1)! = 2 \cdot 2! = 4$ 이므로 성공하고, $n+1 = 2$ (즉 $n = 1$) 는 $2 \mid 2 \cdot 0!$ 이므로 성공합니다.
그래서 홀수 소수가 아닌 모든 $n+1$ 에 대해 몫은 정수입니다.

$$n+1 = ab,\ 1 < a < b \le n-1 \ \Rightarrow\ (n+1) \mid (n-1)! \mid 2\,(n-1)!$$

💡 합성수의 인수들은 이미 팩토리얼 안에서 기다리고 있으므로 그 수는 나누어 들어갑니다.

#16 관점 바꾸기 4.OA.B.4 단계 5

여집합 세기

홀수 소수인 $n+1$ 값만 실패하므로, 그것들을 세어 $24$ 에서 뺍니다.
$n$ 이 $1$ 부터 $24$ 까지 갈 때 $n+1$ 은 $2$ 부터 $25$ 까지 갑니다.
그 범위의 홀수 소수는 $3, 5, 7, 11, 13, 17, 19, 23$ — 정확히 $8$ 개입니다.
나머지 모든 $n$ 은 성공하므로 성공하는 개수는 $24 - 8 = 16$ 입니다.
답은 (C)입니다.

$$24 - \#\{3,5,7,11,13,17,19,23\} = 24 - 8 = 16 \ \Rightarrow\ \textbf{(C)}$$

💡 실패는 드문 홀수 소수뿐이므로, 그것들을 세어 빼는 것이 모든 성공을 나열하는 것보다 낫습니다.

[1] #4 6.EE.A.2 나누는 수 $1 + 2 + \cdots + n$ 은 등차수열의 합이고, 이는 $\dfrac{n(n+1)}{2}$ 와 같습니다. 그래서 문제는 $

[2] #4 6.EE.A.3 $n!$ 을 $\dfrac{n(n+1)}{2}$ 로 나눕니다: 분수로 나누는 것은 뒤집어 곱하는 것이므로 $\dfrac{2 \cdot n!}{n

[3] #5 7.NS.A.2 $n+1$ 이 홀수 소수 $p$ 라고 합시다. 그러면 $p$ 는 $2$ 와 공통 인수가 없고, $(n-1)! = 1 \cdot 2 \cdots

[4] #5 7.NS.A.2 $n+1$ 이 합성수이고 $6$ 이상이면, 서로 다른 두 인수 $a \ne b$ 로 쪼개지며 둘 다 $n-1$ 이하이므로 이미 $(n-1)!$

[5] #16 4.OA.B.4 홀수 소수인 $n+1$ 값만 실패하므로, 그것들을 세어 $24$ 에서 뺍니다. $n$ 이 $1$ 부터 $24$ 까지 갈 때 $n+1$ 은 $2$

검토

합리성 확인: 실패하는 여덟 개의 $n$ 값은 $2, 4, 6, 10, 12, 16, 18, 22$ — 바로 $n+1$ 이 홀수 소수인 $n$ — 이고, 그중 아무거나 손으로 확인해도 맞습니다: $n = 4$ 이면 합은 $10$ 이지만 $4! = 24$ 는 $10$ 의 배수가 아닙니다. 성공하는 경우에는 $n = 3$ (합 $6$, 그리고 $3! = 6$)과 $n = 5$ (합 $15$, 그리고 $5! = 120 = 15 \cdot 8$) 같은 쉬운 확인이 포함됩니다. 실패가 예외적이므로 답이 범위의 위쪽에 오리라 예상되며, $24$ 중 $16$ 이 이에 맞습니다. 훨씬 작은 선택지 $8$ 과 $12$ 는 몇 안 되는 홀수 소수가 허용하는 것보다 훨씬 많은 실패를 필요로 합니다.

대안 접근: 일반적 논증을 건너뛰고 $n = 1$ 부터 $24$ 까지 표를 만듭니다: 합 $\frac{n(n+1)}{2}$ 를 계산하고 $n!$ 이 그 배수인지 확인합니다. 정수 몫이 나오는 것은 $n = 1, 3, 5, 7, 8, 9, 11, 13, 14, 15, 17, 19, 20, 21, 23, 24$ — 열여섯 개 — 로 (C)와 일치합니다. 표에서 패턴도 드러납니다: 실패는 정확히 $n = 2, 4, 6, 10, 12, 16, 18, 22$, 즉 각 홀수 소수보다 하나 작은 곳에 놓입니다.

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

6.EE.A.2 문자가 수를 나타내는 식을 쓰고, 읽고, 계산한다 (누적합 $1 + 2 + \cdots + n$ 을 하나의 식 $\frac{n(n+1)}{2}$ 로 다시 쓰는 데 사용.)
6.EE.A.3 연산의 성질을 적용하여 동치인 식을 만든다 (공통 인수 $n$ 을 약분하여 몫 $\frac{n!}{n(n+1)/2}$ 를 동치인 형태 $\frac{2\,(n-1)!}{n+1}$ 로 간단히 하는 데 사용.)
7.NS.A.2 유리수의 곱셈과 나눗셈에 대한 이해를 적용하고 확장한다 ($n+1$ 이 곱 $2\,(n-1)!$ 을 나누는지 판단하는 데 사용 — 소수는 나눌 수 없지만 합성수의 인수는 이미 팩토리얼 안에 있음.)
4.OA.B.4 모든 인수쌍을 찾고 배수를 인식하며 소수인지 합성수인지 판별한다 (각 $n+1$ 을 소수 또는 합성수로 분류하고 $2$ 와 $25$ 사이의 홀수 소수를 세어 $24 - 8 = 16$ 에 이르는 데 사용.)

⭐ $1 + 2 + \cdots + n$ 을 $\frac{n(n+1)}{2}$ 로 바꿔 간단히 하면, 나눗셈은 $n+1$ 이 홀수 소수일 때만 실패합니다 — 그러니 그 $8$ 개의 소수를 세어 $24$ 에서 빼면 $16$ 입니다.