2024 AMC 8 Problems/Problem 16
Contents
Problem 16
Minh enters the numbers through into the cells of a 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 ?
Solution
We know that if a row/column of numbers has a single multiple of , that entire row/column will be divisible by . Since there are multiples of from to , We need to find a way to place the non-multiples of such that they take up as many entire rows and columns as possible. If we naively put in non-multiples of in rows from the top, we get rows that are multiples of . 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 rows/columns would usually take of our non-multiples, but if we do rows and columns, will intersect. With our being enough as we need only non-multiples of ( minus the 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 -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 rectangle. This has area and rows and columns divisible by . We want and minimized.
If , we achieve minimum with .
If ,our best is . Note if , then , and hence there is no smaller answer, and we get (D) 11.
- SahanWijetunga
Video Solution 1 (easy to digest) by Power Solve
Video Solution 2 by OmegaLearn.org
Video Solution 3 by SpreadTheMathLove
https://www.youtube.com/watch?v=Svibu3nKB7E