Difference between revisions of "2024 AMC 8 Problems/Problem 16"
(→Solution 2) |
|||
| Line 8: | Line 8: | ||
We see that filling <math>7</math> rows/columns would usually take <math>7 \times 9 = 63</math> of our non-multiples, but if we do <math>4</math> rows and <math>3</math> columns, <math>12</math> will intersect. With our <math>54</math> being enough as we need only <math>51</math> non-multiples of <math>3</math>(<math>63</math> minus the <math>12</math> 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 <math>18 - 7 = \boxed{\textbf{(D)} 11}</math> -IwOwOwl253 ~andliu766(Minor edits) | We see that filling <math>7</math> rows/columns would usually take <math>7 \times 9 = 63</math> of our non-multiples, but if we do <math>4</math> rows and <math>3</math> columns, <math>12</math> will intersect. With our <math>54</math> being enough as we need only <math>51</math> non-multiples of <math>3</math>(<math>63</math> minus the <math>12</math> 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 <math>18 - 7 = \boxed{\textbf{(D)} 11}</math> -IwOwOwl253 ~andliu766(Minor edits) | ||
==Solution 2== | ==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 <math>a \times b</math> rectangle. This has <math>ab</math> | + | 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 <math>a \times b</math> rectangle. This has <math>ab</math> area and <math>a+b</math> rows and columns divisible by <math>3</math>. We want <math>ab\ge 27</math> and <math>a+b</math> minimized. |
If <math>ab=27</math>, we achieve minimum with <math>a+b=9+3=12</math>. | If <math>ab=27</math>, we achieve minimum with <math>a+b=9+3=12</math>. | ||
Revision as of 17:16, 26 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)
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
