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 "2020 CIME I Problems/Problem 7"

(→‎Solution)
(→‎Solution)
 
Line 3: Line 3:
  
 
==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)
+
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)
  
 
==See also==
 
==See also==

Latest revision as of 11: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 (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_CIME_I_Problems/Problem_7&oldid=144649"