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 "Mock AIME 6 2006-2007 Problems/Problem 10"
(→‎Solution)
 
(36 intermediate revisions by the same user not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
Let <math>R</math> be the rotational matrix for a point along the origin:
+
Let <math>R(\theta)</math> be the rotational matrix for a point to rotate <math>(\theta)</math> around the origin:
  
−
<math>R=\begin{pmatrix} cos(\theta) & -sin(\theta)\\ sin(\theta) & cos(\theta) \end{pmatrix}</math>
+
<math>R(\theta)=\begin{bmatrix} cos(\theta) & -sin(\theta)\\ sin(\theta) & cos(\theta) \end{bmatrix}</math>
  
 
For <math>\theta = 90^\circ</math>
 
For <math>\theta = 90^\circ</math>
  
−
<math>R=\begin{pmatrix} cos(90^\circ) & -sin(90^\circ)\\ sin(90^\circ) & cos(90^\circ) \end{pmatrix}=\begin{pmatrix} 0 & -1\\ 1 & 0 \end{pmatrix}</math>
+
<math>R=\begin{bmatrix} cos(90^\circ) & -sin(90^\circ)\\ sin(90^\circ) & cos(90^\circ) \end{bmatrix}=\begin{bmatrix} 0 & -1\\ 1 & 0 \end{bmatrix}</math>
  
−
Let <math>P_r</math> be the point of rotation.
+
Let <math>P_r</math> be the point of rotation, then <math>P_r=\begin{bmatrix} 2000-n \\ n \end{bmatrix}</math>
  
−
<math>P_r=\begin{pmatrix} 2000-k \\ k \end{pmatrix}</math>
+
Let's write <math>P_n</math> in matrix form as: <math>P_n=\begin{bmatrix} P_{x_n} \\ P_{y_n} \end{bmatrix}</math>, where <math>P_{x_n}</math> and <math>P_{y_n}</math> are the <math>x</math> and <math>y</math> coordinates of <math>P_n</math> respectively.
  
−
<math>P_{n+1}=R(P_n-P_r)+P_r=\begin{pmatrix} 0 & -1\\ 1 & 0 \end{pmatrix}\begin{pmatrix} P_{n_x}-(2000-k) \\ P_{n_y}-k \end{pmatrix}+\begin{pmatrix} 2000-k \\ k \end{pmatrix}</math>
+
We can write the equation of <math>P_{n+1}</math> by translating the <math>P_n</math> to the origin, multiply it by the rotation matrix <math>R</math> and then add the point subtracted:
  
 +
<math>P_{n+1}=(R)(P_n-P_r)+P_r=\begin{bmatrix} 0 & -1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} P_{x_n}-(2000-n) \\ P_{y_n}-n \end{bmatrix}+\begin{bmatrix} 2000-n \\ n \end{bmatrix}=\begin{bmatrix} 2000-P_{y_n} \\ P_{x_n}+2n-2000 \end{bmatrix}</math>
 +
 +
Now we find <math>P_{n+2}</math>:
 +
 +
<math>P_{n+2}=\begin{bmatrix} 2000-P_{y_{n+1}} \\ P_{x_{n+1}}+2n-2000 \end{bmatrix}=\begin{bmatrix} 2000-(P_{x_n}+2n-2000) \\ (2000-P_{y_n})+2(n+1)-2000 \end{bmatrix}=\begin{bmatrix} 4000-P_{x_n}-2n \\ -P_{y_n}+2(n+1) \end{bmatrix}</math>
 +
 +
For this problem, we're only interested in the <math>y</math>-coordinate.  So,
 +
 +
<math>P_{y_{n+1}}=P_{x_n}+2n-2000</math>
 +
 +
<math>P_{y_{n+2}}=-P_{y_n}+2(n+1)</math>
 +
 +
Notice that since <math>2(n+1) \equiv 0\; (mod\;2)</math>, then <math>P_{y_{n+2}} \equiv P_{y_n}\; (mod\;2)</math>.
 +
 +
Since <math>P_{y_0}=0</math> and we're looking at a <math>y</math>-coordinate of <math>433</math>, we notice that <math>433 \equiv 1\; (mod\;2) \not\equiv P_{y_0}\; (mod\;2)</math>. 
 +
 +
Therefore we need to calculate <math>P_{y_1}</math>:
 +
 +
