AMC 10 · 2023 · #23

학년 11 number-theorycounting

유형 Casework by Position / Vertex Type └ 세부 유형 Count of Type

prime-factorizationdivisor-counttriangular-numberssystematic-enumeration identify-subproblemsconvert-to-algebrasystematic-enumeration ↑ 선수 지식: prime-factorizationdivisor-count

📏 긴 풀이 💡 5 개 인사이트

문제

보통 육면체 주사위 여러 개를 한 번에 굴려 나온 눈을 모두 곱합니다. 서로 다른 굴림이 같은 곱을 낼 수 있으므로 중요한 것은 굴림 수가 아니라 곱이 가질 수 있는 서로 다른 값의 개수입니다. 그 개수가 정확히 936입니다. 주사위 개수를 구하세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 다르게 정리하기

곱을 하나하나 적어 나가는 방법은 가망이 없다. 곱들이 지저분하게 겹치는 데다 개수도 수백 개나 되기 때문이다. 빠져나갈 길은 곱을 수 하나로 저장하지 말고 세 개의 개수로 저장하는 것이다. 주사위 눈은 모두 소수 2, 3, 5만으로 이루어져 있으므로 어떤 곱이든 2^a 3^b 5^c 꼴이고, 소인수분해가 유일하므로 세 쌍 (a,b,c)가 곱을 대신할 수 있다. 여기서 함정을 조심해야 한다. 도달 가능한 세 쌍은 지수들이 이루는 직육면체 전체가 아니다. 주사위 하나는 한 가지 일밖에 못 하므로, 5에 쓴 주사위는 2의 지수를 올리는 데 쓸 수 없기 때문이다. 해결책은 세는 순서를 제대로 잡는 것이다. b와 c는 말 그대로 주사위의 머릿수이므로 이 둘을 먼저 고정하면, 남은 주사위들이 a를 빈틈없는 구간 위로 쓸고 지나가고 그 구간의 길이는 바로 적을 수 있다. 그 길이들을 모두 더하면 n에 대한 삼차식이 나오고, 인수분해 한 번으로 끝난다.

1STEP 1

곱을 세 지수로 저장

곱을 세 지수로 저장합니다.

1 = 2⁰ 3⁰ 5⁰, 2 = 2¹, 3 = 3¹, 4 = 2², 5 = 5¹, 6 = 2¹ · 3¹ → 곱 = 2^a 3^b 5^c

2STEP 2

뻔한 계산이 틀리는 이유

단순 곱셈은 중복을 세어 버립니다.

n = 1: (2 · 1 + 1)(1+1)² = 12 ≠ 6

3STEP 3

두 지수는 바로 읽기

두 지수는 굴림에서 바로 읽힙니다.

c = (5가 나온 주사위 수), b = (3 또는 6이 나온 주사위 수), b + c ≤ n, k = n - b - c

4STEP 4

남은 지수가 훑는 구간

남은 지수가 빈틈없는 구간을 훑습니다.

a_max = b + 2k = b + 2(n - b - c) = 2n - b - 2c, (a의 값의 개수) = 2n + 1 - b - 2c

5STEP 5

모든 경우의 구간 더하기

모든 경우의 구간 길이를 더합니다.

N(n) = Σ_b=0ⁿ Σ_c=0ⁿ-b (2n + 1 - b - 2c) = Σ_b=0ⁿ (n - b + 1)(n + 1) = (n+1) · (n+1)(n+2)/2 = (n+1)² (n+2)/2

6STEP 6

식을 목표와 같게 놓기

식을 936과 같다고 놓습니다.

(n+1)² (n+2)/2 = 936 → (n+1)² (n+2) = 1872

7STEP 7

인수분해해 답 읽기

인수분해하면 11입니다.

1872 = 2⁴ · 3² · 13 = 12² · 13 = (n+1)² (n+2) → n + 1 = 12, n + 2 = 13, n = 11

정답

손으로 확인할 수 있을 만큼 작은 경우로 식을 시험해 볼 수 있다. n = 1이면 식은 (2² · 3)/2 = 6을 주는데, 실제로 주사위 하나는 1부터 6까지 서로 다른 곱 여섯 가지를 준다. n = 2이면 식은 (3² · 4)/2 = 18을 준다. 주사위 두 개가 만드는 순서 없는 쌍은 C(7, 2) = 21가지이고 겹치는 경우는 1 · 4 = 2 · 2, 1 · 6 = 2 · 3, 2 · 6 = 3 · 4 정확히 세 번뿐이므로 21 - 3 = 18이 맞는다. 주어진 선택지마다 식을 돌려 보면 n = 6 → 196, n = 8 → 405, n = 9 → 550, n = 10 → 726, n = 11 → 936이다. 목표에 닿는 것은 n = 11뿐이고, N(n)이 순증가하므로 다른 n은 있을 수 없다. 크기 어림도 들어맞는다. N(n)은 대략 n³/2처럼 자라므로 n³ ≈ 1872에서 n ≈ 12.3인데, 실제 식이 n 대신 n+1과 n+2를 쓰는 만큼 이 어림값은 조금 크게 나오는 것이 당연하고 정답 11로 내려온다. 마지막으로 n = 11일 때 뻔한 직육면체 계산은 23 · 12 · 12 = 3312였을 텐데 이는 936의 세 배가 넘으므로, 도달 가능한 세 쌍이 직육면체의 일부에 지나지 않는다는 점이 다시 확인된다.

💡핵심 정리

주사위의 곱은 결국 2와 3과 5를 몇 개씩 품고 있는지를 적은 주소 (a,b,c)일 뿐이고, 세어야 할 것은 주사위가 실제로 닿을 수 있는 주소의 개수이지 직육면체 안에 들어가기만 하는 주소의 개수가 아니다.

곱을 지수 세 개로 저장하기
뻔한 계산이 왜 틀리는지 확인하기
b와 c는 굴림에서 바로 읽기
2의 지수는 빈틈없는 구간을 훑는다
모든 경우의 구간 길이를 더하기
식을 936과 같다고 놓기
1872를 인수분해해 n을 읽어 내기