Difference between revisions of "2020 CIME I Problems/Problem 7"

(Solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
{{solution}}
+
Let <math>S(n) = f(1)+f(2)+\cdots+f(n)</math>. We claim that <cmath>S(n) = \frac{1}{2} - \frac{1}{2 \cdot (2n+1)!!}.</cmath> We show this using induction. Suppose this is true for some <math>n = k</math>. Then, it must be true for <math>k+1</math>. The base case when <math>k = 1</math> is trivial. Then, we have that <cmath>\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*}</cmath> Hence, this completes the induction therefore proving the claim. So, the numerator <math>p</math> is <math>\frac{1}{2}(4041!! - 1)</math>. We proceed using Euler's Theorem combined with Chinese Remainder Theorem. It is obvious that <math>4041!! \equiv 0 \pmod{125}</math> so <math>p \equiv 62\pmod{125}</math>. Also, instead of considering <math>p</math> modulo <math>8</math>, we consider it modulo <math>16</math>. Then, we get <cmath>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},</cmath> by Euler's Totient Theorem as <math>\phi(16) = 8</math>. This implies that <math>\frac{1}{2}(4041!! - 1) \equiv 0\pmod{8}</math>, so <math>p \equiv 0\pmod{8}</math>. Solving the system of congruences, we get <math>p \equiv \boxed{312}\pmod{1000}</math>. ~rocketsri (based off of official solution)
Notice that the product of first 2n+1 odd numbers = (2n+2)! / ((2^n+2)*(n+1)!) ; substituting this for f(n) gives the answer
+
 
 
==See also==
 
==See also==
 
{{CIME box|year=2020|n=I|num-b=6|num-a=8}}
 
{{CIME box|year=2020|n=I|num-b=6|num-a=8}}

Revision as of 12:05, 2 February 2021

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

Invalid username
Login to AoPS