AMC 10 · 2010 · #25

학년 7 number-theory

유형 Branching State Enumeration └ 세부 유형 Numeric Operation Tree

perfect-squaresgreedy-algorithmunits-digit-tracking work-backwards ↑ 선수 지식: perfect-squares

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

문제

짐은 양의 정수 $n$ 에서 시작하여 수의 열을 만든다. 각 다음 수는 현재 수보다 작거나 같은 가장 큰 완전제곱수를 빼서 얻으며, $0$ 에 도달할 때까지 이를 반복한다. 예를 들어 짐이 $n = 55$ 에서 시작하면, 그의 열은 $5$ 개의 수로 이루어진다.

$\begin{array}{ccccc} {}&{}&{}&{}&55\\ 55&-&7^2&=&6\\ 6&-&2^2&=&2\\ 2&-&1^2&=&1\\ 1&-&1^2&=&0\\ \end{array}$

$N$ 을 짐의 열이 $8$ 개의 수를 갖게 되는 가장 작은 수라 하자. $N$ 의 일의 자리 숫자는 무엇인가?

답을 골라 클릭하세요.

(A)

$\ 1$

(B)

$\ 3$

(C)

$\ 5$

(D)

$\ 7$

(E)

$\ 9$

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 짐은 양의 정수 하나에서 시작해서, 현재 수를 넘지 않는 가장 큰 완전제곱수를 계속 빼 나가고, $0$에 도달하면 멈춘다. 시작값, 중간에 나온 값들, 마지막 $0$까지 모두 세면 수들의 목록이 만들어진다. 이 목록이 정확히 $8$개의 수로 이루어지게 하는 가장 작은 시작값 $N$을 찾고, 그 $N$의 일의 자리 숫자를 구하라.

주어진 것: 매 단계마다 현재 수를 넘지 않는 가장 큰 완전제곱수 $s^2$을 뺀다.; 값이 $0$이 되면 과정이 멈춘다.; $n=55$이면 목록은 $55,6,2,1,0$ — 즉 $5$개의 수이다.; 목록이 정확히 $8$개의 수를 가지길 원한다.; 선택지는 일의 자리 숫자다: (A) $1$, (B) $3$, (C) $5$, (D) $7$, (E) $9$.

구하는 것: 목록이 정확히 $8$개의 수가 되는 가장 작은 시작 정수 $N$의 일의 자리 숫자.

이해

계획

주요 도구: #11 거꾸로 풀기

보조 도구: #4 변수 도입하기, #14 극단의 원리, #3 가능성 지우기

앞으로 계산하는 방법은 막막하다. 시작값을 하나씩 넣어 보며 $7$번 뺄셈이 걸리는 수가 나올 때까지 시험해야 하기 때문이다. 그런데 모든 목록의 끝은 항상 같은 값 $0$이다. 그래서 Tool #11(거꾸로 풀기)이 딱 맞는다. $0$에서 시작해 위로 한 항씩 목록을 키워 나가되, 매 단계에서 '현재 수 위에 올 수 있는 가장 작은 수'를 묻는다. 이를 답하려면 Tool #4(변수 도입하기)가 필요하다. 빼는 제곱수를 $s^2$이라 부르고 '값을 넘지 않는 가장 큰 제곱수'라는 말을 $s$에 대한 부등식으로 바꾼다. Tool #14(극단의 원리)는 이 탐욕적 선택을 믿게 해 준다 — 목표값이 커지면 그 위의 최소 예상값도 커지므로, 매 단계에서 가장 작은 값을 택하면 전체적으로도 가장 작은 $N$이 나온다. 마지막으로 Tool #3(가능성 지우기)이 마무리한다. 구한 일의 자리 숫자에 맞는 선택지는 단 하나뿐이다.

실행 — 정답: B

#11 거꾸로 풀기 6.EE.B.5 단계 1

수가 아니라 단계 수를 세기

$8$개의 수 사이에는 화살표가 $7$개 있으므로 뺄셈이 정확히 $7$번 필요하다.
모든 목록은 $0$에서 끝나므로 맨 아래에 $0$을 놓고, 그 위로 $7$줄이 쌓일 때까지 한 줄씩 위로 만들어 간다.
가장 작은 $N$을 얻으려면 새 줄을 될 수 있는 대로 작게 만든다.

$$8\text{개의 수} \;=\; 7\text{번의 뺄셈}, \qquad \text{맨 아래 줄} = 0$$

💡 도착점 $0$은 변하지 않으므로 시작값을 뒤지는 것보다 $0$에서 위로 사슬을 키우는 편이 훨씬 쉽다.

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

가장 작은 앞 항을 구하는 규칙

어떤 줄의 값이 $c$라 하자.
바로 위 줄은 $c+s^2$이어야 하며, 여기서 $s^2$은 그 자리에서 빼는 제곱수다.
$s^2$이 정말로 $c+s^2$을 넘지 않는 가장 큰 제곱수이려면, 그 값이 다음 제곱수 $(s+1)^2$보다 작아야 한다.
이 부등식을 풀면 $s$는 적어도 $c$의 절반이어야 한다.
앞 항 $c+s^2$을 작게 하려면 허용되는 가장 작은 $s$를 고른다.

$$c+s^2 < (s+1)^2 \;\Rightarrow\; c < 2s+1 \;\Rightarrow\; s \ge \tfrac{c}{2}$$

💡 빼는 제곱수가 너무 작으면 남은 값이 다음 제곱수를 넘어서 더 큰 제곱수가 대신 쓰이게 된다.

#11 거꾸로 풀기 6.EE.A.1 단계 3

사슬을 위로 쌓기

