Difference between revisions of "2024 AMC 8 Problems/Problem 16"

Revision as of 17:19, 28 January 2024

Problem 16

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$ ?

Solution

We know that if a row/column of numbers has a single multiple of $3$ , that entire row/column will be divisible by $3$ . Since there are $27$ multiples of $3$ from $1$ to $81$ , We need to find a way to place the $54$ non-multiples of $3$ such that they take up as many entire rows and columns as possible. If we naively put in non-multiples of $3$ in $6$ rows from the top, we get $18 - 6 = 12$ rows that are multiples of $3$ . However, we can improve this number by making some rows and columns intersect so that some squares help fill out both rows and columns We see that filling $7$ rows/columns would usually take $7 \times 9 = 63$ of our non-multiples, but if we do $4$ rows and $3$ columns, $12$ will intersect. With our $54$ being enough as we need only $51$ non-multiples of $3$ ( $63$ minus the $12$ overlapped). We check to see if we can fill out one more row/column, and when that fails we conclude the final answer to be $18 - 7 = \boxed{\textbf{(D)} 11}$ -IwOwOwl253 ~andliu766(Minor edits) (If someone would add a diagram that would be greatly appreciated)

Solution 2

Note you can swap/rotate any configuration of rows, such that all the rows and columns that have a product of 3 are in the top left. Hence the points are bounded by a $a \times b$ rectangle. This has $ab$ area and $a+b$ rows and columns divisible by $3$ . We want $ab\ge 27$ and $a+b$ minimized.

If $ab=27$ , we achieve minimum with $a+b=9+3=12$ .

If $ab=28$ ,our best is $a+b=7+4=11$ . Note if $a+b=10$ , then $ab\le 25$ , and hence there is no smaller answer, and we get (D) 11.

- SahanWijetunga

Solution 3

For a row or column to have a product divisible by $3$ , there must be a multiple of $3$ in the row or column. To create the least amount of rows and columns with multiples of $3$ , we must find a way to keep them all together, to minimize the total number of rows and columns. From $1$ to $81$ , there are $27$ multiples of $3$ ( $81/3$ ). So we have to fill $27$ cells with numbers that are multiples of $3$ . If we put $25$ of these numbers in a $5 x 5$ grid, there would be $5$ rows and $5$ columns ( $10$ in total), with products divisible by $3$ . However, we have $27$ numbers, so $2$ numbers remain to put in the $9 x 9$ grid. If we put both numbers in the $6$ th column, but one in the first row, and one in the second row, (next to the $5 x 5$ already filled), we would have a total of $6$ columns now, and still $5$ rows with products that are multiples of $3$ . So the answer is $\boxed{\textbf{(D)} 11}$

~goofytaipan

Video Solution 1 (easy to digest) by Power Solve

https://youtu.be/zxkL4c316vg

Video Solution 2 by OmegaLearn.org

https://youtu.be/xfiPVmuMiXs

Video Solution 3 by SpreadTheMathLove

https://www.youtube.com/watch?v=Svibu3nKB7E

Video Solution by NiuniuMaths (Easy to understand!)

https://www.youtube.com/watch?v=V-xN8Njd_Lc

~NiuniuMaths

Video Solution by CosineMethod [🔥Fast and Easy🔥]

https://www.youtube.com/watch?v=DLzFB4EplKk

@@ Line 4: / Line 4: @@
 ==Solution==
-<asy>
-usepackage("mathptmx");
-defaultpen(linewidth(0.5));
-size(5cm);
-defaultpen(fontsize(14pt));
-filldraw((1,2)--(2,1)--(3,2)--(4,1)--(5,2)--(4,3)--(5,4)--(4,5)--(3,4)--(2,5)--(1,4)--(2,3)--(1,2)--cycle,5);
-draw((0,0)--(6,0), gray);
-draw((0,1)--(6,1), gray);
-draw((0,2)--(6,2), gray);
-draw((0,3)--(6,3), gray);
-draw((0,4)--(6,4), gray);
-draw((0,5)--(6,5), gray);
-draw((0,6)--(6,6), gray);
-draw((0,0)--(0,6), gray);
-draw((1,0)--(1,6), gray);
-draw((2,0)--(2,6), gray);
-draw((3,0)--(3,6), gray);
-draw((4,0)--(4,6), gray);
-draw((5,0)--(5,6), gray);
-draw((6,0)--(6,6), gray);
-</asy>
 We know that if a row/column of numbers has a single multiple of <math>3</math>, that entire row/column will be divisible by <math>3</math>. Since there are <math>27</math> multiples of <math>3</math> from <math>1</math> to <math>81</math>, We need to find a way to place the <math>54</math> non-multiples of <math>3</math> such that they take up as many entire rows and columns as possible.

2024 AMC 8 (Problems • Answer Key • Resources)
Preceded by Problem 15	Followed by Problem 17
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AJHSME/AMC 8 Problems and Solutions

Page

Toolbox

Search