← Sensim Lab Sensim Math

AMC 8 · 2024 · #16

Easy mode Grade 4
📗 View original problem →

Problem

Picture a 9×99 \times 9 grid of empty squares. Minh writes the numbers 1,2,3,…,811, 2, 3, \dots, 81 inside the squares, putting one number in each square. She can choose the order however she likes.

After filling the grid, she looks at each row and multiplies all 99 numbers in that row together. She does the same for each column. So she ends up with 99 row-products and 99 column-products, 1818 products in total.

Some of these products will be divisible by 33. Minh wants to arrange the numbers so that as few of these 1818 products as possible are divisible by 33.

What is the smallest number of products that can be divisible by 33?

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

Pick an answer.

(A)
8
(B)
9
(C)
10
(D)
11
(E)
12
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

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

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

⭐ 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.