AMC 8 · 2024 · #16

학년 4 number-theory

유형 Grid Tiling / Packing with Divisibility └ 세부 유형 Divisibility-Selected Items — Minimize Bounding Footprint

divisibility-rulesmultiplesfactors optimization-countingsystematic-enumeration ↑ 선수 지식: factorsmultiplesdivisibility-rules

📏 긴 풀이 💡 4 개 인사이트

📘 쉬운 버전 보기 →

문제

민서는 $9 \times 9$ 격자의 각 칸에 $1$ 부터 $81$ 까지의 수를 임의의 순서로 한 번씩 적어 넣었습니다. 그런 다음 각 행과 각 열에 있는 수들의 곱을 계산했습니다. 곱이 $3$ 으로 나누어떨어지는 행과 열의 개수의 합의 최솟값은 얼마입니까?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 8 2024 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 민서가 $1$부터 $81$까지의 수를 $9 \times 9$ 격자에 한 칸씩 채워 넣습니다. 각 행과 각 열의 곱을 구할 때, 그 곱이 $3$으로 나누어떨어지는 **행과 열의 개수의 합**을 가능한 한 **작게** 만들려면 그 합은 최소 몇 개여야 하는지를 묻는 문제입니다.

주어진 것: $9 \times 9$ 격자(가로 9칸, 세로 9칸, 총 81칸)에 $1$부터 $81$까지의 수를 한 번씩 모두 적는다; 각 행의 곱과 각 열의 곱을 계산한다; 선택지: (A) 8, (B) 9, (C) 10, (D) 11, (E) 12

구하는 것: 곱이 $3$의 배수가 되는 행의 개수와 열의 개수의 합의 **최솟값**

이해

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #6 추측하고 확인하기, #2 빠짐없이 나열하기, #3 가능성 지우기

이 문제는 "$9\times 9$ 격자", "$1$부터 $81$" 같이 큰 수가 등장하지만, 핵심 아이디어는 두 가지뿐입니다: **"줄에 $3$의 배수가 하나라도 있으면 그 줄의 곱은 $3$의 배수"** 라는 사실과, **"$3$의 배수들이 차지하는 행 $r$개·열 $c$개를 작게 하려면 그 $3$의 배수들을 작은 직사각형 안에 몰아 넣어야 한다"** 는 사실입니다. 그래서 도구 #9로 문제를 "$3$의 배수 $27$개를 한 직사각형 ($r \times c$) 안에 넣을 때 $r+c$를 가장 작게"라는 더 쉬운 문제로 바꿉니다. 그 다음 도구 #6으로 $r+c=10, 11, 12$를 차례로 시험하고, 도구 #2로 가능한 $(r,c)$ 쌍을 빠짐없이 나열한 뒤, 도구 #3으로 선택지 중 답을 골라냅니다.

실행 — 정답: D

#9 더 쉬운 문제로 줄이기 4.OA.B.4 단계 1

먼저 가장 중요한 관찰부터 합니다: 여러 수의 곱이 $3$의 배수가 되는 것은 그 수들 중 **적어도 하나가 $3$의 배수**일 때 그리고 그때뿐입니다.
그러니 한 행의 곱이 $3$의 배수인지 아닌지는 오직 "그 행에 $3$의 배수가 들어 있는가?"로 결정됩니다.
열도 마찬가지입니다.
따라서 우리는 "$3$의 배수가 들어 있는 행의 개수 + $3$의 배수가 들어 있는 열의 개수"를 최소화하면 됩니다.

$$\text{행의 곱이 } 3 \text{의 배수} \iff \text{그 행에 } 3 \text{의 배수가 적어도 하나 있다}$$

💡 "여러 수의 곱이 어떤 소수로 나누어떨어지려면 그 인수들 중 하나가 그 소수여야 한다"는 것은 4학년에서 배우는 약수·배수의 기본 개념입니다.

#9 더 쉬운 문제로 줄이기 3.OA.C.7 단계 2

다음으로 $1$부터 $81$ 사이에 $3$의 배수가 몇 개인지 셉니다.
$3$의 배수는 $3, 6, 9, \ldots, 81$이고, 가장 큰 것이 $81 = 3 \times 27$이므로 그 개수는 $81 \div 3 = 27$개입니다.
그러니 격자 $81$칸 가운데 정확히 $27$칸에 $3$의 배수가 놓이게 됩니다.

$$3 \text{의 배수 개수} = 81 \div 3 = 27$$