<math>P_{y_1}=P_{x_0}+(2)(0)-2000=2007-2000=7</math>
 +
 +
<math>P_{y_m} \equiv 1\; (mod\;2)\equiv P_{y_1}\; (mod\;2)</math>
 +
 +
So, we use the recursive formula for <math>P_{y_{n+2}}</math> starting with <math>P_{y_1}</math>:
 +
 +
<math>P_{y_3}=-P_{y_1}+(2)(1)+2</math>
 +
 +
<math>P_{y_5}=-P_{y_3}+(2)(3)+2</math>
 +
 +
<math>P_{y_7}=-P_{y_5}+(2)(5)+2</math>
 +
 +
and we can find <math>P_{y_{2q+1}}</math> for <math>q \in \mathbb{Z}^{+}</math> as:
 +
 +
<math>P_{y_{2q+1}}=-P_{y_{2q-1}}+2(2q-1)+2=-P_{y_{2q-1}}+4q</math>
 +
 +
<math>P_{y_{2q+1}}=(-1)^q P_{y_1}+4(q-(q-1)+(q-2)-(q-3)+....+0)</math>
 +
 +
<math>P_{y_{2q+1}}=(-1)^q P_{y_1}+4 \left( \begin{cases} q, & q\;is\;odd \\ 0, & q\;is\;even\end{cases}+\begin{cases} -\frac{q-1}{2}, & q\;is\;odd \\ \frac{q}{2}, & q\;is\;even\end{cases} \right) </math>
 +
 +
<math>P_{y_{2q+1}}=(-1)^q P_{y_1}+ \begin{cases} 2q+2, & k\;is\;odd \\ 2q, & q\;is\;even\end{cases}=(-1)^q P_{y_1}+ 2q+\begin{cases} 2, & q\;is\;odd \\ 0, & q\;is\;even\end{cases}</math>
 +
 +
<math>P_{y_{2q+1}}=(-1)^qP_{y_1}+2q+(1-(-1)^q)=(-1)^q(P_{y_1}-1)+2q+1</math>
 +
 +
Since <math>P_{y_{2q+1}}=433</math>, and <math>P_{y_1}=7</math> then we solve for <math>q</math> as follows:
 +
 +
<math>(-1)^q(7-1)+2q+1=433</math>
 +
 +
<math>q=\frac{433-1-(-1)^q6}{2}=216-(-1)^q3</math>
 +
 +
Since <math>\pm 1 \equiv 1\; (mod\;2)</math> then <math>\pm 3 \equiv 1\; (mod\;2)</math> and <math>(-1)^q3 \equiv 1\; (mod\;2)</math>
 +
 +
Therefore <math>(216-(-1)^q3) \equiv 1\; (mod\;2)</math> and <math>q</math> is odd.
 +
 +
So, <math>q=216-(-1)(3)=219</math> and <math>m=2q+1=(2)(219)+1=\boxed{439}</math>
  
 
~Tomas Diaz. orders@tomasdiaz.com
 
~Tomas Diaz. orders@tomasdiaz.com
 +
 +
{{alternate solutions}}

Latest revision as of 15:20, 25 November 2023

Problem

Given a point $P$ in the coordinate plane, let $T_k(P)$ be the $90^\circ$ rotation of $P$ around the point $(2000-k,k)$. Let $P_0$ be the point $(2007,0)$ and $P_{n+1}=T_n(P_n)$ for all integers $n\ge 0$. If $P_m$ has a $y$-coordinate of $433$, what is $m$?

Solution

Let $R(\theta)$ be the rotational matrix for a point to rotate $(\theta)$ around the origin:

$R(\theta)=\begin{bmatrix} cos(\theta) & -sin(\theta)\\ sin(\theta) & cos(\theta) \end{bmatrix}$

For $\theta = 90^\circ$

$R=\begin{bmatrix} cos(90^\circ) & -sin(90^\circ)\\ sin(90^\circ) & cos(90^\circ) \end{bmatrix}=\begin{bmatrix} 0 & -1\\ 1 & 0 \end{bmatrix}$

Let $P_r$ be the point of rotation, then $P_r=\begin{bmatrix} 2000-n \\ n \end{bmatrix}$

