AMC 8 · 2024 · #16
Grade 4 number-theoryProblem
Minh enters the numbers 1 through 81 into the cells of a 9×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?
Pick an answer.
AMC 8 2024 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
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
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
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
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.
💡 "A product is divisible by a prime exactly when one of the factors is" is the Grade 4 factors-and-multiples idea.
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$.
💡 $81 \div 3 = 27$ is exactly Grade 3 fluent multiplication and division within 100.
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$.
💡 Seeing $r$ rows and $c$ columns as forming an $r \times c$ rectangle of cells is the Grade 3 "area = rows × columns" idea.
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**.
💡 Multiplying $5 \times 5 = 25$ and comparing $25$ with $27$ is Grade 3 multiplication and comparison.
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$.
💡 Listing all integer pairs that sum to $11$, multiplying each, and comparing with $27$ is a Grade 4 multi-step problem-solving task.
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).
💡 Eliminating the smaller choices because they violate the factor/area condition and picking the smallest workable one is well within Grade 4 reasoning.
4.OA.B.4 Start with the key observation: a product of several whole numbers is divisible 3.OA.C.7 Next, count the multiples of $3$ between $1$ and $81$. They are $3, 6, 9, \ldots 3.MD.C.7 Reframe the problem in the easier form. Suppose the $27$ multiples of $3$ occupy 3.OA.C.7 Now Tool #6 — **guess and check** the small sums first. Try $r + c = 10$. For a 4.OA.A.3 Now try $r + c = 11$ and **list every** $(r,c)$ pair systematically: $(2,9), (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.7Fluently 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.7Relate 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.4Find 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.3Solve 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!
⭐ This AMC 8 problem only needs Grade 4 factors and multiples and multi-step problem solving you already know!
More like this
Same archetype — closest grade level first.
