AMC 10 · 2010 · #25

학년 7 number-theory

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

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

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

문제

짐은 양의 정수 하나에서 시작해 현재 수를 넘지 않는 가장 큰 완전제곱수를 계속 뺀다. 값이 0이 되면 멈춘다. 시작값과 중간 값들, 마지막 0까지 모두 모으면 하나의 목록이 된다. 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.

풀이 과정

전략 거꾸로 풀기

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

1STEP 1

수가 아니라 단계 수를 세기

8개의 수는 뺄셈 7번을 뜻한다. 목록은 0에서 끝나니 0부터 위로, 새 줄을 될 수 있는 대로 작게 쌓는다.

8개의 수 = 7번의 뺄셈, 맨 아래 줄 = 0

2STEP 2

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

값이 c인 줄의 위는 c+s²이다. s²이 최대 제곱수이려면 c+s²이 (s+1)²보다 작아야 하고, s는 c의 절반 이상이다.

c+s² ＜ (s+1)² → c ＜ 2s+1 → s ≥ c/2

3STEP 3

사슬을 위로 쌓기

규칙을 일곱 번 적용해 매번 가장 작은 제곱수를 더한다. 사슬은 0,1,2,3,7,23,167,7223으로 오른다.

0 → 1 → 2 → 3 → 7 → 23 → 167 → 7223

4STEP 4

왜 7223이 정말 가장 작은가

목표가 크면 앞 항도 커지므로, 매 줄에서 가장 작은 값을 택하면 꼭대기 수가 최소인 7223이 된다.

N = 167 + 84² = 167 + 7056 = 7223

5STEP 5

일의 자리 숫자 읽기

묻는 것은 일의 자리 숫자뿐이고, 7223은 3으로 끝나 맞는 선택지는 하나뿐이다.

7223의 일의 자리 숫자 = 3 → (B)

정답

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

💡핵심 정리

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

수가 아니라 단계 수를 세기
가장 작은 앞 항을 구하는 규칙
사슬을 위로 쌓기
왜 7223이 정말 가장 작은가
일의 자리 숫자 읽기

수가 아니라 단계 수를 세기

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

사슬을 위로 쌓기

왜 7223이 정말 가장 작은가

일의 자리 숫자 읽기

비슷한 유형 더 풀어보기