💡 $81 \div 3 = 27$ 은 $100$ 이내의 곱셈·나눗셈을 척척 해내는 3학년 단원에 해당합니다.

#9 더 쉬운 문제로 줄이기 3.MD.C.7 단계 3

이제 문제를 더 쉬운 모양으로 바꿉니다.
$3$의 배수 $27$개가 들어 있는 "행들"의 개수를 $r$, "열들"의 개수를 $c$라고 하면, 이 $27$개 칸은 모두 그 $r$개의 행과 $c$개의 열이 만드는 **$r \times c$ 직사각형 안**에 있어야 합니다.
그러므로 그 직사각형의 칸 수 $r \times c$ 는 적어도 $27$이어야 합니다.
즉 우리는 $r, c \le 9$인 자연수에 대해 $r \times c \ge 27$ 이면서 $r + c$ 가 가장 작은 경우를 찾으면 됩니다.

$$r \times c \ge 27,\quad 1 \le r, c \le 9,\quad \text{최솟값 } r + c = ?$$

💡 $r$개의 행과 $c$개의 열이 만드는 격자가 $r \times c$ 칸이라는 것은 3학년의 "직사각형의 넓이 = 가로 × 세로" 개념입니다.

#6 추측하고 확인하기 3.OA.C.7 단계 4

이제 도구 #6 — 작은 합부터 차례로 **추측하고 확인**합니다.
$r+c$ 의 합이 작을수록 좋으니 $r+c=10$ 부터 시도합니다.
합이 $10$일 때 $r \times c$ 가 가장 커지는 것은 두 수가 가까울 때 ($r=c=5$) 이며, 이때 $r \times c = 25 < 27$.
그러므로 합이 $10$ 이하인 경우는 $27$개의 칸을 담을 수 없어 **불가능**합니다.

$$r+c = 10 \;\Rightarrow\; \max(r \times c) = 5 \times 5 = 25 < 27$$

💡 $5 \times 5 = 25$ 와 $25$ 가 $27$ 보다 작은지 비교하는 일은 3학년의 곱셈·비교 능력으로 충분합니다.

#2 빠짐없이 나열하기 4.OA.A.3 단계 5

다음으로 $r+c = 11$ 을 시도하고, 합이 $11$이 되는 $(r,c)$ 쌍을 **빠짐없이 나열**합니다: $(2,9), (3,8), (4,7), (5,6), (6,5), (7,4), (8,3), (9,2)$.
각각의 곱은 $18, 24, 28, 30, 30, 28, 24, 18$ 입니다.
이 중 $r \times c \ge 27$ 인 것은 $(4,7), (5,6), (6,5), (7,4)$ 로, 예를 들어 $5$개의 행과 $6$개의 열이 만드는 $5 \times 6 = 30$ 칸의 직사각형 안에 $3$의 배수 $27$개를 모두 넣을 수 있습니다.
그러니 $r+c = 11$은 **실제로 가능**하며, 그때 곱이 $3$의 배수가 되는 행과 열의 총합은 $5 + 6 = 11$ 입니다.

$$r+c = 11:\ (4,7) \to 28,\ (5,6) \to 30,\ (6,5) \to 30,\ (7,4) \to 28 \;\ge\; 27 \checkmark$$

💡 합이 $11$이 되는 자연수 쌍을 모두 적고 각각의 곱과 $27$을 비교해 조건을 만족하는 것을 찾는 일은 4학년의 여러 단계 문제 해결에 해당합니다.

#3 가능성 지우기 4.OA.B.4 단계 6

마지막으로 $11$이 선택지에 있는지 확인합니다.
보기 (A) $8$, (B) $9$, (C) $10$ 은 모두 $r+c \le 10$ 이라 4단계에서 보인 대로 $r \times c \le 25 < 27$ 이므로 **불가능**해 지워집니다.
(E) $12$ 도 가능하지만 우리는 더 작은 값 $11$ 을 이미 만들었으므로 답이 아닙니다.
따라서 정답은 (D) $11$ 입니다.

$$\min(r+c) = 11 \;\Rightarrow\; \textbf{(D)}$$

💡 더 작은 보기들이 약수·곱셈 조건을 만족하지 못한다는 사실로 후보를 지우고 답을 고르는 일은 4학년 수준에서 자연스럽게 할 수 있습니다.

