Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 2)
(→‎Solution 2)
Line 14: Line 14:
  
 
If <math>ab=28</math>,our best is <math>a+b=7+4=11</math>. Note if <math>a+b=10</math>, then <math>ab\le 25</math>, and hence there is no smaller answer, and we get (D) 11.  
 
If <math>ab=28</math>,our best is <math>a+b=7+4=11</math>. Note if <math>a+b=10</math>, then <math>ab\le 25</math>, and hence there is no smaller answer, and we get (D) 11.  
 +
 
- SahanWijetunga
 
- SahanWijetunga
  

Revision as of 16:37, 26 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

These are just left here for future conveniency. 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 x 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 = (D) 11 -IwOwOwl253

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$ are and $a+b$ rows and columns divisible by $3$. We want $ab\ge 27$ and $ab$ 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

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 CosineMethod [🔥Fast and Easy🔥]

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AMC_8_Problems/Problem_16&oldid=213216"