AMC 10 · 2013 · #21

학년 6 number-theory

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

prime-factorizationfactorialdivisibility-rules convert-to-algebrapattern-recognition ↑ 선수 지식: prime-factorization

📏 긴 풀이 💡 3 개 인사이트

문제

$12$ 명의 해적으로 이루어진 무리가 금화가 든 보물 상자를 다음과 같이 나눠 가지기로 했다. $k^{\text{th}}$ 번째 순서로 자기 몫을 가져가는 해적은 상자에 남아 있는 금화의 $\frac{k}{12}$ 를 가져간다. 처음에 상자에 든 금화의 개수는 이 방식으로 각 해적이 양의 정수 개의 금화를 받을 수 있게 하는 가장 작은 수이다. $12^{\text{th}}$ 번째 해적이 받는 금화는 몇 개인가?

답을 골라 클릭하세요.

(A)

720

(B)

1296

(C)

1728

(D)

1925

(E)

3850

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 12명의 해적이 순서대로 금화를 나눈다. k번째 해적은 자기 차례에 상자에 남아 있는 금화의 k/12를 가져간다. 상자에 처음 담긴 금화 수는, 12명 모두가 양의 정수 개의 금화를 받을 수 있게 하는 가장 작은 수다. 12번째(마지막) 해적이 받는 금화가 몇 개인지 구하여라.

주어진 것: 12명의 해적이 차례로 금화를 가져간다.; k번째 해적은 자기 차례에 상자에 남은 금화의 k/12를 가져간다.; 처음 금화 수는 모든 몫이 양의 정수가 되게 하는 가장 작은 수다.; 12번째 해적이 마지막이고 12/12 = 1이므로, 그는 상자에 남은 금화를 전부 가져간다.

구하는 것: 12번째 해적이 받는 금화의 개수.

이해

계획

주요 도구: #4 변수 도입하기

보조 도구: #5 패턴 찾기, #7 작은 문제로 쪼개기, #3 가능성 지우기

처음 개수를 모르니 문자로 이름 붙이고 12번째 해적의 몫을 하나의 분수로 쓴다. 이 몫은 처음 개수가 분모를 지워줄 때만 정수가 되므로, 진짜 핵심은 소인수 문제다. 분모가 필요로 하는 2와 3의 거듭제곱을 딱 맞게 공급하는 가장 작은 처음 개수를 찾고, 무엇이 남는지 본다.

실행 — 정답: D

#5 패턴 찾기 5.NF.B.4 단계 1

매 차례 남는 금화 따라가기

k번째 해적이 상자의 k/12를 가져가면, 그가 남기는 몫은 1 - k/12 = (12-k)/12이다.
그래서 매 차례는 금화 더미에 간단한 분수를 곱한다.
1번째 해적은 11/12를, 2번째는 10/12를 남기고, 11번째는 1/12를 남긴다.
그러면 12번째 해적이 그 12/12를 가져가니, 상자에 남은 것을 전부 쓸어 담는다.

\text{해적 } k \text{ 이후: } \ \text{남는 양} = \frac{12-k}{12}\times(\text{직전 더미})

💡 남은 것의 일부를 가져가는 것은 더미에 남는 비율을 곱하는 것과 같다.

#4 변수 도입하기 6.EE.B.6 단계 2

마지막 해적의 몫 쓰기

처음 금화 수를 N이라 하자.
1번부터 11번 해적이 각자의 비율만큼 남기면, 더미에는 11/12, 10/12, ..., 1/12가 차례로 곱해진다.
그래서 12번째 해적이 통째로 가져가는 남은 금화는, N에 이 분자들의 곱을 12를 열두 번이 아니라 열한 번 곱한 값으로 나눈 것이다.
분자들의 곱은 11 x 10 x 9 x ...
x 1 = 11!
(11 팩토리얼)이고, 분모에는 12가 열한 개 있다.

$$S_{12} = N\cdot\frac{11\cdot10\cdots1}{12^{11}} = \frac{N\cdot 11!}{12^{11}}$$

💡 남는 비율들을 이어 곱하면 전체 과정이 마지막 몫에 대한 깔끔한 식 하나로 바뀐다.

#7 작은 문제로 쪼개기 6.EE.A.1 단계 3

조각들을 소수로 분해하기

이것이 언제 정수가 되는지 보려면 분자와 분모를 소인수로 분해한다.
분모 12^{11} = (2^2 x 3)^{11} = 2^{22} x 3^{11}이다.
분자 11!
= 2^8 x 3^4 x 5^2 x 7 x 11이다 (11!에는 2가 여덟 개, 3이 네 개, 5가 두 개, 7이 한 개, 11이 한 개 있다).
공통된 2와 3을 지우면 12번째 해적의 몫은 N에 5^2 x 7 x 11을 곱한 값을, 분모에 여전히 남은 2와 3의 거듭제곱으로 나눈 것이 된다.

$$S_{12} = \frac{N\cdot 2^{8}\cdot 3^{4}\cdot 5^{2}\cdot 7\cdot 11}{2^{22}\cdot 3^{11}} = \frac{N\cdot 5^{2}\cdot 7\cdot 11}{2^{14}\cdot 3^{7}}$$

💡 소인수분해는 어떤 인수를 공급해야 하고 어떤 것이 지워지는지 정확히 보여준다.

