AMC 10 · 2002 · #22
학년 8 number-theory1 번부터 100 번까지 번호가 매겨진 타일들의 집합에 대해 다음 조작을 반복한다: 완전제곱수 번호가 붙은 타일을 모두 없애고, 남은 타일에 1 부터 차례로 다시 번호를 매긴다. 집합의 타일 개수를 하나로 줄이려면 이 조작을 몇 번 해야 하는가?
답을 골라 클릭하세요.
AMC 10 2002 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.
도구 + CCSS 풀이
이해
문제 재정리: $1$번부터 $100$번까지 번호가 매겨진 타일 $100$개로 시작합니다. 한 번의 조작은 두 가지를 합니다: 먼저 번호가 완전제곱수인 타일($1,4,9,\dots$)을 모두 버리고, 그다음 남은 타일을 빈틈 없이 $1,2,3,\dots$으로 다시 번호 매깁니다. 이 조작 전체를 계속 반복합니다. 타일이 단 하나만 남을 때까지 조작을 몇 번 해야 하는지 세어 보세요.
주어진 것: 시작 집합은 $1$번부터 $100$번까지의 타일이므로 타일은 $100$개; 각 조작은 현재 번호가 완전제곱수인 타일을 정확히 제거함; 제거 후 남은 타일은 $1,2,3,\dots$으로 다시 번호가 매겨져 집합이 다시 $1$부터 (새 개수)까지가 됨; 선택지: (A) $10$, (B) $11$, (C) $18$, (D) $19$, (E) $20$
구하는 것: 집합을 정확히 타일 하나로 줄이는 데 필요한 조작 횟수
이해
문제 재정리: $1$번부터 $100$번까지 번호가 매겨진 타일 $100$개로 시작합니다. 한 번의 조작은 두 가지를 합니다: 먼저 번호가 완전제곱수인 타일($1,4,9,\dots$)을 모두 버리고, 그다음 남은 타일을 빈틈 없이 $1,2,3,\dots$으로 다시 번호 매깁니다. 이 조작 전체를 계속 반복합니다. 타일이 단 하나만 남을 때까지 조작을 몇 번 해야 하는지 세어 보세요.
주어진 것: 시작 집합은 $1$번부터 $100$번까지의 타일이므로 타일은 $100$개; 각 조작은 현재 번호가 완전제곱수인 타일을 정확히 제거함; 제거 후 남은 타일은 $1,2,3,\dots$으로 다시 번호가 매겨져 집합이 다시 $1$부터 (새 개수)까지가 됨; 선택지: (A) $10$, (B) $11$, (C) $18$, (D) $19$, (E) $20$
계획
주요 도구: #5 패턴 찾기
보조 도구: #4 변수 도입하기, #9 더 쉬운 문제로 줄이기
$100$부터 타일 하나하나를 따라가며 끝까지 흉내 내는 것은 느리므로, 도구 #5(패턴 찾기)가 앞장섭니다: 조작을 두어 번 해 보며 개수가 $100$에서 어떻게 줄어드는지 지켜봅니다. 핵심은 각 단계 후 타일이 다시 $1,2,3,\dots$으로 번호 매겨지기 때문에 타일의 개수만 중요하다는 점입니다. 왜 이 패턴이 성립하는지 보려면 도구 #4(변수 도입하기)로 개수를 $n$이라 부르고, 한 번의 조작이 $n$ 이하의 완전제곱수를 정확히 제거함을 확인합니다. 도구 #9(더 쉬운 문제로 줄이기)가 이를 더 날카롭게 합니다: 개수가 완전제곱수 $n=k^2$일 때 무슨 일이 일어나는지 시험하면 깔끔한 규칙이 나타납니다 — 두 번의 조작은 항상 $k^2$개의 타일을 $(k-1)^2$개로 바꿉니다. 그러면 조작 횟수를 세는 일은 $10^2$에서 $1^2$까지 완전제곱수를 몇 번 한 칸씩 내리는지 세는 것일 뿐입니다.
실행 — 정답: C
6.EE.A.1 단계 1 조작을 두 번 하고 개수를 지켜보기
- 각 단계 후 남은 타일이 다시 $1,2,3,\dots$으로 번호 매겨지므로 타일의 개수만 중요합니다.
- 타일 $100$개로 시작합니다.
- $1$부터 $100$까지의 완전제곱수는 $1,4,9,16,25,36,49,64,81,100$ — $10$개 — 이므로 첫 번째 조작은 $10$개를 제거하고 $100-10=90$개를 남깁니다.
- 이제 타일이 $90$개입니다.
- $1$부터 $90$까지의 완전제곱수는 $1,4,\dots,81$ — $9$개 ($9^2=81\le 90$이지만 $10^2=100>90$이므로) — 이므로 두 번째 조작은 $9$개를 제거하고 $90-9=81$개를 남깁니다.
- $81=9^2$은 그 자체로 완전제곱수임에 주목하세요.
- 그래서 두 번의 조작이 $100=10^2$에서 $81=9^2$으로 내려주었습니다.
💡 타일이 매번 다시 번호 매겨지므로 바뀌는 것은 오직 개수뿐입니다.
8.EE.A.2 단계 2 제곱근으로 제거 개수 세기
- 현재 개수를 $n$이라 합시다.
- 한 번의 조작은 번호가 완전제곱수인 타일을 모두 제거하는데, $n$ 이하의 완전제곱수는 $1^2,2^2,\dots$부터 $n$ 이하인 가장 큰 제곱수까지입니다.
- 그 가장 큰 것은 $\lfloor\sqrt{n}\rfloor^2$이므로, 제거되는 타일 수는 정확히 $\lfloor\sqrt{n}\rfloor$ — 제곱이 $n$을 넘지 않는 가장 큰 정수 — 입니다.
- 예를 들어 $n=90$이면 $\sqrt{90}\approx 9.49$이므로 $\lfloor\sqrt{90}\rfloor=9$개가 떨어져 나가며, 앞서 본 것과 일치합니다.
- 이것은 모든 단계에 대한 하나의 깔끔한 규칙을 줍니다: 타일 $n$개에서 $n-\lfloor\sqrt{n}\rfloor$개로 갑니다.
💡 $n$ 이하 완전제곱수의 개수는 제곱수가 $n$을 넘기 전까지 갈 수 있는 거리, 즉 $\lfloor\sqrt{n}\rfloor$입니다.
6.EE.A.3 단계 3 두 번의 조작이 완전제곱수를 한 칸 내림
- 규칙을 완전제곱수 $n=k^2$에 시험해 봅니다.
- 첫 번째 조작: $\lfloor\sqrt{k^2}\rfloor=k$이므로 $k$개를 제거하고 $k^2-k$를 남깁니다.
- 이제 $k^2-k$ 이하인 제곱수는 몇 개일까요?
- $(k-1)^2=k^2-2k+1$은 ($k\ge 1$일 때) $k^2-k$ 이하이지만 $k^2$은 $k^2-k$보다 크므로, $k^2-k$ 이하 가장 큰 제곱수는 $(k-1)^2$이고 $\lfloor\sqrt{k^2-k}\rfloor=k-1$입니다.
- 두 번째 조작은 $k-1$개를 제거하여 $k^2-k-(k-1)=k^2-2k+1=(k-1)^2$을 남깁니다.
- 그래서 두 번의 조작은 항상 $k^2$개의 타일을 $(k-1)^2$개로 내려줍니다.
- 이는 1단계와 일치합니다: $10^2\to 9^2$.
💡 제곱 개수에서 $k$개를 떼어내면 바로 아래 제곱수 바로 위에 내려앉으므로, 한 번 더 떼어내면 정확히 그 제곱수에 안착합니다.
4.OA.C.5 단계 4 제곱수를 한 칸씩 내리며 세기
- 두-조작 규칙을 반복 적용하며 완전제곱수의 밑이 매번 $1$씩 떨어지는 것을 봅니다: $10^2\to 9^2\to 8^2\to\cdots\to 2^2\to 1^2$.
- $1^2=1$에 도달했다는 것은 타일 하나가 남았다는 뜻이며, 이것이 멈추는 지점입니다.
- 밑이 $10$에서 $1$까지 내려가는 것은 $9$번 내려가는 것이고, 각 내림은 $2$번의 조작이 드므로 $9\times 2=18$번의 조작입니다.
- (마지막 구간 직접 확인: 타일 $4$개는 $2$개를 제거해 $2$개가 되고, 타일 $2$개는 $1$개를 제거해 $1$개가 됩니다 — $17$번째와 $18$번째 조작.) 그래서 $18$번의 조작이 필요하며, 이는 선택지 (C)입니다.
💡 매 두 번의 조작이 제곱의 밑을 하나씩 낮추므로, 아홉 번의 낮춤이 $10^2$을 타일 하나까지 데려갑니다.
6.EE.A.1 각 단계 후 남은 타일이 다시 $1,2,3,\dots$으로 번호 매겨지므로 타일의 개수만 중요합니다. 타일 $100$개로 시작합니다. $1$부터 8.EE.A.2 현재 개수를 $n$이라 합시다. 한 번의 조작은 번호가 완전제곱수인 타일을 모두 제거하는데, $n$ 이하의 완전제곱수는 $1^2,2^2,\dot 6.EE.A.3 규칙을 완전제곱수 $n=k^2$에 시험해 봅니다. 첫 번째 조작: $\lfloor\sqrt{k^2}\rfloor=k$이므로 $k$개를 제거하고 4.OA.C.5 두-조작 규칙을 반복 적용하며 완전제곱수의 밑이 매번 $1$씩 떨어지는 것을 봅니다: $10^2\to 9^2\to 8^2\to\cdots\to 검토
합리성 확인: 확실히 하기 위해 개수를 끝까지 곧장 흉내 냅니다: $100\to 90\to 81\to 72\to 64\to 56\to 49\to 42\to 36\to 30\to 25\to 20\to 16\to 12\to 9\to 6\to 4\to 2\to 1$. 화살표를 세면 $18$번의 조작이고, 모든 완전제곱수 값($81,64,49,36,25,16,9,4,1$)이 두-단계 규칙이 예측한 바로 그 자리에 나타납니다. 답 $18$은 선택지 사이에서도 합리적입니다: 순진한 추측은 $10$(시작 제곱수당 한 번)이나 $20$(제곱수 열 개에 대해 각각 두 번)일 수 있지만, 과정은 제곱수를 $9$번만 내린 뒤 $1^2$에서 끝나므로 $20$이 아니라 $18$이 맞습니다.
대안 접근: 제곱근 세기 대신, 남은 타일 수만 추적하며 그 개수 이하의 완전제곱수 개수를 반복해서 빼고 세어 나갑니다: $100,90,81,72,64,56,49,42,36,30,25,20,16,12,9,6,4,2,1$. $1$에 닿기까지 뺄셈이 $18$번 있습니다. 이 무차별 세기는 대수 없이도 패턴 답 $18$을 확인해 줍니다.
사용된 CCSS 표준 (최저 학년 8)
6.EE.A.1자연수 지수를 포함한 수식을 쓰고 계산하기 (완전제곱수 $1,4,9,\dots,100$을 알아보고 $100=10^2$, $81=9^2$을 제곱수로 읽어 개수가 줄어드는 것을 보는 데 사용.)8.EE.A.2제곱근·세제곱근 기호로 해를 나타내기 ($n$ 이하 완전제곱수의 개수를 매 조작에서 제거되는 타일 수 $\lfloor\sqrt{n}\rfloor$로 세는 데 사용.)6.EE.A.3연산의 성질을 적용하여 동치인 식 만들기 ($k^2-k-(k-1)=k^2-2k+1=(k-1)^2$을 정리하여 두 번의 조작이 $k^2$개 타일을 $(k-1)^2$개로 바꿈을 증명하는 데 사용.)4.OA.C.5주어진 규칙을 따르는 수 또는 도형 패턴 만들기 (제곱수 밑 패턴 $10^2\to 9^2\to\cdots\to 1^2$을 이어가며 $9\times 2=18$번의 조작을 세는 데 사용.)
⭐ 타일 개수만 중요하고, 매 두 번의 조작이 완전제곱수 개수를 한 칸씩 낮추므로, $10^2$개의 타일은 타일 하나에 도달하는 데 $9\times 2=18$번의 조작이 필요합니다.
⭐ 타일 개수만 중요하고, 매 두 번의 조작이 완전제곱수 개수를 한 칸씩 낮추므로, $10^2$개의 타일은 타일 하나에 도달하는 데 $9\times 2=18$번의 조작이 필요합니다.
비슷한 유형 더 풀어보기
같은 archetype · 비슷한 학년부터.