AMC 10 · 2021 · #8

학년 6 number-theory
유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint
lcmprime-factorizationexponentsdivisibility-rules identify-subproblemssystematic-enumeration ↑ 선수 지식: lcmprime-factorization
📏 중간 풀이 💡 2 개 인사이트
문제
10부터 30까지의 모든 정수로 나누어떨어지는 가장 작은 수를 첫 값이라 합니다. 그리고 그 첫 값과 32부터 40까지의 각 수로 모두 나누어떨어지는 가장 작은 수를 둘째 값이라 합니다. 둘째 값을 첫 값으로 나눈 값을 구하세요.

답을 골라 클릭하세요.

(A)
1
(B)
2
(C)
37
(D)
74
(E)
2886
풀이 과정
전략 다르게 정리하기

숫자 그대로 쓰면 M과 N은 어마어마하게 크다. 하지만 최소공배수에는 훨씬 다루기 쉬운 두 번째 표현이 있다 — 소수별 지수의 목록이다. 두 수를 그 방식으로 다시 적으면(다르게 정리하기) 문제 전체가 지수 비교로 바뀐다. 이 교체 덕분에 더 쉬운 문제로 줄일 수 있다: N과 M을 구해 나누는 대신, 지수 목록이 바뀌는 자리만 찾으면 된다. 그다음 그 탐색을 32부터 40까지 아홉 개의 작은 확인으로 쪼갠다(작은 문제로 쪼개기). 가능성 지우기는 다섯 개의 보기를 상대로 한 독립적인 검산 수단으로 남겨 둔다.

1STEP 1

최소공배수를 지수 목록으로 읽기

최소공배수를 지수 목록으로 읽습니다.

lcm(a₁, a₂, …, a_k) = Π_p prime p^ max_i v_p(a_i)
2STEP 2

10부터 30까지에서 가장 높은 소수 탑 찾기

첫 범위에서 가장 높은 탑을 찾습니다.

M = 2⁴ · 3³ · 5² · 7 · 11 · 13 · 17 · 19 · 23 · 29
3STEP 3

나누는 대신 지수를 비교하기

나누는 대신 지수를 비교합니다.

N/M = Π_p prime p^ v_p(N) - v_p(M)
4STEP 4

32부터 40까지 하나씩 확인하기

새 수 대부분이 이미 포함돼 있습니다.

32 = 2⁵, 33 = 3 · 11, 34 = 2 · 17, 35 = 5 · 7, 36 = 2² · 3², 37, 38 = 2 · 19, 39 = 3 · 13, 40 = 2³ · 5
5STEP 5

두 변화를 곱하기

두 변화를 곱하면 74입니다.

N/M = 2⁵⁻⁴ · 37¹⁻⁰ = 2 · 37 = 74
정답
74
74M이 정말로 32부터 40까지의 공배수인지 확인한다. 74M = 2 · 37 · M = 2⁵ · 3³ · 5² · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 37이므로 32에 필요한 2⁵, 36에 필요한 2² · 3², 40에 필요한 2³ · 5, 그리고 37 자신까지 모든 조건을 갖추고 있다. 또한 이보다 작아질 수도 없다: 37은 소수이고 N은 나누지만 M은 나누지 않으므로 37은 반드시 N/M을 나눈다. 그리고 2⁵는 N을 나누지만 M은 2⁴까지만 가지므로 2 하나가 반드시 남는다. 따라서 N/M은 최소 2 · 37 = 74이고, 실제로 정확히 74이다. 문제가 31을 슬쩍 건너뛴 점도 눈여겨볼 만하다 — 만약 31이 목록에 있었다면 비에 소인수가 하나 더 붙었을 것이다.
💡핵심 정리

최소공배수는 사실 가장 큰 소수 거듭제곱들의 목록일 뿐이므로, 두 최소공배수를 비교하는 일은 거대한 수를 곱해 보는 게 아니라 지수를 비교하는 일이다.

  • 최소공배수를 지수 목록으로 읽기
  • 10부터 30까지에서 가장 높은 소수 탑 찾기
  • 나누는 대신 지수를 비교하기
  • 32부터 40까지 하나씩 확인하기
  • 두 변화를 곱하기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.