MathDB

11

Part of 2011 AIME Problems

Problems(2)

Remainders when divided by 1000

Source:

3/18/2011
Let RR be the set of all possible remainders when a number of the form 2n2^n, nn a nonnegative integer, is divided by 10001000. Let SS be the sum of all elements in RR. Find the remainder when SS is divided by 10001000.
modular arithmeticinvariantAMCAIMEfunction
Determinants of a Matrix [2011.II.11]

Source:

3/31/2011
Let MnM_n be the n×nn\times n matrix with entries as follows: for 1≤i≤n1\leq i \leq n, mi,i=10m_{i,i}=10; for 1≤i≤n−1,mi+1,i=mi,i+1=31\leq i \leq n-1, m_{i+1,i}=m_{i,i+1}=3; all other entries in MnM_n are zero. Let DnD_n be the determinant of matrix MnM_n. Then ∑n=1∞18Dn+1\displaystyle \sum_{n=1}^{\infty} \dfrac{1}{8D_n+1} can be represented as pq\frac{p}{q}, where pp and qq are relatively prime positive integers. Find p+qp+q.
Note: The determinant of the 1×11\times 1 matrix [a][a] is aa, and the determinant of the 2×22\times 2 matrix [abcd]=ad−bc\left[ \begin{array}{cc} a & b \\ c & d \end{array} \right]=ad-bc; for n≥2n\geq 2, the determinant of an n×nn\times n matrix with first row or first column a1 a2 a3… ana_1\ a_2\ a_3 \dots\ a_n is equal to a1C1−a2C2+a3C3−⋯+(−1)n+1anCna_1C_1 - a_2C_2 + a_3C_3 - \dots + (-1)^{n+1} a_nC_n, where CiC_i is the determinant of the (n−1)×(n−1)(n-1)\times (n-1) matrix found by eliminating the row and column containing aia_i.
linear algebramatrixinductionAMCAIMEnumber theoryrelatively prime