AMC 10 · 2020 · #22

학년 6 number-theory

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

floor-functiondivisibility-rulesdivisor-countmodular-arithmeticpattern-recognition complementary-countingpattern-recognitioncasework ↑ 선수 지식: floor-functiondivisor-count

📏 긴 풀이 💡 3 개 인사이트

문제

For how many positive integers $n \le 1000$ is $\left\lfloor \dfrac{998}{n} \right\rfloor+\left\lfloor \dfrac{999}{n} \right\rfloor+\left\lfloor \dfrac{1000}{n}\right \rfloor$ not divisible by $3$ ? (Recall that $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$ .)

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 양의 정수 $n \le 1000$ 중에서 합 $S(n) = \lfloor 998/n \rfloor + \lfloor 999/n \rfloor + \lfloor 1000/n \rfloor$ 이 $3$ 의 배수가 아닌 $n$ 의 개수를 구하세요. 여기서 $\lfloor x \rfloor$ 은 $x$ 이하의 가장 큰 정수.

주어진 것: 같은 $n$ 으로 나눈 연속된 세 분자 $998, 999, 1000$; $n$ 은 $1 \le n \le 1000$ 인 양의 정수; $999 = 3^3 \cdot 37$, $1000 = 2^3 \cdot 5^3$ (인수분해 활용); 선택지: (A) $22$, (B) $23$, (C) $24$, (D) $25$, (E) $26$

구하는 것: $S(n)$ 이 $3$ 의 배수가 아닌 $n$ 의 개수

이해

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #5 패턴 찾기, #16 관점 바꾸기, #2 빠짐없이 나열하기, #3 가능성 지우기

도구 #9(더 쉬운 문제): 작은 $n$ ($1, 2, 7, 8, 9, \ldots$) 부터 손으로 계산해 "세 바닥값이 언제 달라지는지" 파악. 도구 #5(패턴): $999$ 나 $1000$ 이 $n$ 의 배수일 때만 바닥값이 "점프" 함 — 깔끔한 조건. 도구 #16(관점 바꾸기): $3$ 의 배수가 아닌 $n$ 을 직접 세지 말고 "세 바닥값이 모두 같지 않은 $n$" 즉 $999$ 또는 $1000$ 의 약수만 세기. 도구 #2(빠짐없이 나열): 약수 목록을 만들어 합집합. 도구 #3(가능성 지우기): 규칙을 만족하지만 실제로는 $3$ 의 배수가 되는 $n=1$ 예외 제거.

실행 — 정답: A

#9 더 쉬운 문제로 줄이기 6.NS.B.2 단계 1

작은 값으로 감잡기.
$n=7$: $\lfloor 998/7 \rfloor = 142, \lfloor 999/7 \rfloor = 142, \lfloor 1000/7 \rfloor = 142$.
합 $= 426 = 3 \cdot 142$, $3$ 의 배수.
$n=8$ ($1000$ 의 약수): $\lfloor 998/8 \rfloor = 124, \lfloor 999/8 \rfloor = 124, \lfloor 1000/8 \rfloor = 125$.
합 $= 373$, $3$ 의 배수 아님.
$n=9$ ($999$ 의 약수): $\lfloor 998/9 \rfloor = 110, \lfloor 999/9 \rfloor = 111, \lfloor 1000/9 \rfloor = 111$.
합 $= 332$, $3$ 의 배수 아님.
패턴: $n$ 이 $999$ 또는 $1000$ 을 "정확히 나눌" 때만 바닥값에 점프 발생.

$$n=7: 142+142+142 = 426\;(\div 3\;\checkmark);\;\; n=8: 124+124+125 = 373\;(\not\div 3);\;\; n=9: 110+111+111 = 332\;(\not\div 3)$$

💡 몇 개 손으로 해보면 — $n$ 이 $999, 1000$ 중 하나에 정확히 떨어질 때만 바닥값이 다르다.

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

일반 규칙.
$999 = nq + r$ ($0 \le r < n$) 로 쓰면 $\lfloor 999/n \rfloor = q$.
$998 = nq + (r-1)$, $1000 = nq + (r+1)$.
$r$ 의 위치로 세 경우.
(i) $1 \le r \le n-2$: 세 나머지 모두 $[0, n-1]$ 안 — 세 바닥값 모두 $q$, 합 $= 3q \equiv 0 \pmod 3$.
(ii) $r=0$ ($n \mid 999$): $998$ 의 나머지 $n-1 \Rightarrow \lfloor 998/n \rfloor = q-1$; $1000$ 의 나머지 $1 \Rightarrow \lfloor 1000/n \rfloor = q$.
합 $= (q-1)+q+q = 3q-1 \equiv 2 \pmod 3$.
(iii) $r=n-1$ ($n \mid 1000$): $998$ 의 나머지 $n-2 \Rightarrow \lfloor 998/n \rfloor = q$; $1000$ 의 나머지 $0 \Rightarrow \lfloor 1000/n \rfloor = q+1$.
합 $= q+q+(q+1) = 3q+1 \equiv 1 \pmod 3$.
결론: $S(n)$ 이 $3$ 배수 아니다 $\iff$ $n \mid 999$ 또는 $n \mid 1000$.

$$S(n) \not\equiv 0 \pmod 3 \iff n \mid 999 \text{ 또는 } n \mid 1000$$

💡 $999 \bmod n$ 의 값에 따라 깔끔히 세 가지 경우로 나뉨.

#3 가능성 지우기 3.OA.B.5 단계 3

