Difference between revisions of "2020 AIME II Problems/Problem 12"

(Solution)
(Solution 2 (Official MAA))
(20 intermediate revisions by 8 users not shown)
Line 1: Line 1:
Let <math>m</math> and <math>n</math> be odd integers greater than <math>1.</math> An <math>m\times n</math> rectangle is made up of unit squares where the squares in the top row are numbered left to right with the integers <math>1</math> through <math>n</math>, those in the second row are numbered left to right with the integers <math>n + 1</math> through <math>2n</math>, and so on. Square <math>200</math> is in the top row, and square <math>2000</math> is in the bottom row. Find the number of ordered pairs <math>(m,n)</math> of odd integers greater than <math>1</math> with the property that, in the <math>m\times n</math> rectangle, the line through the centers of squares <math>200</math> and <math>2000</math> intersects the interior of square <math>1099</math>
+
==Problem==
 +
Let <math>m</math> and <math>n</math> be odd integers greater than <math>1.</math> An <math>m\times n</math> rectangle is made up of unit squares where the squares in the top row are numbered left to right with the integers <math>1</math> through <math>n</math>, those in the second row are numbered left to right with the integers <math>n + 1</math> through <math>2n</math>, and so on. Square <math>200</math> is in the top row, and square <math>2000</math> is in the bottom row. Find the number of ordered pairs <math>(m,n)</math> of odd integers greater than <math>1</math> with the property that, in the <math>m\times n</math> rectangle, the line through the centers of squares <math>200</math> and <math>2000</math> intersects the interior of square <math>1099</math>.
  
 
==Solution==
 
==Solution==
Let us take some cases. Since m and n are odds, and 200 is in the top row and 2000 in the bottom, m has to be 3, 5, 7 or 9. Also, taking a look at the diagram, the slope of the line connecting those centers has to have an absolute value of<math> < 1</math>. Therefore, <math>m < 1800 mod n < 1800-m</math>.  
+
Let us take some cases. Since <math>m</math> and <math>n</math> are odds, and <math>200</math> is in the top row and <math>2000</math> in the bottom, <math>m</math> has to be <math>3</math>, <math>5</math>, <math>7</math>, or <math>9</math>. Also, taking a look at the diagram, the slope of the line connecting those centers has to have an absolute value of <math> < 1</math>. Therefore, <math>m < 1800 \mod n < 1800-m</math>.  
  
If m is 3, n can be from 667 to 999. However, 900 divides 1800, so looking at mods, we can easily eliminate 899 and 901. Now, counting these odd integers, we get <math>167 - 2 = 165</math>.
+
If <math>m=3</math>, <math>n</math> can range from <math>667</math> to <math>999</math>. However, <math>900</math> divides <math>1800</math>, so looking at mods, we can easily eliminate <math>899</math> and <math>901</math>. Now, counting these odd integers, we get <math>167 - 2 = 165</math>.
  
Similarly, let m be 5. Then n can range from 401 to 499. However, 450 divides 1800, so one can remove 449 and 451. Counting odd integers, we get <math>50 - 2 = 48</math>.
+
Similarly, let <math>m=5</math>. Then <math>n</math> can range from <math>401</math> to <math>499</math>. However, <math>450|1800</math>, so one can remove <math>449</math> and <math>451</math>. Counting odd integers, we get <math>50 - 2 = 48</math>.
  
Take m as 7. Then, n can range from 287 to 333. However, 300 divides 1800, so one can verify and eliminate 299 and 301. Counting odd integers, we get <math>24 - 2 = 22</math>.
+
Take <math>m=7</math>. Then, <math>n</math> can range from <math>287</math> to <math>333</math>. However, <math>300|1800</math>, so one can verify and eliminate <math>299</math> and <math>301</math>. Counting odd integers, we get <math>24 - 2 = 22</math>.
  
Let m be 9. Then n can vary from 223 to 249. However, 225 divides 1800. Checking that value and the values around it, we can eliminate 225. Counting odd integers, we get <math>14 - 1 = 13</math>.
+
Let <math>m = 9</math>. Then <math>n</math> can vary from <math>223</math> to <math>249</math>. However, <math>225|1800</math>. Checking that value and the values around it, we can eliminate <math>225</math>. Counting odd integers, we get <math>14 - 1 = 13</math>.
  
 
Add all of our cases to get <cmath> 165+48+22+13 = \boxed{248} </cmath>
 
Add all of our cases to get <cmath> 165+48+22+13 = \boxed{248} </cmath>
  
 
-Solution by thanosaops
 
-Solution by thanosaops
 +
 +
==Solution 2 (Official MAA)==
 +
Because square <math>2000</math> is in the bottom row, it follows that <math>\frac{2000}m \le n < \frac{2000}{m-1}</math>. Moreover, because square <math>200</math> is in the top row, and square <math>2000</math> is not in the top row, <math>1 < m \le 10</math>. In particular, because the number of rows in the rectangle must be odd, <math>m</math> must be one of <math>3, 5, 7,</math> or <math>9.</math>
 +
 +
