AMC 10 · 2002 · #22

학년 8 number-theory

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

perfect-squarespattern-recognitionfloor-function pattern-recognition ↑ 선수 지식: perfect-squares

📏 긴 풀이 💡 3 개 인사이트

문제

1번부터 100번까지 번호가 매겨진 타일 100개로 시작합니다. 한 번의 조작은 두 가지를 합니다: 먼저 번호가 완전제곱수인 타일(1,4,9,…)을 모두 버리고, 그다음 남은 타일을 빈틈 없이 1,2,3,…으로 다시 번호 매깁니다. 이 조작 전체를 계속 반복합니다. 타일이 단 하나만 남을 때까지 조작을 몇 번 해야 하는지 세어 보세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 패턴 찾기

100부터 타일 하나하나를 따라가며 끝까지 흉내 내는 것은 느리므로, 도구 #5(패턴 찾기)가 앞장섭니다: 조작을 두어 번 해 보며 개수가 100에서 어떻게 줄어드는지 지켜봅니다. 핵심은 각 단계 후 타일이 다시 1,2,3,…으로 번호 매겨지기 때문에 타일의 개수만 중요하다는 점입니다. 왜 이 패턴이 성립하는지 보려면 도구 #4(변수 도입하기)로 개수를 n이라 부르고, 한 번의 조작이 n 이하의 완전제곱수를 정확히 제거함을 확인합니다. 도구 #9(더 쉬운 문제로 줄이기)가 이를 더 날카롭게 합니다: 개수가 완전제곱수 n=k²일 때 무슨 일이 일어나는지 시험하면 깔끔한 규칙이 나타납니다 — 두 번의 조작은 항상 k²개의 타일을 (k-1)²개로 바꿉니다. 그러면 조작 횟수를 세는 일은 10²에서 1²까지 완전제곱수를 몇 번 한 칸씩 내리는지 세는 것일 뿐입니다.

1STEP 1

조작을 두 번 하고 개수를 지켜보기

개수만 중요합니다. 100개엔 제곱수 10개 → 90개, 90개엔 9개 → 81=9²개.

100 → 90 → 81; 100=10², 81=9²

2STEP 2

제곱근으로 제거 개수 세기

개수를 n이라 하면 n 이하 제곱수는 1²,…,⌊√(n)⌋²이므로 매번 ⌊√(n)⌋개가 빠집니다: n → n-⌊√(n)⌋. n=90이면 9개.

n ⟶ n-⌊√(n)⌋; ⌊√(90)⌋=9

3STEP 3

두 번의 조작이 완전제곱수를 한 칸 내림

n=k²이면 k개가 빠져 k²-k, 이는 (k-1)² 바로 위입니다. 다음 조작이 k-1개를 빼 정확히 (k-1)²에 안착합니다.

k² → k²-k → k²-2k+1=(k-1)²

4STEP 4

제곱수를 한 칸씩 내리며 세기

밑이 10²→9²→…→1²로 떨어지고 1²=1개가 멈춤 지점. 9번 내림 × 2 = 18번, 선택지 (C).

10²→ 9²→…→ 1²₉번 내림, 9 × 2 = 18 → (C)

정답

확실히 하기 위해 개수를 끝까지 곧장 흉내 냅니다: 100→ 90→ 81→ 72→ 64→ 56→ 49→ 42→ 36→ 30→ 25→ 20→ 16→ 12→ 9→ 6→ 4→ 2→ 1. 화살표를 세면 18번의 조작이고, 모든 완전제곱수 값(81,64,49,36,25,16,9,4,1)이 두-단계 규칙이 예측한 바로 그 자리에 나타납니다. 답 18은 선택지 사이에서도 합리적입니다: 순진한 추측은 10(시작 제곱수당 한 번)이나 20(제곱수 열 개에 대해 각각 두 번)일 수 있지만, 과정은 제곱수를 9번만 내린 뒤 1²에서 끝나므로 20이 아니라 18이 맞습니다.

💡핵심 정리

타일 개수만 중요하고, 매 두 번의 조작이 완전제곱수 개수를 한 칸씩 낮추므로, 10²개의 타일은 타일 하나에 도달하는 데 9 × 2=18번의 조작이 필요합니다.

조작을 두 번 하고 개수를 지켜보기
제곱근으로 제거 개수 세기
두 번의 조작이 완전제곱수를 한 칸 내림
제곱수를 한 칸씩 내리며 세기

조작을 두 번 하고 개수를 지켜보기

제곱근으로 제거 개수 세기

두 번의 조작이 완전제곱수를 한 칸 내림

제곱수를 한 칸씩 내리며 세기

비슷한 유형 더 풀어보기