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 개 인사이트

📘 쉬운 버전 보기 →

문제

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

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 더 쉬운 문제로 줄이기

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

1STEP 1

곱이 3의 배수가 되는 건 그 안에 3의 배수가 하나라도 있을 때뿐 — 그래서 그런 수가 든 행·열만 셉니다.

행의 곱이 3 의 배수 ⇔ 그 행에 3 의 배수가 적어도 하나 있다

2STEP 2

1부터 81 사이의 3의 배수는 3, 6, …, 81, 즉 81 ÷ 3 = 27개를 격자에 놓아야 합니다.

3 의 배수 개수 = 81 ÷ 3 = 27

3STEP 3

27개가 걸친 행·열이 r × c 직사각형을 이루니 다 담으려면 r × c ≥ 27 (r, c ≤ 9).

r × c ≥ 27, 1 ≤ r, c ≤ 9, 최솟값 r + c = ?

4STEP 4

작은 합부터 확인합니다: r + c = 10 은 5 × 5 = 25 ＜ 27 이 최대라, 합이 10 이하면 27개를 담을 수 없습니다.

r+c = 10 → max(r × c) = 5 × 5 = 25 ＜ 27

5STEP 5

r + c = 11 의 쌍 (5,6)은 5 × 6 = 30 ≥ 27 이라 27개가 모두 들어가, 합 11이 실제로 가능합니다.

r+c = 11: (4,7) → 28, (5,6) → 30, (6,5) → 30, (7,4) → 28 ≥ 27 ✓

6STEP 6

보기 8, 9, 10 은 r + c ≤ 10 이라 불가능하고 12 는 과하니, 최솟값은 11, 곧 (D)입니다.

min(r+c) = 11 → (D)

정답

구한 답 11 의 합리성을 확인해 봅시다. 9× 9 격자에는 9개의 행과 9개의 열이 있어 곱이 3의 배수가 되는 줄의 수는 최대 9 + 9 = 18이고, 답 11은 그 안에 있어 크기가 합리적입니다. 또 3의 배수가 27개나 되므로 한두 줄에 다 몰아넣을 수 없고(9칸짜리 한 줄에는 최대 9개만 들어감), 적어도

\lceil \frac{27}{9} \rceil

= 3개의 행과 3개의 열이 필요합니다 — 즉 r+c ≥ 6. 따라서 11은 "너무 작지도, 너무 크지도" 않습니다. 실제 구성 예시: 5× 6 부분 격자 (30칸) 안의 어느 27칸을 골라 3의 배수를 넣고 나머지 54칸에는 3의 배수가 아닌 54개의 수를 넣으면 됩니다.

💡핵심 정리

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

비슷한 유형 더 풀어보기