https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Piguy747&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T14:36:19ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=Characteristic_polynomial&diff=159291Characteristic polynomial2021-07-30T20:23:46Z<p>Piguy747: Lucas numbers in introductory problems were L_1=2 and L_2=1 when they should be L_0=2 and L_1=1.</p>
<hr />
<div>The '''characteristic polynomial''' of a linear [[operator]] refers to the [[polynomial]] whose roots are the [[eigenvalue]]s of the operator. It carries much information about the operator. <br />
<br />
In the context of problem-solving, the characteristic polynomial is often used to find closed forms for the solutions of [[#Linear recurrences|linear recurrences]].<br />
<br />
== Definition ==<br />
Suppose <math>A</math> is a <math>n \times n</math> [[matrix]] (over a field <math>K</math>). Then the characteristic polynomial of <math>A</math> is defined as <math>P_A(t) = \det(tI - A)</math>, which is a <math>n</math>th degree polynomial in <math>t</math>. Here, <math>I</math> refers to the <math>n\times n</math> [[identity matrix]].<br />
<br />
Written out, the characteristic polynomial is the [[determinant]]<br />
<br />
<center><cmath>P_A(t) = \begin{vmatrix}t-a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & t-a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & t-a_{nn}\end{vmatrix}</cmath></center><br />
<br />
== Properties ==<br />
An [[eigenvector]] <math>\bold{v} \in K^n</math> is a non-zero vector that satisfies the relation <math>A\bold{v} = \lambda\bold{v}</math>, for some scalar <math>\lambda \in K</math>. In other words, applying a linear operator to an eigenvector causes the eigenvector to dilate. The associated number <math>\lambda</math> is called the [[eigenvalue]]. <br />
<br />
There are at most <math>n</math> distinct eigenvalues, whose values are exactly the roots of the characteristic polynomial of the square matrix. To prove this, we use the fact that the determinant of a matrix is <math>0</math> [[iff]] the column vectors of the matrix are [[linearly dependent]]. Observe that if <math>\lambda</math> satisfies <math>\det(\lambda I-A) = 0</math>, then the column vectors of the <math>n\times n</math> matrix <math>\lambda I - A</math> are linearly dependent. Indeed, if we define <math>T = \lambda I - A</math> and let <math>\bold{T}^1, \bold{T}^2, \ldots, \bold{T}^n</math> denote the column vectors of <math>T</math>, this is equivalent to saying that there exists not all zero scalars <math>v_i \in K</math> such that <br />
<br />
<cmath>v_1 \cdot \bold{T}^1 + v_2 \cdot \bold{T}^2 + \cdots + v_n \cdot \bold{T}^n = \bold{O}.</cmath><br />
<br />
Hence, there exists a non-zero vector <math>\bold{v} = (v_1, v_2, \ldots, v_n) \in K^n</math> such that <math>(\lambda I - A) \bold{v} = \bold{O}</math>. Distributing and re-arranging, <math>A\bold{v} = \lambda\bold{v}</math>, as desired. In the other direction, if <math>A \bold{v} = \lambda \bold{v}</math>, then <math>\lambda I \bold{v} - A \bold{v} = \bold{O}</math>. But then, the column vectors of <math>\lambda I - A</math> are linearly dependent, so it follows that <math>\det(\lambda I - A) = 0</math>. <br><br><br />
<br />
Note that if <math>t = 0</math>, then <math>P_A(0) = \det (tI - A) = \det (-A) = (-1)^n \det (A)</math>. Hence, the characteristic polynomial encodes the determinant of the matrix. Also, the [[coefficient]] of the <math>t^{n-1}</math> term of <math>P_A(t)</math> gives the negative of the [[trace]] of the matrix (which follows from [[Vieta's formulas]]). <br />
<br />
By the [[Hamilton-Cayley Theorem]], the characteristic polynomial of a square matrix applied to the square matrix itself is zero, that is <math>P_A(A) = 0</math>. The [[minimal polynomial]] of <math>A</math> thus divides the characteristic polynomial <math>p_A</math>. <br />
<br />
== Linear recurrences ==<br />
Let <math>x_1, x_2, \ldots, </math> be a sequence of real numbers. Consider a monic [[homogenous]] [[linear recurrence]] of the form <br />
<br />
<center><cmath>x_{n} = c_{n-1}x_{n-1} + c_{n-2}x_{n-2} + \cdots + c_{n-k}x_{n-k}, \quad (*)</cmath></center> <br />
<br />
where <math>c_1, \ldots, c_k</math> are real constants. The characteristic polynomial of this recurrence is defined as the polynomial <br />
<br />
<center><cmath>P(x) = x^k - c_{k-1}x^{k-1} - c_{k-2}x^{k-2} - \cdots -c_1x - c_k.</cmath></center> <br />
<br />
For example, let <math>F_n</math> be the <math>n</math>th [[Fibonacci number]] defined by <math>F_1 = F_2 = 1</math>, and <br />
<br />
<center><cmath>F_n = F_{n-1} + F_{n-2} \Longleftrightarrow F_n - F_{n-1} - F_{n-2} = 0.</cmath></center><br />
<br />
Then, its characteristic polynomial is <math>x^2 - x - 1</math>. <br><br><br />
<br />
The roots of the polynomial can be used to write a closed form for the recurrence. If the roots of this polynomial <math>P</math> are distinct, then suppose the roots are <math>r_1,r_2, \cdots, r_k</math>. Then, there exists real constants <math>a_1, a_2, \cdots, a_k</math> such that<br />
<br />
<center><cmath>x_n = a_1 \cdot r_1^n + a_2 \cdot r_2^n + \cdots + a_k \cdot r_k^n</cmath></center><br />
<br />
If we evaluate <math>k</math> different values of <math>x_i</math> (typically <math>x_0, x_1, \cdots, x_{k-1}</math>), we can find a linear system in the <math>a_i</math>s that can be solved for each constant. Refer to the [[#Introductory|introductory problems]] below to see an example of how to do this. In particular, for the Fibonacci numbers, this yields [[Binet's formula]]. <br><br><br />
<br />
If there are roots with multiplicity greater than <math>1</math>, suppose <math>r_1 = r_2 = \cdots = r_{k_1}</math>. Then we would replace the term <math>a_1 \cdot r^n + a_2 \cdot r_2^n + \cdots + a_{k_1} \cdot r_{k_1}^n</math> with the expression <br />
<br />
<center><cmath>(a_1 \cdot n^{k_1-1} + a_2 \cdot n^{k_1 - 2} + \cdots + a_{k_1-1} \cdot n + a_{k_1}) \cdot r^n.</cmath></center><br />
<br />
That is, there is now a polynomial in <math>n</math> multiplied with the exponent. Note that there are still the same number of constants that we must solve for. For example, consider the recurrence relation <math>x_n = -2x_{n-1} -x_{n-2} \Longleftrightarrow x_n + 2x_{n-1} + x_{n-2} = 0</math>. It’s characteristic polynomial, <math>x^2 + 2x + 1</math>, has a <math>-1</math> double root. Then, its closed form solution is of the type <math>x_n = (-1)^n(an + b)</math>. <br><br><br />
<br />
Given a linear recurrence of the form <math>x_n - a_1x_{n-1} - \cdots - a_kx_{n-k} = f(n)</math>, we often try to find a new sequence <math>y_n = x_n - g(n)</math> such that <math>y_n</math> is a homogenous linear recurrence. Then, we can find a closed form for <math>y_n</math>, and then the answer is given by <math>x_n = y_n + g(n)</math>. <br />
<br />
Of the following proofs, the second and third are more approachable. <br />
<br />
=== Proof 1 (Linear Algebra) ===<br />
Note: The ideas expressed in this section can be transferred to the next section about differential equations. This requires some knowledge of [[linear algebra]] (upto the [[Spectral Theorem]]).<br />
<br />
Let <math>\bold{y}_{n-1} = \begin{pmatrix} x_{n-1} \\ x_{n-2} \\ \vdots \\ x_{n-k} \end{pmatrix}</math>. Then, we can express our linear recurrence as the matrix <br />
<br />
<center><cmath>A = \begin{pmatrix}a_1 & a_2 & a_3 & \cdots & a_{k-1} & a_{k} \\ 1 & 0 & 0 & \cdots &0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{pmatrix},</cmath></center><br />
<br />
so that <math>\bold{y}_n = A\bold{y}_{n-1}</math> (try to verify this). The characteristic polynomial of <math>A</math> is precisely <math>P_A(t) = \det (tI - A) = a_1 \cdot t^{k-1} + a_2 \cdot t^{k-2} \cdots + a_k = 0</math>. This is not difficult to show via [[Laplace's expansion]] and induction, and is left as an exercise to the reader. <br />
<br />
If the roots of <math>P_A</math> are distinct, then there exists a [[basis]] (of <math>\mathbb{R}^{k-1}</math>) consisting of [[eigenvector]]s of <math>A</math> (since eigenvectors of different eigenvalues are [[linearly independent]]). That is, applying a change of bases, we can write <br />
<br />
<center><cmath>A = U^{-1} D U</cmath></center><br />
<br />
for a matrix <math>U</math> and a diagonal matrix <math>D</math>. Then, <math>A^2 = U^{-1} D U U^{-1} D U = U^{-1} D^2 U</math>, and in general, <math>A^n = U^{-1} D^n U</math>. Thus, <math>\bold{y}_{n} = A^{n}\bold{y}_0 = U^{-1}D^{n+k}U\bold{y}_0</math>. Here, <math>U^{-1}, U,</math> and <math>\bold{y}_0</math> are fixed (note that to find the values of <math>\bold{y}_0</math>, we may need to trace the recurrence backwards. We only take the <math>0</math>th index for simplicity). It follows that <math>y_{n}</math> is a linear combination of the diagonal elements of <math>D</math>, namely <math>r_1^n, r_2^n, \ldots, r_k^n</math>. <br><br><br />
<br />
Suppose now that that the roots of <math>P_A</math> are not distinct. Then, we can write the matrix in the [[Jordan normal form]]. For simplicity, first consider just a single root <math>r</math> repeated <math>k</math> times. The corresponding Jordan form of the matrix is given by (that is, the matrix is [[similar]] to the following):<br />
<br />
<center><cmath>\begin{pmatrix} r & 1 & 0 & \cdots & 0 \\ 0 & r & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & r \end{pmatrix}</cmath>.</center><br />
<br />
Exponentiating this matrix to the <math>n</math>th power will yield [[binomial coefficient]]s as follows<br />
<br />
<center><cmath>\begin{pmatrix} r^n & {n \choose 1}r^{n-1} & {n \choose 2}r^{n-2} & \cdots & {n \choose k}r^{n-k} \\ 0 & r & {n \choose 1}r^{n-1} & \cdots & {n \choose {k-1}}r^{n-k+1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & r^n \end{pmatrix}.</cmath></center><br />
<br />
We can treat the binomial coefficient as a polynomial in <math>n</math>. Furthermore, we can scale away the powers of the eigenvalue (which is a constant); after taking the appropriate linear combinations of the binomial coefficients and a little bit of work, the result follows. <br><br><br />
<br />
See also a <url>viewtopic.php?t=290351 graph-theoretic</url> approach.<br />
<br />
=== Proof 2 (Induction) ===<br />
<br />
There are a couple of lower-level ways to prove this. One is by [[induction]], though the proof is not very revealing; we can explicitly check that a sequence <math>\{a_1 \cdot r_1^n + a_2 \cdot r_2^n + \cdots + a_k \cdot r_k^n\}</math>, for real numbers <math>a_1, a_2, \ldots, a_k</math>, satisfies the linear recurrence relation <math>(*)</math>. If the two sequences are the same for the first <math>k</math> values of the sequence, it follows by induction that the two sequences must be exactly the same.<br />
<br />
In particular, for <math>k=2</math>, we can check this by using the identity <br />
<br />
<center><cmath>ax^{n+1} + by^{n+1} = (x+y)(ax^n + by^n) - xy(ax^{n-1} + by^{n-1}).</cmath></center> <br><br />
<br />
It is also possible to reduce the recurrence to a [[telescoping sum]]. However, the details are slightly messy. <br />
<br />
=== Proof 3 (Partial fractions) ===<br />
<br />
Another method uses [[partial fractions]] and [[generating function]]s, though not much knowledge of each is required for this proof. Let <math>G_n = a_1G_{n-1} + \cdots + a_kG_{n-k}</math> be a linear recurrence. Consider the [[generating function]] given by <br />
<br />
<center><cmath>G(x) = G_0 + G_1x + G_2x^2 + \cdots</cmath></center><br />
<br />
Then, writing the following expressing out and carefully comparing coefficients (try it), <br />
<br />
<center><cmath>a_kG(x) \cdot x^{k-1} + a_{k-1}G(x) \cdot x^{k-2} + \cdots + a_{2}G(x) \cdot x + a_{1}G(x) = \frac{G(x) + R(x)}x,</cmath></center><br />
<br />
where <math>R(x)</math> is a remainder polynomial with degree <math>\le k-1</math>. Re-arranging, <br />
<br />
<center><cmath>G(x) = \frac{R(x)}{a_k\cdot x^{k} + a_{k-1}\cdot x^{k-1} + \cdots + a_{1}x - 1}</cmath></center><br />
<br />
This polynomial in the denominator is the reverse of the characteristic polynomial of the recurrence. Hence, its roots are <math>1/r_1, 1/r_2, \ldots, 1/r_k</math>, assuming that the roots are distinct. Using [[partial fraction]] decomposition (essentially the reverse of the process of adding fractions by combining denominators, except we now pull the denominators apart), we can write <br />
<br />
<center><cmath>G(x) = \frac{c_1}{1 - r_1x} + \frac{c_2}{1-r_2x} + \cdots + \frac{c_k}{1-r_kx } </cmath></center><br />
<br />
for some constants <math>c_1, \ldots, c_k</math>. Using the [[geometric series]] formula, we have <math>\frac{c}{1-y} = c + cy + cy^2 + \ldots</math>. Thus, <br />
<br />
<center><cmath>G(x) = (c_1 + \cdots + c_k) + (c_1r_1 + \cdots + c_kr_k)x + (c_1r_1^2 + \cdots + c_kr_k^2)x^2 + \cdots.</cmath></center><br />
<br />
Comparing coefficients with our original definition of <math>G(x)</math> gives <math>G_n = c_1r_1^n + c_2r_2^n + \cdots + c_kr_k^n</math>, as desired. <br><br><br />
<br />
The generalization to characteristic polynomials with multiple roots is not difficult from here, and is left to the reader. The partial fraction decomposition will have terms of the form <math>\frac{c_i}{(1-r_ix)^\alpha}</math> for <math>\alpha > 1</math>. <br><br><br />
<br />
A note about this argument: all of the power series used here are defined formally, and so we do not actually need to worry whether or not they converge. See these [http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=250866 blog][http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=215833 posts] for further ideas.<br />
<br />
== Differential equations ==<br />
Given a monic linear [[homogenous]] [[differential equation]] of the form <math>D^ny +c_{n-1}D^{n-1}y + \cdots + c_1Dy + c_0y = 0</math>, then the characteristic polynomial of the equation is the polynomial <br />
<br />
<center><cmath>P(t) = t^n + c_{n-1}t^{n-1} + c_{n-2}t^{n-2} + \cdots + c_0.</cmath></center> <br />
<br />
Here, <math>D = \frac{d}{dx}</math> is short-hand for the differential operator. <br><br><br />
<br />
If the roots of the polynomial are distinct, say <math>r_1, r_2, \cdots, r_n</math>, then the solutions of this differential equation are precisely the linear combinations <math>y(x) = a_1e^{r_1x} + a_2e^{r_2x} + \cdots + a_ne^{r_nx}</math>. Similarly, if there is a set of roots with multiplicity greater than <math>1</math>, say <math>r_1, r_2, \cdots, r_k</math>, then we would replace the term <math>a_1e^{r_1x} + \cdots + a_ke^{r_kx}</math> with the expression <math>(a_1x^{k-1} + a_2x^{k-2} + \cdots + a_{k-1}x + a_k)e^{r_1x}</math>. <br><br><br />
<br />
In general, given a linear differential equation of the form <math>Ly = f</math>, where <math>L = c_nD^n + c_{n-1}D^{n-1} + \cdots + c_0</math> is a linear differential operator, then the set of solutions is given by the sum of any solution to the homogenous equation <math>Ly = 0</math> and a specific solution to <math>Ly = f</math>.<br />
<br />
=== Proof ===<br />
We can apply an induction technique similar to the section on linear recurrences above. <br />
<br />
From linear algebra, we can use the following [[vector space]] decomposition theorem. Let <math>A: V \to V</math> be a linear operator for a [[vector space]]s <math>V</math> over a field <math>K</math>. Suppose that there exists a polynomial <math>f(x) \in K[x]</math> such that <math>f = gh</math>, where <math>g</math> and <math>h</math> are non-zero polynomials such that <math>\text{gcd}\,(g,h) = 1</math>, and such that <math>f(A) = O</math>. Then <math>V = \ker g(A) \oplus \ker h(A)</math>. This allows us to reduce the differential equation into finding the solutions to the equation <math>(D - \lambda I)^my = 0</math>, which has a basis of functions <math>e^{\lambda t}, te^{\lambda t}, \ldots, t^{m-1}e^{\lambda t}</math>.<br />
<br />
== Problems ==<br />
=== Introductory ===<br />
*Prove [[Binet's formula]]. Find a similar closed form equation for the [[Lucas sequence]], defined with the starting terms <math>L_0 = 2, L_1 = 1</math>, and satisfying the recursion <math>L_n = L_{n-1} + L_{n-2}</math>. <br />
*Let <math>\{x_n\}</math> denote the sequence defined by the recursion <math>x_0 = 3, x_1 = 1</math>, and <math>x_n = 2x_{n-1} + 3x_{n-2}</math>. Find a closed form expression for <math>x_n</math>.<br />
*Given <math>a_0 = 1</math>, <math>a_1 = 3</math>, and the general relation <math>a_n^2 - a_{n - 1}a_{n + 1} = ( - 1)^n</math> for <math>n \ge 1</math>. Find a linear recurrence for <math>a_n</math>. (AHSME 1958, Problem 40)<br />
<br />
=== Intermediate ===<br />
*Let <math>S_n</math> denote the number of ternary sequences (consisting of <math>0</math>,<math>1</math>, and <math>2</math>s) of length <math>n</math>, such that they do not contain a substring of "10", "01", or "11". Find a closed form expression for <math>S_n</math>. <br />
*Let <math>\{X_n\}</math> and <math>\{Y_n\}</math> be sequences defined as follows: <br />
<br />
<center><cmath>X_0 = Y_0 = X_1 = Y_1 = 1, X_{n+1} = X_n + 2X_{n-1}, Y_{n+1} = 3Y_n + 4Y_{n-1}.</cmath></center><br />
<br />
:Let <math>k</math> be the largest integer that satisfies all of the following conditions:<br />
<br />
::(i) <math>|X_i - k| \le 2007</math>, for some positive integer <math>i</math>;<br />
::(ii) <math>|Y_j - k| \le 2007</math>, for some positive integer <math>j</math>;<br />
::(iii) <math>k < 10^{2007}</math>. <br />
<br />
:Find the remainder when <math>k</math> is divided by <math>2007</math>. (2007 [[iTest]], #47)<br />
<br />
*Let <math>a_{n}</math>, <math>b_{n}</math>, and <math>c_{n}</math> be geometric sequences with different common ratios and let <math>a_{n}+b_{n}+c_{n}=d_{n}</math> for all integers <math>n</math>. If <math>d_{1}=1</math>, <math>d_{2}=2</math>, <math>d_{3}=3</math>, <math>d_{4}=-7</math>, <math>d_{5}=13</math>, and <math>d_{6}=-16</math>, find <math>d_{7}</math>. ([[Mock AIME 1 2006-2007/Problem 13|Mock AIME 1 2006-2007, Problem 13]])<br />
<br />
*Find all possible values of <math>x_0</math> and <math>x_1</math> such that the sequence defined by:<br />
<br />
<center><cmath>x_{n + 1} = \frac {x_{n - 1} x_n}{3x_{n - 1} - 2x_n}, \quad n \ge 1</cmath></center><br />
<br />
:contains infinitely many natural numbers.<br />
<br />
*Show that <math>a^n + b^n + c^n</math> can be written as a linear combination of the [[elementary symmetric polynomials]] <math>abc, ab+bc+ca, a+b+c</math>. In general, prove [[Newton's sums]]. <br />
<br />
=== Olympiad ===<br />
*Let <math>r</math> be a real number, and let <math>x_n</math> be a sequence such that <math>x_0 = 0, x_1 = 1</math>, and <math>x_{n+2} = rx_{n+1} - x_n</math> for <math>n \ge 0</math>. For which values of <math>r</math> does <math>x_1 + x_3 + \cdots + x_{2m-1} = x_m^2</math> for all positive integers <math>m</math>? ([[WOOT]])<br />
* Let <math>a(x,y)</math> be the polynomial <math>x^2y + xy^2</math>, and <math>b(x,y)</math> the polynomial <math>x^2 + xy + y^2</math>. Prove that we can find a polynomial <math>p_n(a, b)</math> which is identically equal to <math>(x + y)^n + (-1)^n (x^n + y^n)</math>. For example, <math>p_4(a, b) = 2b^2</math>. ([[1976 Putnam Problems/Problem A2|1976 Putnam, Problem A2]]).<br />
*<math>a_1,a_2,a_3,b_1,b_2,b_3</math> are distinct positive integers such that <math>(n + 1)a_1^n + na_2^n + (n - 1)a_3^n|(n + 1)b_1^n + nb_2^n + (n - 1)b_3^n</math> holds for all positive integer <math>n</math>. Prove that there exists <math>k\in N</math> such that <math>b_i = ka_i</math> for <math>i = 1,2,3</math>. (2010 Chinese MO, Problem 6)<br />
<br />
== Hints/Solutions ==<br />
=== Introductory ===<br />
* A proof of [[Binet's formula]] may be found in that link. The characteristic polynomial of the Lucas sequence is exactly the same. Hence, the only thing we have to change are the coefficients. <br />
* We will work out this problem in full detail. The recurrence relation is <math>x_n -2x_{n-1} -3x_{n-2}</math>, and its characteristic polynomial is given by <math>x^2-2x-3</math>. The roots of this polynomial are <math>-1</math> and <math>3</math>. Thus, a closed form solution is given by <math>x_n = a \cdot (-1)^n + b \cdot 3^n</math>. For <math>n = 0</math>, we get <math>x_0 = a + b = 3</math>, and for <math>n = 1</math>, we get <math>x_1 = -a + 3b = 1</math>. Solving gives <math>a = 2, b = 1</math>. Thus, our answer is <math>x_n = 2 \cdot (-1)^n + 3^n</math>. <br />
*<url>viewtopic.php?t=282744 Discussion</url> (1958 AHSME, 40)<br />
<br />
=== Intermediate ===<br />
*<url>viewtopic.php?t=335138 Discussion</url><br />
*Answer (2007 iTest 47): The answer is <math>k = 7468</math> (before taking <math>\mod{2007}</math>).<br />
*<url>viewtopic.php?t=287441 Discussion</url> <br />
*Hint (Newton’s Sum): Let us work backwards. Suppose <math>a,b,c</math> are the roots of the characteristic polynomial of a linear recurrence. Then apply [[Vieta's formulas]].<br />
<br />
=== Olympiad ===<br />
*Hint (WOOT): substitute the closed form solution. It is true for all <math>r</math>. <br />
*Hint (1976 Putnam A2): do the even and odd cases separately.<br />
*<url>viewtopic.php?search_id=804457492&t=327474 Discussion</url> (2010 Chinese MO, 6)<br />
<br />
[[Category:Linear algebra]]</div>Piguy747https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_4&diff=1573222020 AIME I Problems/Problem 42021-07-04T04:45:10Z<p>Piguy747: </p>
<hr />
<div><br />
== Problem ==<br />
Let <math>S</math> be the set of positive integers <math>N</math> with the property that the last four digits of <math>N</math> are <math>2020,</math> and when the last four digits are removed, the result is a divisor of <math>N.</math> For example, <math>42,020</math> is in <math>S</math> because <math>4</math> is a divisor of <math>42,020.</math> Find the sum of all the digits of all the numbers in <math>S.</math> For example, the number <math>42,020</math> contributes <math>4+2+0+2+0=8</math> to this total.<br />
<br />
== Solution 1 ==<br />
<br />
We note that any number in <math>S</math> can be expressed as <math>a(10,000) + 2,020</math> for some integer <math>a</math>. The problem requires that <math>a</math> divides this number, and since we know <math>a</math> divides <math>a(10,000)</math>, we need that <math>a</math> divides 2020. Each number contributes the sum of the digits of <math>a</math>, as well as <math>2 + 0 + 2 +0 = 4</math>. Since <math>2020</math> can be prime factorized as <math>2^2 \cdot 5 \cdot 101</math>, it has <math>(2+1)(1+1)(1+1) = 12</math> factors. So if we sum all the digits of all possible <math>a</math> values, and add <math>4 \cdot 12 = 48</math>, we obtain the answer.<br />
<br />
Now we list out all factors of <math>2,020</math>, or all possible values of <math>a</math>. <math>1,2,4,5,10,20,101,202,404,505,1010,2020</math>. If we add up these digits, we get <math>45</math>, for a final answer of <math>45+48=\boxed{093}</math>.<br />
<br />
<br />
-molocyxu<br />
<br />
==Solution 2 (Official MAA)==<br />
Suppose that <math>N</math> has the required property. Then there are positive integers <math>k</math> and <math>m</math> such that <math>N = 10^4m + 2020 = k\cdot m</math>. Thus <math>(k - 10^4)m = 2020</math>, which holds exactly when <math>m</math> is a positive divisor of <math>2020.</math> The number <math>2020 = 2^2\cdot 5\cdot 101</math> has <math>12</math> divisors: <math>1, 2, 4, 5, 10, 20, 101, 202, 404, 505, 1010</math>, and <math>2020.</math> The requested sum is therefore the sum of the digits in these divisors plus <math>12</math> times the sum of the digits in <math>2020,</math> which is<br />
<cmath>(1+2+4+5+1+2+2+4+8+10+2+4)+12\cdot4 = 93.</cmath><br />
<br />
<br />
==Solution 3==<br />
Note that for all <math>N \in S</math>, <math>N</math> can be written as <math>N=10000x+2020=20(500x+101)</math> for some positive integer <math>x</math>. Because <math>N</math> must be divisible by <math>x</math>, <math>\frac{20(500x+101)}{x}</math> is an integer. We now let <math>x=ab</math>, where <math>a</math> is a multiple of <math>20</math>. Then <math>\frac{20(500x+101)}{x}=(\frac{20}{a})( \frac{500x}{b}+\frac{101}{b})</math>. We know <math>\frac{20}{a}</math> and <math>\frac{500x}{b}</math> are integers, so for <math>N</math> to be an integer, <math>\frac{101}{b}</math> must be an integer. For this to happen, <math>b</math> must be a multiple of <math>101</math>. <math>101</math> is prime, so <math>b\in \left \{ 1, 101 \right \}</math>. Because <math>a</math> is a multiple of <math>20</math>, <math>a \in \left \{ 1,2,4,5,10,20\right\}</math>. So <math>x \in \left\{1,2,4,5,10,20,101,202,404,505,1010,2020\right\}</math>. Be know that all <math>N</math> end in <math>2020</math>, so the sum of the digits of each <math>N</math> is the sum of the digits of each <math>x</math> plus <math>2+0+2+0=4</math>. Hence the sum of all of the digits of the numbers in <math>S</math> is <math>12 \cdot 4 +45=\boxed{093}</math>.<br />
<br />
==Video Solutions==<br />
*https://youtu.be/5b9Nw4bQt_k<br />
*https://youtu.be/djWzRC-jGYw<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2020|n=I|num-b=3|num-a=5}}<br />
{{MAA Notice}}</div>Piguy747https://artofproblemsolving.com/wiki/index.php?title=1977_AHSME_Problems/Problem_15&diff=1532411977 AHSME Problems/Problem 152021-05-05T18:00:30Z<p>Piguy747: [asy] and [/asy] changed to <asy> and </asy>.</p>
<hr />
<div>Three circles are drawn, so that each circle is externally tangent to the other two circles. Each circle has a radius of <math>3.</math> A triangle is then constructed, such that each side of the triangle is tangent to two circles, as shown below. Find the perimeter of the triangle.<br />
==Diagram==<br />
<br />
<asy><br />
<br />
unitsize(1 cm);<br />
<br />
<br />
draw(Circle(dir(90),sqrt(3)/2));<br />
<br />
draw(Circle(dir(90 + 120),sqrt(3)/2));<br />
<br />
draw(Circle(dir(90 + 240),sqrt(3)/2));<br />
<br />
draw((1 + sqrt(3))*dir(90)--(1 + sqrt(3))*dir(90 + 120)--(1 + sqrt(3))*dir(90 + 240)--cycle);<br />
<br />
</asy><br />
<br />
Or visit here: https://latex.artofproblemsolving.com/5/6/c/56c2e4a15c4c4654523f9b7ac15535647d8bce47.png<br />
<br />
==Solution==<br />
Solution by e_power_pi_times_i<br />
<br />
Draw perpendicular lines from the radii of the circles to the sides of the triangle, and lines from the radii of the circles to the vertices of the triangle. Because the triangle is equilateral, the lines divide the big triangle into a small triangle, three rectangles, and six small <math>30-60-90</math> triangles. The Longer length of the rectangles is 6 because it is the radius of one circle + the radius of another (<math>3+3</math>). The length of one side is <math>2(3\sqrt{3})+6 = 6\sqrt{3}+6</math>. The perimeter is <math>\boxed{\textbf{(D) }18\sqrt{3}+18}</math>.</div>Piguy747https://artofproblemsolving.com/wiki/index.php?title=1977_AHSME_Problems/Problem_15&diff=1532401977 AHSME Problems/Problem 152021-05-05T17:58:04Z<p>Piguy747: </p>
<hr />
<div>Three circles are drawn, so that each circle is externally tangent to the other two circles. Each circle has a radius of <math>3.</math> A triangle is then constructed, such that each side of the triangle is tangent to two circles, as shown below. Find the perimeter of the triangle.<br />
==Diagram==<br />
<br />
[asy]<br />
<br />
unitsize(1 cm);<br />
<br />
<br />
draw(Circle(dir(90),sqrt(3)/2));<br />
<br />
draw(Circle(dir(90 + 120),sqrt(3)/2));<br />
<br />
draw(Circle(dir(90 + 240),sqrt(3)/2));<br />
<br />
draw((1 + sqrt(3))*dir(90)--(1 + sqrt(3))*dir(90 + 120)--(1 + sqrt(3))*dir(90 + 240)--cycle);<br />
<br />
[/asy]<br />
<br />
Or visit here: https://latex.artofproblemsolving.com/5/6/c/56c2e4a15c4c4654523f9b7ac15535647d8bce47.png<br />
<br />
==Solution==<br />
Solution by e_power_pi_times_i<br />
<br />
Draw perpendicular lines from the radii of the circles to the sides of the triangle, and lines from the radii of the circles to the vertices of the triangle. Because the triangle is equilateral, the lines divide the big triangle into a small triangle, three rectangles, and six small <math>30-60-90</math> triangles. The Longer length of the rectangles is 6 because it is the radius of one circle + the radius of another (<math>3+3</math>). The length of one side is <math>2(3\sqrt{3})+6 = 6\sqrt{3}+6</math>. The perimeter is <math>\boxed{\textbf{(D) }18\sqrt{3}+18}</math>.</div>Piguy747https://artofproblemsolving.com/wiki/index.php?title=1977_AHSME_Problems/Problem_15&diff=1532391977 AHSME Problems/Problem 152021-05-05T17:56:56Z<p>Piguy747: Solution used a radius of 2 instead of 3. I changed the the solution to use a radius of 3.</p>
<hr />
<div>Three circles are drawn, so that each circle is externally tangent to the other two circles. Each circle has a radius of <math>3.</math> A triangle is then constructed, such that each side of the triangle is tangent to two circles, as shown below. Find the perimeter of the triangle.<br />
==Diagram==<br />
<br />
[asy]<br />
<br />
unitsize(1 cm);<br />
<br />
<br />
draw(Circle(dir(90),sqrt(3)/2));<br />
<br />
draw(Circle(dir(90 + 120),sqrt(3)/2));<br />
<br />
draw(Circle(dir(90 + 240),sqrt(3)/2));<br />
<br />
draw((1 + sqrt(3))*dir(90)--(1 + sqrt(3))*dir(90 + 120)--(1 + sqrt(3))*dir(90 + 240)--cycle);<br />
<br />
[/asy]<br />
<br />
Or visit here: https://latex.artofproblemsolving.com/5/6/c/56c2e4a15c4c4654523f9b7ac15535647d8bce47.png<br />
<br />
==Solution==<br />
Solution by e_power_pi_times_i<br />
<br />
Draw perpendicular lines from the radii of the circles to the sides of the triangle, and lines from the radii of the circles to the vertices of the triangle. Because the triangle is equilateral, the lines divide the big triangle into a small triangle, three rectangles, and six small <math>30-60-90</math> triangles. The Longer length of the rectangles is 6 because it is the radius of one circle + the radius of another (<math>3+3</math>). The length of one side is <math>2(3\sqrt{3})+6 = 6\sqrt{3}+6</math>. The perimeter is <math>\boxed{\textbf{(D) }18\sqrt{3}+18}</math>.<br />
<br />
This is believed to be incorrect and ought to be checked by a higher authority.</div>Piguy747https://artofproblemsolving.com/wiki/index.php?title=2016_AIME_I_Problems&diff=1431052016 AIME I Problems2021-01-24T21:55:58Z<p>Piguy747: /* Problem 8 */</p>
<hr />
<div>{{AIME Problems|year=2016|n=I}}<br />
<br />
==Problem 1==<br />
For <math>-1<r<1</math>, let <math>S(r)</math> denote the sum of the geometric series <cmath>12+12r+12r^2+12r^3+\cdots .</cmath> Let <math>a</math> between <math>-1</math> and <math>1</math> satisfy <math>S(a)S(-a)=2016</math>. Find <math>S(a)+S(-a)</math>. <br />
<br />
[[2016 AIME I Problems/Problem 1 | Solution]]<br />
<br />
==Problem 2==<br />
Two dice appear to be normal dice with their faces numbered from <math>1</math> to <math>6</math>, but each die is weighted so that the probability of rolling the number <math>k</math> is directly proportional to <math>k</math>. The probability of rolling a <math>7</math> with this pair of dice is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
[[2016 AIME I Problems/Problem 2 | Solution]]<br />
<br />
==Problem 3==<br />
A ''regular icosahedron'' is a <math>20</math>-faced solid where each face is an equilateral triangle and five triangles meet at every vertex. The regular icosahedron shown below has one vertex at the top, one vertex at the bottom, an upper pentagon of five vertices all adjacent to the top vertex and all in the same horizontal plane, and a lower pentagon of five vertices all adjacent to the bottom vertex and all in another horizontal plane. Find the number of paths from the top vertex to the bottom vertex such that each part of a path goes downward or horizontally along an edge of the icosahedron, and no vertex is repeated.<br />
<asy><br />
size(3cm);<br />
pair A=(0.05,0),B=(-.9,-0.6),C=(0,-0.45),D=(.9,-0.6),E=(.55,-0.85),F=(-0.55,-0.85),G=B-(0,1.1),H=F-(0,0.6),I=E-(0,0.6),J=D-(0,1.1),K=C-(0,1.4),L=C+K-A;<br />
draw(A--B--F--E--D--A--E--A--F--A^^B--G--F--K--G--L--J--K--E--J--D--J--L--K);<br />
draw(B--C--D--C--A--C--H--I--C--H--G^^H--L--I--J^^I--D^^H--B,dashed);<br />
dot(A^^B^^C^^D^^E^^F^^G^^H^^I^^J^^K^^L); <br />
</asy><br />
<br />
[[2016 AIME I Problems/Problem 3 | Solution]]<br />
<br />
==Problem 4==<br />
A right prism with height <math>h</math> has bases that are regular hexagons with sides of length <math>12</math>. A vertex <math>A</math> of the prism and its three adjacent vertices are the vertices of a triangular pyramid. The dihedral angle (the angle between the two planes) formed by the face of the pyramid that lies in a base of the prism and the face of the pyramid that does not contain <math>A</math> measures <math>60^\circ</math>. Find <math>h^2</math>.<br />
<br />
[[2016 AIME I Problems/Problem 4 | Solution]]<br />
<br />
==Problem 5==<br />
Anh read a book. On the first day she read <math>n</math> pages in <math>t</math> minutes, where <math>n</math> and <math>t</math> are positive integers. On the second day Anh read <math>n + 1</math> pages in <math>t + 1</math> minutes. Each day thereafter Anh read one more page than she read on the previous day, and it took her one more minute than on the previous day until she completely read the <math>374</math> page book. It took her a total of <math>319</math> minutes to read the book. Find <math>n + t</math>.<br />
<br />
[[2016 AIME I Problems/Problem 5 | Solution]]<br />
<br />
==Problem 6==<br />
<br />
In <math>\triangle ABC</math> let <math>I</math> be the center of the inscribed circle, and let the bisector of <math>\angle ACB</math> intersect <math>\overline{AB}</math> at <math>L</math>. The line through <math>C</math> and <math>L</math> intersects the circumscribed circle of <math>\triangle ABC</math> at the two points <math>C</math> and <math>D</math>. If <math>LI=2</math> and <math>LD=3</math>, then <math>IC= \frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.<br />
<br />
[[2016 AIME I Problems/Problem 6 | Solution]]<br />
<br />
==Problem 7==<br />
For integers <math>a</math> and <math>b</math> consider the complex number <cmath>\frac{\sqrt{ab+2016}}{ab+100}-\left(\frac{\sqrt{|a+b|}}{ab+100}\right)i.</cmath> Find the number of ordered pairs of integers <math>(a,b)</math> such that this complex number is a real number.<br />
<br />
[[2016 AIME I Problems/Problem 7 | Solution]]<br />
<br />
==Problem 8==<br />
For a permutation <math>p = (a_1,a_2,\ldots,a_9)</math> of the digits <math>1,2,\ldots,9</math>, let <math>s(p)</math> denote the sum of the three <math>3</math>-digit numbers <math>a_1a_2a_3</math> , <math>a_4a_5a_6</math>, and <math>a_7a_8a_9</math>. Let <math>m</math> be the minimum value of <math>s(p)</math> subject to the condition that the units digit of <math>s(p)</math> is <math>0</math>. Let <math>n</math> denote the number of permutations <math>p</math> with <math>s(p) = m</math>. Find <math>|m - n|</math>.<br />
<br />
[[2016 AIME I Problems/Problem 8 | Solution]]<br />
<br />
==Problem 9==<br />
Triangle <math>ABC</math> has <math>AB=40,AC=31,</math> and <math>\sin{A}=\frac{1}{5}</math>. This triangle is inscribed in rectangle <math>AQRS</math> with <math>B</math> on <math>\overline{QR}</math> and <math>C</math> on <math>\overline{RS}</math>. Find the maximum possible area of <math>AQRS</math>.<br />
<br />
[[2016 AIME I Problems/Problem 9 | Solution]]<br />
<br />
==Problem 10==<br />
<br />
A strictly increasing sequence of positive integers <math>a_1</math>, <math>a_2</math>, <math>a_3</math>, <math>\cdots</math> has the property that for every positive integer <math>k</math>, the subsequence <math>a_{2k-1}</math>, <math>a_{2k}</math>, <math>a_{2k+1}</math> is geometric and the subsequence <math>a_{2k}</math>, <math>a_{2k+1}</math>, <math>a_{2k+2}</math> is arithmetic. Suppose that <math>a_{13} = 2016</math>. Find <math>a_1</math>.<br />
<br />
[[2016 AIME I Problems/Problem 10 | Solution]]<br />
<br />
==Problem 11==<br />
<br />
Let <math>P(x)</math> be a nonzero polynomial such that <math>(x-1)P(x+1)=(x+2)P(x)</math> for every real <math>x</math>, and <math>\left(P(2)\right)^2 = P(3)</math>. Then <math>P(\tfrac72)=\tfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n</math>.<br />
<br />
[[2016 AIME I Problems/Problem 11 | Solution]]<br />
<br />
==Problem 12==<br />
Find the least positive integer <math>m</math> such that <math>m^2 - m + 11</math> is a product of at least four not necessarily distinct primes. <br />
<br />
[[2016 AIME I Problems/Problem 12 | Solution]]<br />
<br />
==Problem 13==<br />
Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line <math>y = 24</math>. A fence is located at the horizontal line <math>y = 0</math>. On each jump Freddy randomly chooses a direction parallel to one of the coordinate axes and moves one unit in that direction. When he is at a point where <math>y=0</math>, with equal likelihoods he chooses one of three directions where he either jumps parallel to the fence or jumps away from the fence, but he never chooses the direction that would have him cross over the fence to where <math>y < 0</math>. Freddy starts his search at the point <math>(0, 21)</math> and will stop once he reaches a point on the river. Find the expected number of jumps it will take Freddy to reach the river.<br />
<br />
[[2016 AIME I Problems/Problem 13 | Solution]]<br />
<br />
==Problem 14==<br />
<br />
Centered at each lattice point in the coordinate plane are a circle radius <math>\frac{1}{10}</math> and a square with sides of length <math>\frac{1}{5}</math> whose sides are parallel to the coordinate axes. The line segment from <math>(0,0)</math> to <math>(1001, 429)</math> intersects <math>m</math> of the squares and <math>n</math> of the circles. Find <math>m + n</math>.<br />
<br />
[[2016 AIME I Problems/Problem 14 | Solution]]<br />
<br />
==Problem 15==<br />
<br />
Circles <math>\omega_1</math> and <math>\omega_2</math> intersect at points <math>X</math> and <math>Y</math>. Line <math>\ell</math> is tangent to <math>\omega_1</math> and <math>\omega_2</math> at <math>A</math> and <math>B</math>, respectively, with line <math>AB</math> closer to point <math>X</math> than to <math>Y</math>. Circle <math>\omega</math> passes through <math>A</math> and <math>B</math> intersecting <math>\omega_1</math> again at <math>D \neq A</math> and intersecting <math>\omega_2</math> again at <math>C \neq B</math>. The three points <math>C</math>, <math>Y</math>, <math>D</math> are collinear, <math>XC = 67</math>, <math>XY = 47</math>, and <math>XD = 37</math>. Find <math>AB^2</math>.<br />
<br />
[[2016 AIME I Problems/Problem 15 | Solution]]<br />
<br />
{{AIME box|year=2016|n=I|before=[[2015 AIME II Problems]]|after=[[2016 AIME II Problems]]}}<br />
{{MAA Notice}}</div>Piguy747