For each possible choice of <math>m</math> and <math>n</math>, let <math>\ell_{m,n}</math> denote the line through the centers of squares <math>200</math> and <math>2000.</math> Note that for odd values of <math>m</math>, the line <math>\ell_{m,n}</math> passes through the center of square <math>1100.</math> Thus <math>\ell_{m,n}</math> intersects the interior of cell <math>1099</math> exactly when its slope is strictly between <math>-1</math> and <math>1</math>. The line <math>\ell_{m,n}</math> is vertical whenever square <math>2000</math> is the <math>200</math>th square in the bottom row of the rectangle. This would happen for <math>m = 3, 5, 7, 9</math> when <math>n = 900, 450, 300, 225</math>, respectively. When <math>n</math> is 1 greater than or 1 less than these numbers, the slope of <math>\ell_{m,n}</math> is <math>1</math> or <math>-1</math>, respectively. In all other cases the slope is strictly between <math>-1</math> and <math>1.</math> The admissible values for <math>n</math> for each possible value of <math>m</math> are given in the following table.
 +
<cmath>\begin{tabular}{|c|c|c|c|c|}\hline
 +
m & minimum n & maximum n & avoided n & number of odd n\\\hline
 +
3&667&999&899, 900, 901&165\\\hline
 +
5&400&499&449, 450, 451&48\\\hline
 +
7&286&333&299, 300, 301&22\\\hline
 +
9&223&249&224, 225, 226&13\\\hline
 +
\end{tabular}</cmath>
 +
This accounts for <math>165 + 48 + 22 + 13 = 248</math> rectangles.
 +
 +
==Video Solution 1==
 +
https://www.youtube.com/watch?v=MrtKoO16XLQ ~ MathEx
 +
 +
==Video Solution 2==
 +
https://youtu.be/v58SLOoAKTw
 +
 +
==See Also==
 +
{{AIME box|year=2020|n=II|num-b=11|num-a=13}}
 +
{{MAA Notice}}

Revision as of 02:19, 18 February 2021

Problem

Let $m$ and $n$ be odd integers greater than $1.$ An $m\times n$ rectangle is made up of unit squares where the squares in the top row are numbered left to right with the integers $1$ through $n$, those in the second row are numbered left to right with the integers $n + 1$ through $2n$, and so on. Square $200$ is in the top row, and square $2000$ is in the bottom row. Find the number of ordered pairs $(m,n)$ of odd integers greater than $1$ with the property that, in the $m\times n$ rectangle, the line through the centers of squares $200$ and $2000$ intersects the interior of square $1099$.

Solution

Let us take some cases. Since $m$ and $n$ are odds, and $200$ is in the top row and $2000$ in the bottom, $m$ has to be $3$, $5$, $7$, or $9$. Also, taking a look at the diagram, the slope of the line connecting those centers has to have an absolute value of $< 1$. Therefore, $m < 1800 \mod n < 1800-m$.

If $m=3$, $n$ can range from $667$ to $999$. However, $900$ divides $1800$, so looking at mods, we can easily eliminate $899$ and $901$. Now, counting these odd integers, we get $167 - 2 = 165$.

Similarly, let $m=5$. Then $n$ can range from $401$ to $499$. However, $450|1800$, so one can remove $449$ and $451$. Counting odd integers, we get $50 - 2 = 48$.

Take $m=7$. Then, $n$ can range from $287$ to $333$. However, $300|1800$, so one can verify and eliminate $299$ and $301$. Counting odd integers, we get $24 - 2 = 22$.

Let $m = 9$. Then $n$ can vary from $223$ to $249$. However, $225|1800$. Checking that value and the values around it, we can eliminate $225$. Counting odd integers, we get $14 - 1 = 13$.

Add all of our cases to get \[165+48+22+13 = \boxed{248}\]

-Solution by thanosaops

Solution 2 (Official MAA)

Because square $2000$ is in the bottom row, it follows that $\frac{2000}m \le n < \frac{2000}{m-1}$. Moreover, because square $200$ is in the top row, and square $2000$ is not in the top row, $1 < m \le 10$. In particular, because the number of rows in the rectangle must be odd, $m$ must be one of $3, 5, 7,$ or $9.$

For each possible choice of $m$ and $n$, let $\ell_{m,n}$ denote the line through the centers of squares $200$ and $2000.$ Note that for odd values of $m$, the line $\ell_{m,n}$ passes through the center of square $1100.$ Thus $\ell_{m,n}$ intersects the interior of cell $1099$ exactly when its slope is strictly between $-1$ and $1$. The line $\ell_{m,n}$ is vertical whenever square $2000$ is the $200$th square in the bottom row of the rectangle. This would happen for $m = 3, 5, 7, 9$ when $n = 900, 450, 300, 225$, respectively. When $n$ is 1 greater than or 1 less than these numbers, the slope of $\ell_{m,n}$ is $1$ or $-1$, respectively. In all other cases the slope is strictly between $-1$ and $1.$ The admissible values for $n$ for each possible value of $m$ are given in the following table. \[\begin{tabular}{|c|c|c|c|c|}\hline m & minimum n & maximum n & avoided n & number of odd n\\\hline 3&667&999&899, 900, 901&165\\\hline 5&400&499&449, 450, 451&48\\\hline 7&286&333&299, 300, 301&22\\\hline 9&223&249&224, 225, 226&13\\\hline \end{tabular}\] This accounts for $165 + 48 + 22 + 13 = 248$ rectangles.

Video Solution 1

https://www.youtube.com/watch?v=MrtKoO16XLQ ~ MathEx

Video Solution 2

https://youtu.be/v58SLOoAKTw

See Also

2020 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 11
Followed by
Problem 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png