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 "2010 USAMO Problems/Problem 5"

(→‎Solution)
(Added to olympiad number theory category)
 
(4 intermediate revisions by 4 users not shown)
Line 50: Line 50:
 
\begin{align*}
 
\begin{align*}
 
\frac{1}{p} - 2S_q
 
\frac{1}{p} - 2S_q
−
&= \frac{1}{2r+1} - \left(\sum_{k=1}^{3r+1}\frac{1}{k} - \sum_{k=1}^{r} \frac{1}{k}\right) \\
+
&= \frac{1}{2r+1} - \left(\sum_{k=2}^{3r+1}\frac{1}{k} - \sum_{k=1}^{r} \frac{1}{k}\right) \\
 
&= \frac{1}{2r+1} - \left(\sum_{k=r+1}^{3r+1}\frac{1}{k} - 1\right) \\
 
&= \frac{1}{2r+1} - \left(\sum_{k=r+1}^{3r+1}\frac{1}{k} - 1\right) \\
 
&= 1 - \left(\sum_{k=r+1}^{2r}\frac{1}{k} + \sum_{k=2r+2}^{3r+1}\frac{1}{k}\right)
 
&= 1 - \left(\sum_{k=r+1}^{2r}\frac{1}{k} + \sum_{k=2r+2}^{3r+1}\frac{1}{k}\right)
Line 56: Line 56:
 
</cmath>
 
</cmath>
 
</center>
 
</center>
−
In the above sum the fractions represent every non-zero remainder <math>\mod p</math>. Multiplying all the denominators yields a number <math>N</math> that is <math>-1 \pmod p</math>. The numerator <math>\mod p</math> is <math>N</math> times the sum of the reciprocals
+
In the above sum the denominators of the fractions represent each non-zero remainder <math>\pmod p</math> exactly once. Multiplying all the denominators yields a number <math>N</math> that is <math>p-1 \pmod p</math>. The numerator <math>\pmod p</math> is <math>N</math> times the sum of the <math>\pmod p</math> inverses of each non-zero remainder, and since this sum is <math>0 \pmod p</math>, the numerator is <math>0 \pmod p</math>. The rest of the argument is as before.
−
<math>\mod p</math> of each non-zero remainder, and since this sum is <math>0</math>, the numerator is <math>0 \pmod p</math>. The rest of the argument is as before.
+
 
 +
==See also==
 +
{{USAMO newbox|year=2010|num-b=4|num-a=6}}
 +
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 01:08, 15 June 2020

Problem

Let $q = \dfrac{3p-5}{2}$ where $p$ is an odd prime, and let

\[S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q\cdot (q+1) \cdot (q+2)}.\]

Prove that if $\dfrac{1}{p}-2S_q = \dfrac{m}{n}$ for integers $m$ and $n$, then $m-n$ is divisible by $p$.

Solution

Since $p$ is an odd prime, $p = 2r + 1$, for a suitable positive integer $r$, and consequently $q = 3r - 1$.

The partial-fraction decomposition of the general term of $S_q$ is:

\begin{align*} \frac{1}{(3k-1)3k(3k+1)} &= \frac{1}{2}\left(\frac{1}{3k-1} - \frac{2}{3k} + \frac{1}{3k+1}\right) \\ &= \frac{1}{2}\left(\frac{1}{3k-1} + \frac{1}{3k} - \frac{1}{k} + \frac{1}{3k+1}\right) \\ &= \frac{1}{2}\left[\left(\frac{1}{3k-1} + \frac{1}{3k} + \frac{1}{3k+1}\right) - \frac{1}{k}\right], \end{align*}

therefore

\begin{align*} \frac{1}{p} - 2S_q &= \frac{1}{2r+1} - \left(\sum_{k=2}^{3r+1}\frac{1}{k} - \sum_{k=1}^{r} \frac{1}{k}\right) \\ &= \frac{1}{2r+1} - \left[\left(\sum_{k=r+1}^{3r+1}\frac{1}{k}\right)- 1\right] \\ &= 1 - \left(\sum_{k=r+1}^{2r}\frac{1}{k} + \sum_{k=2r+2}^{3r+1}\frac{1}{k}\right) \\ &= 1 - \sum_{k=1}^{r}\left(\frac{1}{(2r+1) - k} + \frac{1}{(2r+1) + k}\right) \\ &= 1 - \sum_{k=1}^{r}\frac{2p}{(p - k)(p + k)} \\ &= 1 - \frac{a}{b} = \frac{b - a}{b} \end{align*}

with $a$ and $b$ positive relatively-prime integers.

Since $r < p$ and $p$ is a prime, in the final sum all the denominators are relatively prime to $p$, but all the numerators are divisible by $p$, and therefore the numerator $a$ of the reduced fraction $\frac{a}{b}$ will be divisible by $p$. Since the sought difference $m - n = (b-a) - b = -a$, we conclude that $p$ divides $m-n$ as required.

Alternative Calculation

We can obtain the result in a slightly different way:

\begin{align*} \frac{1}{p} - 2S_q &= \frac{1}{2r+1} - \left(\sum_{k=2}^{3r+1}\frac{1}{k} - \sum_{k=1}^{r} \frac{1}{k}\right) \\ &= \frac{1}{2r+1} - \left(\sum_{k=r+1}^{3r+1}\frac{1}{k} - 1\right) \\ &= 1 - \left(\sum_{k=r+1}^{2r}\frac{1}{k} + \sum_{k=2r+2}^{3r+1}\frac{1}{k}\right) \end{align*}

In the above sum the denominators of the fractions represent each non-zero remainder $\pmod p$ exactly once. Multiplying all the denominators yields a number $N$ that is $p-1 \pmod p$. The numerator $\pmod p$ is $N$ times the sum of the $\pmod p$ inverses of each non-zero remainder, and since this sum is $0 \pmod p$, the numerator is $0 \pmod p$. The rest of the argument is as before.

See also

2010 USAMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_USAMO_Problems/Problem_5&oldid=125462"