AMC 8 · 2024 · #16

Grade 4 number-theory

Archetype Grid Tiling / Packing with Divisibility

divisibility-rulesmultiplesfactors optimization-countingsystematic-enumeration ↑ Prerequisites: factorsmultiplesdivisibility-rules

📏 Long solution 💡 4 insights

📘 View easy version →

Problem

Minh enters the numbers $1$ through $81$ into the cells of a $9 \times 9$ grid in some order. She calculates the product of the numbers in each row and column. What is the least number of rows and columns that could have a product divisible by $3$ ?

$\textbf{(A) } 8\qquad\textbf{(B) } 9\qquad\textbf{(C) } 10\qquad\textbf{(D) } 11\qquad\textbf{(E) } 12$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: Minh fills a $9 \times 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$.

Givens: A $9 \times 9$ grid (9 rows, 9 columns, 81 cells); The numbers $1, 2, 3, \ldots, 81$ are placed exactly once each; Answer choices: (A) 8, (B) 9, (C) 10, (D) 11, (E) 12

Unknowns: The **minimum** of (number of rows whose product is divisible by $3$) + (number of columns whose product is divisible by $3$)

Understand

Givens: A $9 \times 9$ grid (9 rows, 9 columns, 81 cells); The numbers $1, 2, 3, \ldots, 81$ are placed exactly once each; Answer choices: (A) 8, (B) 9, (C) 10, (D) 11, (E) 12

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #6 Guess and Check, #2 Make a Systematic List, #3 Eliminate Possibilities