#7 작은 문제로 쪼개기 6.NS.B.4 단계 4

가장 작은 처음 개수 찾기

이제 분모에는 2^{14} x 3^{7}이 남는다.
몫이 정수가 되려면 N은 적어도 2를 열네 개, 3을 일곱 개 공급해야 한다.
앞선 각 해적을 같은 방식으로 확인해 보면, 어느 앞 차례도 이 마지막 차례보다 더 많은 2나 3을 요구하지 않는다.
그래서 마지막 몫이 정수가 되면 앞의 모든 몫도 정수가 된다.
따라서 가장 작은 N은 정확히 N = 2^{14} x 3^{7}이며, 다른 소수는 더할 필요가 없다.

$$N_{\min} = 2^{14}\cdot 3^{7}$$

💡 가장 작은 안전한 처음 개수는 가장 까다로운 차례를 지울 만큼의 2와 3만 딱 지닌다.

#3 가능성 지우기 4.OA.B.4 단계 5

지우고 몫 읽어내기

몫에 N = 2^{14} x 3^{7}을 대입한다.
N의 2^{14}과 3^{7}이 분모의 2^{14}과 3^{7}을 완벽히 지워, 5^2 x 7 x 11 = 25 x 77 = 1925만 남는다.
2의 인수가 모두 지워졌으니 답은 반드시 홀수인데, 보기 중 홀수는 1925뿐이다.
12번째 해적은 1925개의 금화를 받으며, 답은 (D)이다.

$$S_{12} = 2^{14}\cdot 3^{7}\cdot\frac{5^{2}\cdot 7\cdot 11}{2^{14}\cdot 3^{7}} = 5^{2}\cdot 7\cdot 11 = 1925$$

💡 N을 모든 2와 3을 지우도록 만들었기에, 홀수 인수 5, 5, 7, 11만 살아남는다.

[1] #5 5.NF.B.4 k번째 해적이 상자의 k/12를 가져가면, 그가 남기는 몫은 1 - k/12 = (12-k)/12이다. 그래서 매 차례는 금화 더미에 간단한 분

[2] #4 6.EE.B.6 처음 금화 수를 N이라 하자. 1번부터 11번 해적이 각자의 비율만큼 남기면, 더미에는 11/12, 10/12, ..., 1/12가 차례로 곱해

[3] #7 6.EE.A.1 이것이 언제 정수가 되는지 보려면 분자와 분모를 소인수로 분해한다. 분모 12^{11} = (2^2 x 3)^{11} = 2^{22} x 3^{

[4] #7 6.NS.B.4 이제 분모에는 2^{14} x 3^{7}이 남는다. 몫이 정수가 되려면 N은 적어도 2를 열네 개, 3을 일곱 개 공급해야 한다. 앞선 각 해적

[5] #3 4.OA.B.4 몫에 N = 2^{14} x 3^{7}을 대입한다. N의 2^{14}과 3^{7}이 분모의 2^{14}과 3^{7}을 완벽히 지워, 5^2 x

검토

합리성 확인: 처음 개수를 2^{14} x 3^{7}만 딱 담고 그 이상은 담지 않도록 골랐으므로, 그 소수들은 완전히 지워지고 최종 몫은 5^2 x 7 x 11 = 1925가 된다. 2의 인수가 전부 사라졌으니 답은 홀수여야 하는데, 다섯 보기 중 홀수는 1925뿐이라 (D)가 확인되고 나머지는 한눈에 지워진다.

대안 접근: 마지막 해적부터 거꾸로 생각한다. 그는 남은 전부, 즉 N x 11!/12^{11}을 가져간다. N을 먼저 최소화하는 대신, 분자 11 x 10 x ... x 1을 12^{11} = 2^{22} x 3^{11}에 대해 지운다. 가장 작은 N은 남은 2^{14} x 3^{7}만 채우고, 살아남는 홀수 5^2 x 7 x 11 = 1925가 바로 마지막 해적의 몫이다. 시험에서 더 빠른 방법: 2의 거듭제곱이 모두 지워지므로 답은 홀수이고, 홀수는 (D) 1925뿐이다.

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

5.NF.B.4 Apply and extend understanding of multiplication to multiply a fraction by a fraction ('남은 금화의 k/12를 가져간다'를 더미에 남는 비율 (12-k)/12를 곱하는 것으로 바꾸기)
6.EE.B.6 Use variables to represent numbers and write expressions to solve problems (처음 개수를 N으로 이름 붙이고 12번째 해적의 몫을 N x 11!/12^{11}로 쓰기)
6.EE.A.1 Write and evaluate numerical expressions involving whole-number exponents (12^{11} = 2^{22} x 3^{11}과 11! = 2^8 x 3^4 x 5^2 x 7 x 11을 소수 거듭제곱으로 분해하기)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (모든 몫을 정수로 만드는 데 딱 필요한 인수를 공급하는 가장 작은 N = 2^{14} x 3^{7} 찾기)
4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (살아남는 홀수 인수 5 x 5 x 7 x 11 = 1925를 읽어내고 홀짝으로 답 확인하기)

⭐ '남은 것의 몇 분의 몇'을 이어 붙여 하나의 식으로 만들고, 소인수가 가장 작은 시작값과 무엇이 살아남는지 알려주게 하라.