Problem 16 · 2024 AMC 8
Hard
Counting & Probability
careful-countingdivisibility
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?
Show answer
Answer: D — 11 rows and columns.
Show hints
Hint 1 of 2
One multiple of 3 anywhere in a row makes that whole row's product divisible by 3 — same for its column. So a single bad number "poisons" a full row AND a full column. How do you poison as few lines as possible?
Still stuck? Show hint 2 →
Hint 2 of 2
Technique: count the multiples of 3 (there are 27 in 1–81) and pack them into an r×c block. That block fits r·c of them while poisoning r + c lines — minimize r + c with r·c ≥ 27.
Show solution
Approach: pack multiples of 3 into the tightest possible block
- A row or column's product is divisible by 3 the instant it holds even one multiple of 3. So each multiple-of-3 placement poisons one row and one column — the goal is to confine all of them to the fewest lines. There are 27 multiples of 3 in 1–81 (81÷3).
- Squeeze them into an r×c rectangle: it covers r·c cells and poisons exactly r + c lines. We need r·c ≥ 27 while making r + c small. A 5×5 block holds 25 — two short.
- Tuck the last 2 multiples into a 6th column (rows 1–2). Now rows poisoned: 5; columns poisoned: 6; total 5 + 6 = 11. (A 6×5 would also reach 30 cells and 11 lines — same minimum.)
- This transfers: for a fixed area r·c, the perimeter-like sum r + c is smallest when the rectangle is near-square — the same reason a square fences the most area for a given fence.
Mark:
· log in to save