2024 AMC 8 Problems/Problem 16

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)

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.