AMC 10 · 2013 · #20

학년 6 number-theory

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

prime-factorizationfactorialprime-numbers extremal-constructionidentify-subproblems ↑ 선수 지식: prime-factorizationfactorial

📏 중간 풀이 💡 3 개 인사이트

문제

$2013$ 을 다음 형태로 나타낸다.

$2013 = \frac {a_1!a_2!...a_m!}{b_1!b_2!...b_n!}$ ,

여기서 $a_1 \ge a_2 \ge \cdots \ge a_m$ 과 $b_1 \ge b_2 \ge \cdots \ge b_n$ 은 양의 정수이고 $a_1 + b_1$ 은 가능한 한 작다. $|a_1 - b_1|$ 은 얼마인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 10 2013 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 2013을 분자와 분모가 각각 팩토리얼들의 곱인 분수로 나타낸다. 즉 2013 = (a_1! a_2! ... a_m!)/(b_1! b_2! ... b_n!)이고, a들은 감소하지 않는 양의 정수, b들도 감소하지 않는 양의 정수다. 이런 모든 표현 중에서 a_1 + b_1이 가장 작아지는 것을 고른다. 그때 |a_1 - b_1|의 값을 구하라.

주어진 것: 2013은 분자의 팩토리얼 곱을 분모의 팩토리얼 곱으로 나눈 값과 같아야 한다; a_1 >= a_2 >= ... >= a_m은 양의 정수 (a_1이 분자에서 가장 큰 수); b_1 >= b_2 >= ... >= b_n은 양의 정수 (b_1이 분모에서 가장 큰 수); 가능한 모든 표현 중 a_1 + b_1이 최소가 된다

구하는 것: a_1 + b_1을 최소로 만드는 표현에서의 |a_1 - b_1| 값

이해

계획

주요 도구: #14 극단의 원리

보조 도구: #7 작은 문제로 쪼개기, #6 추측하고 확인하기

'가장 작게'라는 말은 곧장 극단의 원리를 가리킨다. 여전히 성립하는 가장 작은 a_1과 가장 작은 b_1을 쫓아가면 된다. 열쇠는 소인수다. 팩토리얼 n!은 n이 소수 p까지 올라가야만 그 소수 p를 담으므로, 2013 안의 가장 큰 소수가 a_1을 정하고, 딸려 오는 가장 큰 불필요한 소수가 b_1을 정한다. 문제를 'a_1은 얼마나 작을 수 있나'와 'b_1은 얼마나 작을 수 있나'로 쪼갠 뒤, 실제 표현 하나를 만들어 그 최솟값에 도달함을 확인한다.

실행 — 정답: B

#7 작은 문제로 쪼개기 4.OA.B.4 단계 1

2013을 소인수분해하기

2013을 소인수로 쪼갠다.
2013은 3으로 나누어지므로 2013 = 3 x 671이고, 671 = 11 x 61이다.
11과 61은 모두 소수이므로 2013 = 3 x 11 x 61이다.
가장 큰 소인수는 61이다.

$$2013 = 3 \times 11 \times 61$$

💡 소수로 쪼개면 팩토리얼들이 어떤 재료를 공급해야 하는지 정확히 드러난다.

#14 극단의 원리 6.NS.B.4 단계 2

소수 61이 a_1 = 61을 강제한다

61이 2013을 나누므로 분자의 곱은 61로 나누어져야 한다.
팩토리얼 n!이 소수 61로 나누어지려면 n이 적어도 61이어야 한다.
따라서 분자의 수 중 적어도 하나는 61 이상이고, 그중 가장 큰 a_1은 61 이상이다.
a_1을 최대한 작게 하려면 a_1 = 61로 잡는다.

$$61 \mid 2013 \;\Rightarrow\; a_1 \ge 61, \qquad \min a_1 = 61$$

💡 소수는 수가 그 소수까지 올라가야만 비로소 팩토리얼 안으로 들어온다.

#14 극단의 원리 6.NS.B.4 단계 3

61!이 59를 끌고 와 b_1 = 59를 강제한다

a_1 = 61이면 분자에 61!이 들어 있고, 61!에는 소수 59가 포함된다(60은 소수가 아니므로 59가 61 바로 아래의 가장 큰 소수다).
그런데 59는 2013을 나누지 않으므로, 이 불필요한 59는 분모에서 상쇄되어야 한다.
팩토리얼이 소수 59를 담으려면 그 수가 적어도 59여야 하므로, 분모에서 가장 큰 수 b_1은 적어도 59다.
b_1 = 59로 잡으면 a_1 + b_1 = 61 + 59 = 120이고, a_1 = 61일 때 이미 a_1 >= 61이고 b_1 >= 59이므로 어떤 선택도 이보다 작을 수 없다.

61! \text{ 는 } 59 \text{ 를 포함},\; 59 \nmid 2013 \;\Rightarrow\; b_1 \ge 59, \qquad a_1 + b_1 = 120

