AMC 10 · 2023 · #22

학년 9 number-theory

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

functional-equationprime-factorizationdivisor-sumfactors easier-related-problemsystematic-enumerationidentify-subproblems ↑ 선수 지식: prime-factorizationfactors

📏 긴 풀이 💡 3 개 인사이트

문제

양의 정수에서 정의된 함수가 정확히 하나 있습니다. 모든 양의 정수에서 그 수의 약수마다 약수와 나머지 몫에서의 함숫값을 곱해 모두 더하면 항상 1이 됩니다. 이 함수가 2023에서 갖는 값을 구하세요.

답을 골라 클릭하세요.

(A)

-1536

(B)

(C)

108

(D)

116

(E)

144

풀이 과정

전략 더 쉬운 문제로 줄이기

2023을 대입할 공식이 없으니, 손잡이는 식들의 무리 그 자체뿐이다. 관찰 두 가지가 이 무한한 무리를 유한한 것으로 바꾼다. 첫째, d=1 항만 따로 떼어 내도록 합을 다시 쓰면(다르게 정리하기), n에 대한 식에는 f(n)이 정확히 한 번만 나타나고 나머지는 전부 n의 진약수에서의 값이라는 것이 드러난다. 이 한 번의 재배열이 바로 f가 존재하고 유일한 이유이며, 조건을 이미 아는 값들로부터 f(n)을 계산하는 절차로 바꿔 준다. 둘째, 조건은 모든 n에서 성립하므로 아주 작은 n부터 써먹고(더 쉬운 문제로 줄이기) 위로 올라가면 된다. 도중에 등장하는 수는 2023의 약수뿐이고 2023 = 7 · 17²의 약수는 여섯 개뿐이므로, 이 등반은 여섯 걸음이면 끝난다(작은 문제로 쪼개기). 올라가는 길에 소수의 거듭제곱에 대한 패턴이 보이는데(패턴 찾기), 눈여겨볼 만하지만 꼭 필요하지는 않다. 여섯 걸음만으로 답에 닿고, 오답 선택지 하나를 슬그머니 만들어 내는 곱셈성 지름길을 피할 수 있기 때문이다(가능성 지우기).

1STEP 1

함숫값 항 분리하기

찾는 항을 분리합니다.

Σ_d ∣ n d · f (n/d) = 1 · f(n) + Σ_d ∣ n, d ＞ 1 d · f (n/d) = 1 ⟹ f(n) = 1 - Σ_d ∣ n, d ＞ 1 d · f (n/d)

2STEP 2

약수 모두 적기

약수가 여섯 개뿐입니다.

2023 = 7 · 289 = 7 · 17², 2023의 약수: 1, 7, 17, 119, 289, 2023

3STEP 3

맨 아래에서 출발

가장 작은 값부터 구합니다.

n = 1: 1 · f (1/1) = 1 ⟹ f(1) = 1

4STEP 4

두 소수에서의 값

두 소수에서의 값을 구합니다.

f(7) + 7 f(1) = 1 ⟹ f(7) = 1 - 7 = -6, f(17) + 17 f(1) = 1 ⟹ f(17) = 1 - 17 = -16

5STEP 5

소수의 제곱에서의 값

소수의 제곱에서도 구합니다.

f(289) + 17 f(17) + 289 f(1) = 1 ⟹ f(289) - 272 + 289 = 1 ⟹ f(289) = 1 - 17 = -16

6STEP 6

두 소수의 곱에서의 값

두 소수의 곱에서도 구합니다.

f(119) + 7 f(17) + 17 f(7) + 119 f(1) = 1 ⟹ f(119) - 112 - 102 + 119 = 1 ⟹ f(119) - 95 = 1 ⟹ f(119) = 96

7STEP 7

마지막 값 구하기

마지막 값은 96입니다.

f(2023) + 7 f(289) + 17 f(119) + 119 f(17) + 289 f(7) + 2023 f(1) = 1 ; f(2023) - 112 + 1632 - 1904 - 1734 + 2023 = 1 ; f(2023) - 95 = 1 ⟹ f(2023) = 96

정답

가장 강한 확인은 여섯 값을 원래 조건에 도로 넣어 모든 식이 정말 1이 되는지 보는 것이다. f(1)=1, f(7)=-6, f(17)=-16, f(119)=96, f(289)=-16, f(2023)=96으로 두면, n=7일 때 -6 + 7 = 1, n=17일 때 -16 + 17 = 1, n=289일 때 -16 - 272 + 289 = 1, n=119일 때 96 - 112 - 102 + 119 = 1, n=2023일 때 96 - 112 + 1632 - 1904 - 1734 + 2023 = 1이다. 여섯 개가 모두 성립하므로 값들은 서로 어긋나지 않고 답은 96이다. 오답 선택지도 읽어 볼 값어치가 있다. 선택지 (A)~-1536은 (-6)·(-16)·(-16)인데, 2023 = 7 · 17 · 17을 세 개의 별개 소인수로 보고 f를 전부 곱했을 때, 즉 f(17²) = f(17)²이라고 가정했을 때 나오는 값이다. 5단계에서 f(289)를 직접 계산해 256이 아니라 -16을 얻었으므로 그 가정은 거짓이고 -1536은 지울 수 있다. 부호도 맞는다. 구조 안의 음수 인수 두 개가 짝을 이루므로 96은 양수다.

💡핵심 정리

규칙이 모든 수에서 성립한다면 가장 작은 수부터 넣어 보라. 식 하나가 새 값 하나를 건네주고, 거기서부터 올라가면 된다.

f(n)이 든 항 분리하기
결국 여섯 개의 수뿐
맨 아래 n=1에서 출발
소수 7과 17로 올라가기
소수의 제곱: f(289)
두 소수의 곱: f(119)
n = 2023에서 마무리