[1] #9 4.OA.B.4 먼저 가장 중요한 관찰부터 합니다: 여러 수의 곱이 $3$의 배수가 되는 것은 그 수들 중 **적어도 하나가 $3$의 배수**일 때 그리고 그때

[2] #9 3.OA.C.7 다음으로 $1$부터 $81$ 사이에 $3$의 배수가 몇 개인지 셉니다. $3$의 배수는 $3, 6, 9, \ldots, 81$이고, 가장 큰 것

[3] #9 3.MD.C.7 이제 문제를 더 쉬운 모양으로 바꿉니다. $3$의 배수 $27$개가 들어 있는 "행들"의 개수를 $r$, "열들"의 개수를 $c$라고 하면, 이

[4] #6 3.OA.C.7 이제 도구 #6 — 작은 합부터 차례로 **추측하고 확인**합니다. $r+c$ 의 합이 작을수록 좋으니 $r+c=10$ 부터 시도합니다. 합이

[5] #2 4.OA.A.3 다음으로 $r+c = 11$ 을 시도하고, 합이 $11$이 되는 $(r,c)$ 쌍을 **빠짐없이 나열**합니다: $(2,9), (3,8), (4

[6] #3 4.OA.B.4 마지막으로 $11$이 선택지에 있는지 확인합니다. 보기 (A) $8$, (B) $9$, (C) $10$ 은 모두 $r+c \le 10$ 이라 4

검토

합리성 확인: 구한 답 $11$ 의 합리성을 확인해 봅시다. $9\times 9$ 격자에는 $9$개의 행과 $9$개의 열이 있어 곱이 $3$의 배수가 되는 줄의 수는 최대 $9 + 9 = 18$이고, 답 $11$은 그 안에 있어 크기가 합리적입니다. 또 $3$의 배수가 $27$개나 되므로 한두 줄에 다 몰아넣을 수 없고($9$칸짜리 한 줄에는 최대 $9$개만 들어감), 적어도 $\lceil 27/9 \rceil = 3$개의 행과 $3$개의 열이 필요합니다 — 즉 $r+c \ge 6$. 따라서 $11$은 "너무 작지도, 너무 크지도" 않습니다. 실제 구성 예시: $5\times 6$ 부분 격자 ($30$칸) 안의 어느 $27$칸을 골라 $3$의 배수를 넣고 나머지 $54$칸에는 $3$의 배수가 아닌 $54$개의 수를 넣으면 됩니다.

대안 접근: 다른 방법으로는 도구 #16(관점 바꾸기 / 여집합)을 써서 "곱이 $3$의 배수가 **아닌** 행과 열의 개수의 합을 가장 크게"로 바꿔 풀 수도 있습니다. 그러면 "$3$의 배수가 아닌 수($54$개)들이 통째로 차지하는 행 $9-r$개, 열 $9-c$개"의 합을 최대화하는 같은 모양의 문제가 되고, 결국 같은 부등식 $r \times c \ge 27$ 에 도달해 답 $11$ 을 얻습니다. 다만 본 풀이가 더 직접적이고, 같은 답을 더 적은 단계로 보여 줍니다.

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

3.OA.C.7 100 이내의 곱셈과 나눗셈을 능숙하게 한다 ($81 \div 3 = 27$ 로 $1$~$81$ 안의 $3$의 배수 개수를 세고, $5 \times 5 = 25$, $5 \times 6 = 30$ 같은 곱셈을 빠르게 확인하는 데 사용.)
3.MD.C.7 넓이를 곱셈·덧셈과 연결한다 ($r$개의 행과 $c$개의 열이 만드는 직사각형 부분 격자의 칸 수가 $r \times c$ 라는 것을 인식하는 데 사용.)
4.OA.B.4 약수의 쌍을 모두 찾고 배수를 인식하며 소수·합성수를 판별한다 ("곱이 $3$의 배수가 되려면 인수 중 하나가 $3$의 배수여야 한다"는 약수·배수 사실과, 작은 보기들을 지워 답을 고르는 데 사용.)
4.OA.A.3 사칙 연산을 사용해 여러 단계의 문장제를 푼다 ($r+c=11$이 되는 $(r,c)$ 쌍을 나열하고 각 곱과 $27$ 을 비교해 가능한 배치를 결정하는 데 사용.)

⭐ 이 AMC 8 문제는 사실 4학년 때 배운 약수·배수와 여러 단계 문제 해결만 알면 풀려요!

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: D

검토

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

비슷한 유형 더 풀어보기