Difference between revisions of "2024 AMC 8 Problems/Problem 16"
Niuniumaths (talk | contribs) (→Video Solution 3 by SpreadTheMathLove) |
|||
| Line 15: | Line 15: | ||
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. | ||
| + | |||
| + | ==Solution== | ||
| + | |||
| + | For a row or column to have a product divisible by <math>3</math>, there must be a multiple of <math>3</math> in the row or column. To create the least amount of rows and columns with multiples of <math>3</math>, we must find a way to keep them all together, to minimize the total number of rows and columns. From <math>1</math> to <math>81</math>, there are <math>27</math> multiples of <math>3</math> (<math>81/3</math>). So we have to fill <math>27</math> cells with numbers that are multiples of <math>3</math>. If we put <math>25</math> of these numbers in a <math>5 x 5</math> grid, there would be <math>5</math> rows and <math>5</math> columns (<math>10</math> in total), with products divisible by <math>3</math>. However, we have <math>27</math> numbers, so <math>2</math> numbers remain to put in the <math>9 x 9</math> grid. If we put both numbers in the <math>6</math>th column, but one in the first row, and one in the second row, (next to the <math>5 x 5</math> already filled), we would have a total of <math>6</math> columns now, and still <math>5</math> rows with products that are multiples of <math>3</math>. So the answer is <math>\boxed{\textbf{(D)} 11}</math> | ||
| + | |||
- SahanWijetunga | - SahanWijetunga | ||
Revision as of 16:44, 27 January 2024
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)
(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 
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.
Solution
For a row or column to have a product divisible by , there must be a multiple of in the row or column. To create the least amount of rows and columns with multiples of , we must find a way to keep them all together, to minimize the total number of rows and columns. From to , there are multiples of (
). So we have to fill cells with numbers that are multiples of . If we put 
of these numbers in a 
grid, there would be 
rows and columns (
in total), with products divisible by . However, we have numbers, so 
numbers remain to put in the 
grid. If we put both numbers in the th column, but one in the first row, and one in the second row, (next to the already filled), we would have a total of columns now, and still rows with products that are multiples of . So the answer is 
- 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
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
See Also
| 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 | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