Let's write $P_n$ in matrix form as: $P_n=\begin{bmatrix} P_{x_n} \\ P_{y_n} \end{bmatrix}$, where $P_{x_n}$ and $P_{y_n}$ are the $x$ and $y$ coordinates of $P_n$ respectively.

We can write the equation of $P_{n+1}$ by translating the $P_n$ to the origin, multiply it by the rotation matrix $R$ and then add the point subtracted:

$P_{n+1}=(R)(P_n-P_r)+P_r=\begin{bmatrix} 0 & -1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} P_{x_n}-(2000-n) \\ P_{y_n}-n \end{bmatrix}+\begin{bmatrix} 2000-n \\ n \end{bmatrix}=\begin{bmatrix} 2000-P_{y_n} \\ P_{x_n}+2n-2000 \end{bmatrix}$

Now we find $P_{n+2}$:

$P_{n+2}=\begin{bmatrix} 2000-P_{y_{n+1}} \\ P_{x_{n+1}}+2n-2000 \end{bmatrix}=\begin{bmatrix} 2000-(P_{x_n}+2n-2000) \\ (2000-P_{y_n})+2(n+1)-2000 \end{bmatrix}=\begin{bmatrix} 4000-P_{x_n}-2n \\ -P_{y_n}+2(n+1) \end{bmatrix}$

For this problem, we're only interested in the $y$-coordinate. So,

$P_{y_{n+1}}=P_{x_n}+2n-2000$

$P_{y_{n+2}}=-P_{y_n}+2(n+1)$

Notice that since $2(n+1) \equiv 0\; (mod\;2)$, then $P_{y_{n+2}} \equiv P_{y_n}\; (mod\;2)$.

Since $P_{y_0}=0$ and we're looking at a $y$-coordinate of $433$, we notice that $433 \equiv 1\; (mod\;2) \not\equiv P_{y_0}\; (mod\;2)$.

Therefore we need to calculate $P_{y_1}$:

$P_{y_1}=P_{x_0}+(2)(0)-2000=2007-2000=7$

$P_{y_m} \equiv 1\; (mod\;2)\equiv P_{y_1}\; (mod\;2)$

So, we use the recursive formula for $P_{y_{n+2}}$ starting with $P_{y_1}$:

$P_{y_3}=-P_{y_1}+(2)(1)+2$

$P_{y_5}=-P_{y_3}+(2)(3)+2$

$P_{y_7}=-P_{y_5}+(2)(5)+2$

and we can find $P_{y_{2q+1}}$ for $q \in \mathbb{Z}^{+}$ as:

$P_{y_{2q+1}}=-P_{y_{2q-1}}+2(2q-1)+2=-P_{y_{2q-1}}+4q$

$P_{y_{2q+1}}=(-1)^q P_{y_1}+4(q-(q-1)+(q-2)-(q-3)+....+0)$

$P_{y_{2q+1}}=(-1)^q P_{y_1}+4 \left( \begin{cases} q, & q\;is\;odd \\ 0, & q\;is\;even\end{cases}+\begin{cases} -\frac{q-1}{2}, & q\;is\;odd \\ \frac{q}{2}, & q\;is\;even\end{cases} \right)$

$P_{y_{2q+1}}=(-1)^q P_{y_1}+ \begin{cases} 2q+2, & k\;is\;odd \\ 2q, & q\;is\;even\end{cases}=(-1)^q P_{y_1}+ 2q+\begin{cases} 2, & q\;is\;odd \\ 0, & q\;is\;even\end{cases}$

$P_{y_{2q+1}}=(-1)^qP_{y_1}+2q+(1-(-1)^q)=(-1)^q(P_{y_1}-1)+2q+1$

Since $P_{y_{2q+1}}=433$, and $P_{y_1}=7$ then we solve for $q$ as follows:

$(-1)^q(7-1)+2q+1=433$

$q=\frac{433-1-(-1)^q6}{2}=216-(-1)^q3$

Since $\pm 1 \equiv 1\; (mod\;2)$ then $\pm 3 \equiv 1\; (mod\;2)$ and $(-1)^q3 \equiv 1\; (mod\;2)$

Therefore $(216-(-1)^q3) \equiv 1\; (mod\;2)$ and $q$ is odd.

So, $q=216-(-1)(3)=219$ and $m=2q+1=(2)(219)+1=\boxed{439}$

~Tomas Diaz. orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_6_2006-2007_Problems/Problem_10&oldid=205783"