The problem looks big ($9\times 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 \times c$ rectangle ($r,c \le 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.

Execute — Answer: D

#9 Solve an Easier Related Problem 4.OA.B.4 Step 1

Start with the key observation: a product of several whole numbers is divisible by $3$ if and only if **at least one of those numbers is a multiple of $3$**.
So a row's product is divisible by $3$ exactly when the row contains a multiple of $3$, and the same goes for columns.
Our job becomes: place the multiples of $3$ in the grid so that as few rows and columns as possible contain any of them.

$$\text{row product is divisible by } 3 \iff \text{the row contains at least one multiple of } 3$$

💡 "A product is divisible by a prime exactly when one of the factors is" is the Grade 4 factors-and-multiples idea.

#9 Solve an Easier Related Problem 3.OA.C.7 Step 2

Next, count the multiples of $3$ between $1$ and $81$.
They are $3, 6, 9, \ldots, 81$, and the largest one is $81 = 3 \times 27$, so there are $81 \div 3 = 27$ of them.
So exactly $27$ of the $81$ cells of the grid hold a multiple of $3$.

$$\text{number of multiples of } 3 = 81 \div 3 = 27$$

💡 $81 \div 3 = 27$ is exactly Grade 3 fluent multiplication and division within 100.

#9 Solve an Easier Related Problem 3.MD.C.7 Step 3

Reframe the problem in the easier form.
Suppose the $27$ multiples of $3$ occupy $r$ different rows and $c$ different columns.
Then all $27$ of those cells must lie inside the **$r \times c$ rectangle** formed by those rows and columns.
So that rectangle must have at least $27$ cells: $r \times c \ge 27$.
We just need to find positive integers $r, c \le 9$ minimizing $r + c$ subject to $r \times c \ge 27$.

$$r \times c \ge 27,\quad 1 \le r, c \le 9,\quad \text{minimize } r + c$$

💡 Seeing $r$ rows and $c$ columns as forming an $r \times c$ rectangle of cells is the Grade 3 "area = rows × columns" idea.

#6 Guess and Check 3.OA.C.7 Step 4

Now Tool #6 — **guess and check** the small sums first.
Try $r + c = 10$.
For a fixed sum the product $r \times c$ is largest when $r$ and $c$ are as close as possible, namely $r = c = 5$ giving $r \times c = 25 < 27$.
So no $(r,c)$ with $r+c \le 10$ can hold all $27$ multiples — sums $\le 10$ are **impossible**.

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

💡 Multiplying $5 \times 5 = 25$ and comparing $25$ with $27$ is Grade 3 multiplication and comparison.

#2 Make a Systematic List 4.OA.A.3 Step 5

Now try $r + c = 11$ and **list every** $(r,c)$ pair systematically: $(2,9), (3,8), (4,7), (5,6), (6,5), (7,4), (8,3), (9,2)$.
Their products are $18, 24, 28, 30, 30, 28, 24, 18$.
The ones with $r \times c \ge 27$ are $(4,7), (5,6), (6,5), (7,4)$.
For example a $5 \times 6 = 30$-cell rectangle has room for all $27$ multiples of $3$, so the configuration $r+c = 11$ is **actually achievable**: $5$ rows and $6$ columns are 'contaminated', total $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$$

💡 Listing all integer pairs that sum to $11$, multiplying each, and comparing with $27$ is a Grade 4 multi-step problem-solving task.

#3 Eliminate Possibilities 4.OA.B.4 Step 6

Finally, match $11$ to the answer choices and eliminate.
Choices (A) $8$, (B) $9$, (C) $10$ all need $r+c \le 10$, which Step 4 ruled out as impossible.
Choice (E) $12$ is achievable but larger than the $11$ we just realized, so it is not the minimum.
The minimum is $11$, which is choice (D).

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

💡 Eliminating the smaller choices because they violate the factor/area condition and picking the smallest workable one is well within Grade 4 reasoning.

[1] #9 4.OA.B.4 Start with the key observation: a product of several whole numbers is divisible

[2] #9 3.OA.C.7 Next, count the multiples of $3$ between $1$ and $81$. They are $3, 6, 9, \ldots

[3] #9 3.MD.C.7 Reframe the problem in the easier form. Suppose the $27$ multiples of $3$ occupy

[4] #6 3.OA.C.7 Now Tool #6 — **guess and check** the small sums first. Try $r + c = 10$. For a

[5] #2 4.OA.A.3 Now try $r + c = 11$ and **list every** $(r,c)$ pair systematically: $(2,9), (3,

[6] #3 4.OA.B.4 Finally, match $11$ to the answer choices and eliminate. Choices (A) $8$, (B) $9

Review

Reasonableness: Does $11$ make sense? The grid has $9 + 9 = 18$ rows-plus-columns total, so the answer is at most $18$, and $11 \le 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 27 / 9 \rceil = 3$ rows and similarly $3$ columns are needed: $r + c \ge 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 \times 6 = 30$-cell subgrid, place the $27$ multiples of $3$ there, and fill the remaining $54$ cells with the $54$ non-multiples of $3$.

Alternative: An alternative is Tool #16 (Change Focus / Complement): instead of counting contaminated rows and columns, maximize the number of $3$-clean rows ($9-r$) and $3$-clean columns ($9-c$) that contain only the $54$ non-multiples of $3$. That ends up at the same inequality $r \times c \ge 27$ and the same answer $11$, but our direct approach reaches it with fewer steps.

CCSS standards used (min grade 4)

3.OA.C.7 Fluently multiply and divide within 100 (Computing $81 \div 3 = 27$ to count multiples of $3$, and checking products like $5 \times 5 = 25$ and $5 \times 6 = 30$ against $27$.)
3.MD.C.7 Relate area to multiplication and addition operations (Recognizing that $r$ chosen rows and $c$ chosen columns form a rectangular subgrid of $r \times c$ cells that must hold all $27$ multiples.)
4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (Using the fact that a product is a multiple of $3$ iff a factor is, and eliminating answer choices that violate this condition.)
4.OA.A.3 Solve multi-step word problems using four operations with whole numbers (Listing every $(r,c)$ pair summing to $11$, multiplying each pair, comparing with $27$, and deciding which configurations are achievable.)

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

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: D

Review

CCSS standards used (min grade 4)

More like this