Competition · AMC preparation · step 4 of 4

AMC 8 · 2024 · #16

Grade 4 number-theory
Archetype Grid Tiling / Packing with Divisibility └ Sub-archetype Divisibility-Selected Items — Minimize Bounding Footprint
divisibility-rulesmultiplesfactors optimization-countingsystematic-enumeration ↑ Prerequisites: factorsmultiplesdivisibility-rules
📏 Long solution 💡 4 insights
📘 View easy version →
Problem
Minh fills a 9 × 9 grid with the numbers 1 through 81, one per cell. She computes the product of the numbers in each row and the product in each column. We want the smallest possible total number of rows-plus-columns whose product is divisible by 3.

Pick an answer.

(A)
8
(B)
9
(C)
10
(D)
11
(E)
12

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

How to solve
Strategy Solve an Easier Related Problem

The problem looks big (9 × 9 grid, numbers 1 to 81), but the heart of it is only two ideas: a product is divisible by 3 iff at least one factor is a multiple of 3, and to make few rows and columns "contaminated" by the multiples of 3, you should pack all of those multiples into a small rectangle. Tool #9 reduces the original puzzle to the easier question: "put 27 stones inside an r × c rectangle (r,c ≤ 9); minimize r+c." Then Tool #6 tests small candidate sums r+c = 10, 11, 12, Tool #2 lists the (r,c) pairs for each sum, and Tool #3 eliminates choices to pinpoint the answer.

1STEP 1

State when a product is divisible by 3

A product is divisible by 3 exactly when it contains at least one multiple of 3 — so a row or column counts only if it holds one.

row product is divisible by 3 ⇔ the row contains at least one multiple of 3
2STEP 2

Count the multiples of 3

Between 1 and 81 the multiples of 3 are 3, 6, …, 81, so there are 81 ÷ 3 = 27 of them to place in the grid.

number of multiples of 3 = 81 ÷ 3 = 27
3STEP 3

Restate it as rows times columns

If the 27 multiples touch r rows and c columns, they must all fit in that r × c rectangle, so r × c ≥ 27 with r, c ≤ 9 — minimize r + c.

r × c ≥ 27, 1 ≤ r, c ≤ 9, minimize r + c
4STEP 4

Rule out a sum of 10

Guess-and-check the smallest sum: r + c = 10 peaks at 5 × 5 = 25 ＜ 27, so no sum of 10 or less can hold all 27.

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

Test a sum of 11

For r + c = 11 the pair (5,6) gives 5 × 6 = 30 ≥ 27, so all 27 multiples fit and a sum of 11 is achievable.

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

Match against the choices

Choices 8, 9, 10 all need r + c ≤ 10 (ruled out) and 12 overshoots, so the minimum is 11, choice (D).

min(r+c) = 11 → (D)
Answer
11
Does 11 make sense? The grid has 9 + 9 = 18 rows-plus-columns total, so the answer is at most 18, and 11 ≤ 18. On the low end, 27 multiples of 3 cannot all fit in only one or two rows (a row holds at most 9), so at least ⌈279⌉\lceil \frac{27}{9} \rceil = 3 rows and similarly 3 columns are needed: r + c ≥ 6. So 11 is comfortably between the rough lower bound 6 and the upper bound 18. A concrete construction: pick any 27 cells within a 5 × 6 = 30-cell subgrid, place the 27 multiples of 3 there, and fill the remaining 54 cells with the 54 non-multiples of 3.
💡Key takeaway

This AMC 8 problem only needs Grade 4 factors and multiples and multi-step problem solving you already know!

  • State when a product is divisible by 3
  • Count the multiples of 3
  • Restate it as rows times columns
  • Rule out a sum of 10
  • Test a sum of 11
  • Match against the choices

A parent dashboard for the family lives at sensimlab.com.

More like this

Same problem type. Tags show what each one shares with this problem.