💡 분자의 팩토리얼이 끌고 온 불필요한 소수는 그것을 지우려면 분모의 팩토리얼로 맞받아야 한다.

#6 추측하고 확인하기 5.OA.A.1 단계 4

120에 도달하는 표현 만들기

a_1 = 61, b_1 = 59가 정말 가능한지 확인한다.
61!/59!
= 60 x 61 = 3660 = 2^2 x 3 x 5 x 61에서 출발한다.
여기에 11!/10!
= 11을 곱하고 3!/5!
= 1/20을 곱하면 3660 x 11 / 20 = 2013이다.
따라서 2013 = (61!
11!
3!)/(59!
10!
5!)이고, 분자 61 >= 11 >= 3, 분모 59 >= 10 >= 5로 모두 순서에 맞는다.
이는 최솟값 a_1 + b_1 = 120에 도달하는 유효한 표현이다.

$$\frac{61!\,11!\,3!}{59!\,10!\,5!} = (60\cdot 61)\cdot 11 \cdot \frac{1}{20} = 3660\cdot\frac{11}{20} = 2013$$

💡 실제로 성립하는 표현 하나를 보이면 가장 작은 a_1과 b_1이 바람이 아니라 진짜 가능함이 증명된다.

#7 작은 문제로 쪼개기 4.NBT.B.4 단계 5

차를 구하기

최솟값에서 a_1 = 61, b_1 = 59로 정해지므로 구하는 값은 |a_1 - b_1| = |61 - 59| = 2다.
따라서 정답은 (B)다.

$$|a_1 - b_1| = |61 - 59| = 2$$

💡 59가 61 바로 아래의 소수이기 때문에 두 기준점은 딱 2만큼 떨어진다.

[1] #7 4.OA.B.4 2013을 소인수로 쪼갠다. 2013은 3으로 나누어지므로 2013 = 3 x 671이고, 671 = 11 x 61이다. 11과 61은 모두 소

[2] #14 6.NS.B.4 61이 2013을 나누므로 분자의 곱은 61로 나누어져야 한다. 팩토리얼 n!이 소수 61로 나누어지려면 n이 적어도 61이어야 한다. 따라서

[3] #14 6.NS.B.4 a_1 = 61이면 분자에 61!이 들어 있고, 61!에는 소수 59가 포함된다(60은 소수가 아니므로 59가 61 바로 아래의 가장 큰 소수다

[4] #6 5.OA.A.1 a_1 = 61, b_1 = 59가 정말 가능한지 확인한다. 61!/59! = 60 x 61 = 3660 = 2^2 x 3 x 5 x 61에서

[5] #7 4.NBT.B.4 최솟값에서 a_1 = 61, b_1 = 59로 정해지므로 구하는 값은 |a_1 - b_1| = |61 - 59| = 2다. 따라서 정답은 (B)

검토

합리성 확인: 두 기준점은 양쪽 끝에서 나온다. 61은 2013 안의 가장 큰 소수라 분자에 반드시 나타나야 하고, 59는 61!이 어쩔 수 없이 끌고 오지만 2013은 원하지 않는 가장 큰 소수라 분모에 반드시 나타나야 한다. a_1 >= 61과 b_1 >= 59 두 경계가 모두 딱 맞고, 명시적 표현 (61! 11! 3!)/(59! 10! 5!) = 2013이 둘 다 도달됨을 확인해 주므로 |61 - 59| = 2는 확실하다.

대안 접근: 표현을 직접 만들지 않고 필연성만으로 논증할 수도 있다. 유효한 어떤 형태든 분자에 61이 있어야(없으면 61 인수가 없음) a_1 >= 61이고, 61!이 있는 순간 그것이 담은 소수 59는 분모의 어떤 팩토리얼이 59에 이르지 않는 한 갈 곳이 없어 b_1 >= 59다. 항상 a_1 + b_1 >= 120이고 등호가 가능하므로 최소 쌍은 (61, 59)이며 차는 2다.

사용된 CCSS 표준 (최저 학년 6)

4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (2013을 3 x 11 x 61로 쪼개고 61을 가장 큰 소인수로 찾기.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (팩토리얼이 어떤 소수를 담는지 따져 a_1 = 61과 b_1 = 59를 강제하기.)
5.OA.A.1 Use parentheses, brackets, or braces in numerical expressions and evaluate ((61! 11! 3!)/(59! 10! 5!)을 계산해 2013과 같음을 확인하기.)
4.NBT.B.4 Fluently add and subtract multi-digit whole numbers (a_1 + b_1 = 120과 마지막 |61 - 59| = 2를 계산하기.)

⭐ 수 안의 가장 큰 소수가 위쪽 팩토리얼을 정하고, 그것이 딸려 오게 하는 가장 큰 불필요한 소수가 아래쪽 팩토리얼을 정한다.