AMC 10 · 2022 · #23

학년 11 number-theory

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

lcmp-adic-valuationmodular-arithmeticp-adic-inverseprime-numbers identify-subproblemscaseworksystematic-enumeration ↑ 선수 지식: lcmmodular-arithmetic

📏 긴 풀이 💡 4 개 인사이트

문제

1부터 n까지의 역수를 모두 더해 기약분수로 만들면 분모가 나옵니다. 따로 1부터 n까지의 최소공배수도 있습니다. 1부터 22까지의 n 중에서 그 분모가 최소공배수보다 엄격히 작은 것이 몇 개인지 세세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 다르게 정리하기

22개의 조화급수 분수를 손으로 일일이 계산하고 약분하는 것은 너무 힘들다. 그래서 정보를 다르게 정리한다. 먼저 합 전체를 하나의 분모 L_n 위에 올려 쓴다. 그러면 k_n ＜ L_n은 분자와 L_n이 소인수를 공유한다는 뜻이 된다. 어려운 분수 문제가 소수 하나씩 따져 볼 수 있는 나누어떨어짐 문제로 바뀐다. 소수 p를 하나 고정하면 분자의 거의 모든 항이 p의 배수라서 p로 나눈 나머지에서 사라지고, 많아야 p-1개의 역원 합만 남는다. 이 짧은 합은 계산하기 쉽고, 그 안의 깔끔한 패턴(M=p-1이면 항상 0) 하나가 대부분의 일을 해 준다. 마지막으로 22 이하의 소수를 빠짐없이 나열해 각 소수가 잡아내는 n을 읽고 합집합을 취한다.

1STEP 1

합을 하나의 분모 위에 올리기

합 전체를 최소공배수 위에 올립니다.

1/1+…+1/n=N_n/L_n, N_n=Σ_j=1ⁿL_n/j, k_n=L_n/gcd(N_n,L_n)

2STEP 2

소수 하나 고정하기

소수 하나와 그 지수를 고정합니다.

p^e ≤ n ＜ p^e+1, v_p(L_n)=e, v_p (L_n/j)=e-v_p(j)

3STEP 3

대부분의 항이 사라짐

대부분의 항이 그 소수로 나눠집니다.

N_n≡Σ_ j ≤ n, v_p(j)=eL_n/j (mod p)

4STEP 4

짧은 역원 합만 남음

남는 것은 짧은 역원의 합입니다.

N_n≡ A S_M (mod p), S_M=Σ_m=1^Mm⁻¹, M=⌊n/p^e⌋ ≤ p-1; p ∣ N_n ⇔ S_M≡ 0 (mod p)

5STEP 5

두 가지 사실 쓰기

두 사실이 대부분의 경우를 결정합니다.

S₁=1≢ 0; S_p-1≡ 1+2+…+(p-1)=(p(p-1))/2≡ 0 (mod p) (p odd)

6STEP 6

소수를 훑어보기

22 이하의 소수를 모두 훑습니다.

p=3: n∈{6,7,8}∪{18,19,20,21,22}; p=5: n∈{20,21,22}; p=2,7,11,13,17,19: none

7STEP 7

합집합 취해 세기

합집합의 크기는 8입니다.

{6,7,8}∪{18,19,20,21,22}∪{20,21,22}={6,7,8,18,19,20,21,22}, | · |=8

정답

손으로 두 번만 확인하면 경계가 분명해진다. n=5일 때 L₅=60이고 N₅=60+30+20+15+12=137은 60과 서로소이므로 k₅=60=L₅이고 5는 제외되는 것이 맞다. n=6일 때 L₆=60이고 N₆=60+30+20+15+12+10=147=3 · 49는 60과 인수 3을 공유하므로 147/60=49/20이 되어 k₆=20 ＜ 60이다. 이는 논증이 예측한 p=3, M=2의 경우와 정확히 일치한다. 이 예 하나로 선택지 (A)도 배제된다. 여덟 개의 n에 대한 비 L_n/k_n은 n=6,7,8에서 3,3,3, n=18,19에서 3,3, n=20에서 15, n=21,22에서 45인데, 모두 3과 5만으로 이루어져 있고 짝수인 경우가 하나도 없다. 이는 소수 훑기 결과와 2가 결코 약분되지 않는다는 증명 양쪽에 모두 들어맞는다.

💡핵심 정리

합 전체를 하나의 분모 위에 올린 다음, 소수를 하나씩 따로 데려와 분자를 나누는지 물어보면 된다. 그러면 거대한 분수가 시계 위의 작은 합 몇 개로 바뀐다.

합 전체를 L_n 위에 올리기
소수 하나와 그 지수를 고정하기
대부분의 항은 p로 나눈 나머지에서 사라진다
살아남은 것은 짧은 역원 합
대부분을 결정하는 두 가지 사실
22 이하의 소수를 훑기
합집합을 취하고 세기