AMC 10 · 2010 · #9

학년 8 number-theory

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

prime-factorizationexponentsperfect-squareslcm convert-to-algebraextreme-principle ↑ 선수 지식: prime-factorization

📏 긴 풀이 💡 2 개 인사이트

문제

어떤 수가 20의 배수이고, 그 제곱은 세제곱수이며, 그 세제곱은 제곱수다. 가장 작은 것의 자릿수를 세어라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 다르게 정리하기

세 조건은 n, n², n³이라는 서로 다른 수를 말하고 있어서 처음에는 따로 노는 것처럼 보인다. n을 소인수분해 꼴로 다시 적으면 세 조건이 모두 지수 하나의 목록에 대한 이야기로 정리된다. 제곱과 세제곱은 그 지수들에 2와 3을 곱할 뿐이기 때문이다. 지수에 문자를 붙이면 '세제곱수이다', '제곱수이다'가 단순한 나누어떨어짐 규칙으로 바뀐다. 그 뒤에는 각 지수를 허용되는 가장 작은 값까지 낮춘 것이 가장 작은 n이고, 작은 후보들을 짧게 나열해 보면 더 작은 수가 빠져나가지 못함을 확인할 수 있다.

1STEP 1

n을 소수의 거듭제곱으로 쪼개기

소인수분해가 수를 지수 목록으로 바꾼다.

n=Π_i=1^k p_i^a_i, n²=Π_i=1^k p_i²a_i, n³=Π_i=1^k p_i³a_i

2STEP 2

세제곱수와 제곱수의 조건

세제곱수와 제곱수는 지수의 나누어떨어짐일 뿐이다.

N=Π p^e_p is a cube⇔ 3 ∣ e_p ∀ p, N=(Π p^e_p/3)³

3STEP 3

두 조건을 지수 규칙으로 바꾸기

각 조건이 하나의 단순한 지수 규칙이 된다.

3 ∣ 2a_i → 3 ∣ a_i, 2 ∣ 3a_i → 2 ∣ a_i

4STEP 4

두 규칙을 합치면 여섯제곱

두 규칙이 합쳐지면 여섯제곱이 된다.

2 ∣ a_i and 3 ∣ a_i ⇔ 6 ∣ a_i ⇔ n=t⁶; n=t⁶→ n²=(t⁴)³, n³=(t⁹)²

5STEP 5

20의 배수 조건 넣기

배수 조건이 십의 인수를 강제한다.

20=2² · 5; 6c ≥ 2, 6d ≥ 1 ⇔ c ≥ 1, d ≥ 1 ⇔ 10 ∣ t

6STEP 6

가장 작은 것 고르기

그런 수 중 가장 작은 것은 십의 여섯제곱이다.

{ n }={ t⁶ : 10 ∣ t }, t_min=10 → n=10⁶

7STEP 7

자릿수 세기

자릿수는 7이다, 보기 (D).

10⁶ = 1 000 000 → 7 digits

정답

n = 1000000을 세 조건에 직접 대조한다. 이 수는 20 곱하기 50000이므로 20으로 나누어떨어진다. 제곱은 10¹2 = (10⁴)³으로 완전세제곱수이다. 세제곱은 10¹8 = (10⁹)²으로 완전제곱수이다. 따라서 조건을 만족하고 자릿수는 7이며 보기 (E)와 맞는다. 최소성은 이론 없이 유한 검사로도 확인된다. 6자리 이하인 수는 1000000보다 작은데, 1000000보다 작은 여섯제곱수는 1, 64, 729, 4096, 15625, 46656, 117649, 262144, 531441뿐이다. 이 중 5로 나누어떨어지는 것은 15625 = 5⁶ 하나이고 이 수는 홀수라 20으로 나누어떨어지지 않는다. 그러므로 6자리 이하인 답은 없고 (A)부터 (D)까지는 모두 배제된다.

💡핵심 정리

제곱과 세제곱은 소인수의 지수를 늘리기만 하므로, 세제곱수와 제곱수를 동시에 요구하면 모든 지수가 6의 배수가 될 수밖에 없다.

n을 소수의 거듭제곱으로 쪼개기
세제곱수와 제곱수의 조건
두 조건을 지수 규칙으로 바꾸기
두 규칙을 합치면 여섯제곱
20의 배수 조건 넣기
가장 작은 것 고르기
자릿수 세기