규칙을 일곱 번 적용한다.
매번 허용되는 가장 작은 $s$를 골라 $s^2$을 더한다.
$0$에서 시작해 $1^2$을 세 번 더한 뒤, 값이 커질수록 필요한 $s$도 커진다.
사용된 제곱수는 $1,1,1,4,16,144,7056$이다.

$$0 \xrightarrow{+1^2} 1 \xrightarrow{+1^2} 2 \xrightarrow{+1^2} 3 \xrightarrow{+2^2} 7 \xrightarrow{+4^2} 23 \xrightarrow{+12^2} 167 \xrightarrow{+84^2} 7223$$

💡 각 도약은 같은 제곱수를 유지하는 가장 작은 걸음으로 정해지므로 사다리는 최대한 천천히 올라간다.

#14 극단의 원리 6.EE.B.5 단계 4

왜 7223이 정말 가장 작은가

$s\ge \tfrac{c}{2}$인 앞 항 $c+s^2$은 목표값 $c$가 커질수록 커진다.
따라서 어느 줄에서든 값이 더 작으면 그 위의 값이 더 커질 일은 결코 없다.
그러므로 모든 줄에서 가장 작은 값을 택하면 맨 위 수도 가장 작아져 $N=7223$이 된다.
아래로 내려가는 목록 $7223,167,23,7,3,2,1,0$은 실제로 $8$개의 수다.

$$N = 167 + 84^2 = 167 + 7056 = 7223$$

💡 큰 목표는 큰 앞 항을 요구하므로, 매 단계 가장 작은 것을 택하는 탐욕적 방법은 절대 지지 않는다.

#3 가능성 지우기 6.EE.B.5 단계 5

일의 자리 숫자 읽기

문제는 $N$의 일의 자리 숫자만 묻는다.
$7223$의 일의 자리 숫자는 $3$이며, 이는 단 하나의 선택지와 일치한다.

$$7223\text{의 일의 자리 숫자} = 3 \;\Rightarrow\; \textbf{(B)}$$

💡 $3$으로 끝나는 선택지는 (B)뿐이므로 나머지는 한눈에 지워진다.

[1] #11 6.EE.B.5 $8$개의 수 사이에는 화살표가 $7$개 있으므로 뺄셈이 정확히 $7$번 필요하다. 모든 목록은 $0$에서 끝나므로 맨 아래에 $0$을 놓고,

[2] #4 7.EE.B.4 어떤 줄의 값이 $c$라 하자. 바로 위 줄은 $c+s^2$이어야 하며, 여기서 $s^2$은 그 자리에서 빼는 제곱수다. $s^2$이 정말로 $

[3] #11 6.EE.A.1 규칙을 일곱 번 적용한다. 매번 허용되는 가장 작은 $s$를 골라 $s^2$을 더한다. $0$에서 시작해 $1^2$을 세 번 더한 뒤, 값이 커

[4] #14 6.EE.B.5 $s\ge \tfrac{c}{2}$인 앞 항 $c+s^2$은 목표값 $c$가 커질수록 커진다. 따라서 어느 줄에서든 값이 더 작으면 그 위의 값

[5] #3 6.EE.B.5 문제는 $N$의 일의 자리 숫자만 묻는다. $7223$의 일의 자리 숫자는 $3$이며, 이는 단 하나의 선택지와 일치한다.

검토

합리성 확인: $7223$에 짐의 과정을 실제로 앞으로 돌려 보자. $7223$을 넘지 않는 가장 큰 제곱수는 $84^2=7056$이고 남는 값은 $167$이다. 이어 $12^2=144$로 $23$, $4^2=16$으로 $7$, $2^2=4$로 $3$이 남고, 다시 $1,1,1$을 빼며 $2,1,0$으로 내려간다. 목록은 $7223,167,23,7,3,2,1,0$ — 정확히 $8$개의 수이므로 개수가 맞는다. 앞 항이 커지는 성질 때문에 더 작은 시작값은 반드시 더 짧은 목록을 만들므로 $7223$이 최소이고, 그 일의 자리 숫자 $3$이 (B)를 준다.

대안 접근: 부등식 규칙 대신 각 목록 길이가 처음 나타나는 가장 작은 수를 직접 표로 만들 수도 있다. 길이 $1,2,3,\dots$은 각각 $1,2,3,7,23,167,7223$에서 처음 나타난다. 이 수열을 보면 새 기록은 언제나 직전 값에 '그 절반 이상인 가장 작은 정수'의 제곱을 더한 것이며, 이는 부등식을 추상적으로 세우지 않고도 $7223$을 재현한다.

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

6.EE.A.1 Write and evaluate numerical expressions involving whole-number exponents (사슬을 $7223$까지 쌓으며 $2^2=4$, $12^2=144$, $84^2=7056$ 같은 빼는 제곱수를 계산하는 데 사용.)
7.EE.B.4 Use variables to represent quantities and construct simple equations and inequalities ('값을 넘지 않는 가장 큰 제곱수'를 부등식 $c+s^2<(s+1)^2$으로 바꾸고 풀어 $s\ge \tfrac{c}{2}$을 얻는 데 사용.)
6.EE.B.5 Understand solving an equation or inequality as a process of finding values (각 줄에서 조건을 만족하는 가장 작은 $s$를 고르고, 탐욕적 선택이 가장 작은 $N$을 준다고 논증하는 데 사용.)

⭐ $0$에서 위로 사슬을 쌓되 같은 뺄셈을 유지하는 가장 작은 제곱을 늘 더하라 — 가장 천천히 자라는 사다리의 꼭대기가 바로 가장 작은 시작값이다.