2020 CIME I Problems/Problem 7

Revision as of 12:05, 2 February 2021 by Rocketsri (talk | contribs) (Solution)

Problem 7

For every positive integer $n$, define \[f(n)=\frac{n}{1 \cdot 3 \cdot 5 \cdots (2n+1)}.\] Suppose that the sum $f(1)+f(2)+\cdots+f(2020)$ can be expressed as $\frac{p}{q}$ for relatively prime integers $p$ and $q$. Find the remainder when $p$ is divided by $1000$.

Solution

Let $S(n) = f(1)+f(2)+\cdots+f(n)$. We claim that \[S(n) = \frac{1}{2} - \frac{1}{2 \cdot (2n+1)!!}.\] We show this using induction. Suppose this is true for some $n = k$. Then, it must be true for $k+1$. The base case when $k = 1$ is trivial. Then, we have that \begin{align*} S(k+1) &= f(k) + S(k) \\ {} &= \frac{n}{(2n+1)!!} + \frac{1}{2} - \frac{1}{2 \cdot (2n+1)!!} \\ {} &= \frac{1}{2} - \frac{1}{2 \cdot (2n+3)!!}. \end{align*} Hence, this completes the induction therefore proving the claim. So, the numerator $p$ is $\frac{1}{2}(4041!! - 1)$. We proceed using Euler's Theorem combined with Chinese Remainder Theorem. It is obvious that $4041!! \equiv 0 \pmod{125}$ so $p \equiv 62\pmod{125}$. Also, instead of considering $p$ modulo $8$, we consider it modulo $16$. Then, we get \[4041!! \equiv 3^{253} \cdot 5^{253} \cdot 7^{253} \cdot 9^{252} \cdot 11^{252} \cdot 13^{252} \cdot 15^{252} \equiv 3 \cdot 5 \cdot 7 \cdot 9 \equiv 1\pmod{16},\] by Euler's Totient Theorem as $\phi(16) = 8$. This implies that $\frac{1}{2}(4041!! - 1) \equiv 0\pmod{8}$, so $p \equiv 0\pmod{8}$. Solving the system of congruences, we get $p \equiv \boxed{312}\pmod{1000}$. ~rocketsri (based off of official solution)

See also

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

The problems on this page are copyrighted by the MAC's Christmas Mathematics Competitions. AMC logo.png