AMC 10 · 2016 · #25

학년 9 number-theory

유형 Lattice / Grid Pattern from Small Cases └ 세부 유형 Figure-N Growth Sequence

floor-functionperfect-squaresplace-valuedigit-sum easier-related-problempattern-recognition ↑ 선수 지식: floor-functionperfect-squares

📏 긴 풀이 💡 4 개 인사이트

문제

제곱수를 적고 끝자리를 지우다가 두 값이 크게 벌어지면 멈춘다. 긴 합의 자릿수를 더하여라.

답을 골라 클릭하세요.

(A)

7986

(B)

8002

(C)

8030

(D)

8048

(E)

8064

풀이 과정

전략 변수 도입하기

칠판 놀이는 사실 식 하나, 즉 b(x)=⌊ x²/10^k ⌋이다. 그래서 도구 #4(변수 도입하기)가 두 번 엔진 역할을 한다. 먼저 b(x)에 이름을 붙이고, 그다음 x = 5 · 10^k-1+m으로 기준을 옮기는데 이 한 수가 모든 것을 무너뜨린다. 도구 #9(더 쉬운 문제로 줄이기)는 그림을 준다: k=2 놀이를 손으로 직접 해 보고 어디서 걸려 넘어지는지 보면 일반 k의 작동 원리가 눈에 보인다. 도구 #14(극단의 원리)는 이 문제의 핵심인 두 개의 최소성 논증을 맡는다. 2만큼의 도약이 애초에 가능해지는 가장 이른 x, 그리고 그것이 실제로 처음 일어나는 정확한 x이다. 도구 #5(패턴 찾기)가 마무리한다: 1008개의 f 값이 두 개의 반복되는 숫자열로 쌓이고, 자리 숫자의 합은 열을 세는 것으로 나온다.

1STEP 1

지우기를 버림 나눗셈으로 바꾸기

지우기는 내림이 붙은 단순한 나눗셈이다.

b(x)=⌊ x²/10²ⁿ ⌋, x = 10ⁿ, 10ⁿ+1, 10ⁿ+2, …, b(10ⁿ)=1

2STEP 2

칠판은 끊기지 않는 연속열이다

칠판은 끊기지 않는 연속열을 적는다.

f(k) = B+1, B = b(x^-1), x^ = min{x : b(x)-b(x-1) ≥ 2}

3STEP 3

k=2 놀이를 손으로 해 보기

가장 작은 경우를 손으로 해 본다.

59² = 3481 → 34, 60² = 3600 → 36, f(2) = 35

4STEP 4

도약에는 2x-1 ＞ 10²ⁿ이 필요하다

도약하려면 간격이 나누는 수를 넘어야 한다.

b(x)-b(x-1) ≥ 2 ⟹ 2x-1 ＞ 10²ⁿ ⟹ x ≥ 5 · 10²ⁿ⁻¹+1

5STEP 5

5 · 10²ⁿ⁻¹을 기준으로 옮기기

기준을 옮기면 식이 깔끔해진다.

x = 5 · 10²ⁿ⁻¹+m ⟹ b(x) = 25 · 10²ⁿ⁻² + m + ⌊ m²/10²ⁿ ⌋

6STEP 6

처음 넘치는 순간이 f(2n)을 준다

처음 넘치는 순간이 빠진 값을 지목한다.

f(2n) = 25 · 10²ⁿ⁻²+10ⁿ; f(2)=35, f(4)=2600, f(6)=251000, f(8)=25010000

7STEP 7

전체 합을 두 더미로 나누기

긴 합이 두 더미로 나뉜다.

S = 2525…25₂₅가 1008개 + 111…110₁이 1008개, 그 뒤 0

8STEP 8

열을 더해 자리 숫자를 합하기

열을 더하면 8064, 보기 (E).

7056 + 1008 = 8064 → (E)

정답

8064

서로 독립적인 여러 확인이 모두 들어맞는다. 이 공식은 문제가 간접적으로 알려 준 경우를 재현하고, k=2 놀이를 그대로 돌려 보면(제곱수 2500, 2601, …, 3481, 3600, 칠판 25, 26, …, 34, 36) 35가 처음 건너뛴 수임이 확인된다. k=4를 처음부터 돌려 보면 첫 도약이 5099² → 5100², 칠판으로는 2599 → 2601에서 일어나 f(4) = 2600이 되는데, 이는 25 · 10²+10²이 예측한 값과 정확히 같다. k=6은 251000, k=8은 25010000으로 역시 일치한다. 모양으로도 확인된다. 각 f(2n)의 자리 숫자 합은 2+5+1 = 8이고(작은 n에서는 1이 2나 5 위에 겹쳐 35, 2600이 되지만 합은 그대로 8이다), 전체 합이 받아올림 없이 더해지므로 자리 숫자의 합은 1008 × 8 = 8064여야 한다. 끝으로 답이 8의 배수라는 점에서 7986, 8002, 8030은 바로 걸러지고, 남은 둘 중에서는 항이 1008개라는 사실이 8048이 아니라 8064를 고른다.

💡핵심 정리

k자리를 지우는 것은 10^k으로 나누는 것이고, x = 5 · 10^k-1을 지나면 칠판은 남은 제곱이 10^k을 통째로 채울 때까지 그냥 하나씩 세어 올라간다. 바로 그 한 순간이 건너뛰는 수이며, 그런 수 1008개를 쌓아 더하면 받아올림 없이 자리별로 더해진다.

지우기를 버림 나눗셈으로 바꾸기
칠판은 끊기지 않는 연속열이다
k=2 놀이를 손으로 해 보기
도약에는 2x-1 ＞ 10²ⁿ이 필요하다
5 · 10²ⁿ⁻¹을 기준으로 옮기기
처음 넘치는 순간이 f(2n)을 준다
전체 합을 두 더미로 나누기
열을 더해 자리 숫자를 합하기

지우기를 버림 나눗셈으로 바꾸기

칠판은 끊기지 않는 연속열이다

k=2 놀이를 손으로 해 보기

도약에는 2x-1 ＞ 10²ⁿ이 필요하다

5 · 10²ⁿ⁻¹을 기준으로 옮기기

처음 넘치는 순간이 f(2n)을 준다

전체 합을 두 더미로 나누기

열을 더해 자리 숫자를 합하기

비슷한 유형 더 풀어보기