예외 점검: $n=1$.
이때 $r=0$ 이자 $r=n-1=0$ — (ii) 와 (iii) 가 동시.
직접 계산: $\lfloor 998 \rfloor + \lfloor 999 \rfloor + \lfloor 1000 \rfloor = 2997 = 3 \cdot 999$, $3$ 의 배수.
따라서 $n=1$ 은 $999, 1000$ 둘 다 나누지만 답에 포함 안 됨.

$$n=1: S(1) = 2997 = 3 \cdot 999 \;\Rightarrow\; 3 \text{ 의 배수}$$

💡 $n=1$ 은 유일한 공통 약수이자 규칙을 빠져나가는 예외.

#2 빠짐없이 나열하기 6.NS.B.4 단계 4

$999, 1000$ 의 약수 개수.
$999 = 27 \cdot 37 = 3^3 \cdot 37^1$.
약수 개수 $= (3+1)(1+1) = 8$.
약수들: $1, 3, 9, 27, 37, 111, 333, 999$.
$1000 = 8 \cdot 125 = 2^3 \cdot 5^3$.
약수 개수 $= (3+1)(3+1) = 16$.
약수들: $1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000$.

$$d(999) = 8, \quad d(1000) = 16$$

💡 소인수분해 지수에 $1$ 씩 더해 곱한 표준 약수 공식.

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

포함-배제.
$999, 1000$ 의 공통 약수는 $\gcd(999, 1000) = 1$ 의 약수, 즉 $\{1\}$ 뿐.
합집합 크기 $= 8 + 16 - 1 = 23$.
예외 $n=1$ 은 합집합에 포함되지만 답에 안 들어가므로 빼면 최종 $23 - 1 = 22$.

$$\text{답} = 8 + 16 - 1 - 1 = 22 \Rightarrow \textbf{(A)}$$

💡 두 약수 목록의 포함-배제, 그리고 깨진 $n=1$ 한 번 더 빼기.

[1] #9 6.NS.B.2 작은 값으로 감잡기. $n=7$: $\lfloor 998/7 \rfloor = 142, \lfloor 999/7 \rfloor = 142, \l

[2] #5 6.NS.B.2 일반 규칙. $999 = nq + r$ ($0 \le r < n$) 로 쓰면 $\lfloor 999/n \rfloor = q$. $998 = n

[3] #3 3.OA.B.5 예외 점검: $n=1$. 이때 $r=0$ 이자 $r=n-1=0$ — (ii) 와 (iii) 가 동시. 직접 계산: $\lfloor 998 \rf

[4] #2 6.NS.B.4 $999, 1000$ 의 약수 개수. $999 = 27 \cdot 37 = 3^3 \cdot 37^1$. 약수 개수 $= (3+1)(1+1) =

[5] #16 6.NS.B.4 포함-배제. $999, 1000$ 의 공통 약수는 $\gcd(999, 1000) = 1$ 의 약수, 즉 $\{1\}$ 뿐. 합집합 크기 $= 8

검토

합리성 확인: 답에 든 모든 $n$ 은 자동으로 $\le 1000$ ($999, 1000$ 의 약수). 점검: $n=8$ ($1000$ 약수, $999$ 약수 아님): 합 $= 373 = 3 \cdot 124 + 1$, 안 나눠짐. $n=37$ ($999$ 약수, $1000$ 약수 아님): $\lfloor 998/37 \rfloor = 26, \lfloor 999/37 \rfloor = 27, \lfloor 1000/37 \rfloor = 27$, 합 $= 80 = 3 \cdot 27 - 1$, 안 나눠짐. $n=2$ ($1000$ 약수): $499 + 499 + 500 = 1498 = 3 \cdot 499 + 1$, 안 나눠짐. 답 $22 = 7 + 15$ ($999$ 약수 중 $1$ 제외 $7$ 개 + $1000$ 약수 중 $1$ 제외 $15$ 개) 와 일치. 선택지 (B) $23$ 은 $n=1$ 잊은 함정.

대안 접근: 도구 #2(빠짐없이 나열) 만으로: $n=2, 3, 4, \ldots$ 마다 세 바닥값을 계산해 직접 표로 만들어 같은 $22$ 개를 찾을 수도 있음. 약수 목록 풀이는 $999$ 번 확인 대신 두 목록만 보면 끝나는 장점.

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

3.OA.B.5 연산 성질을 이용한 곱셈·나눗셈 전략 ($n=1$ 예외 직접 확인: $998 + 999 + 1000 = 2997 = 3 \cdot 999$.)
6.NS.B.2 표준 나눗셈 알고리즘으로 여러 자릿수 나누기 ($998, 999, 1000$ 을 $n$ 으로 나눈 몫과 나머지를 계산해 세 바닥값이 언제 달라지는지 파악.)
6.NS.B.4 두 수의 최대공약수와 최소공배수 구하기 ($999 = 3^3 \cdot 37, 1000 = 2^3 \cdot 5^3$ 인수분해, 지수 공식으로 약수 개수 세기, $\gcd(999, 1000) = 1$ 로 포함-배제.)

⭐ 이 AMC 10 문제는 이미 배운 6학년 약수와 약수 개수만 있으면 풀려요 — 세 바닥값은 $n$ 이 $999$ 또는 $1000$ 을 정확히 나눌 때만 다르고, 그 약수 개수($8 + 16 - 1$ 중복)에서 함정 $n=1$ 을 빼면 $22$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: A

검토

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

비슷한 유형 더 풀어보기