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)

(B)

(C)

(D)

(E)

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

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

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

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

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

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

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

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

\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!

More like this