Art of Problem Solving
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

1989 USAMO Problems/Problem 1: Difference between revisions

← Older editNewer edit →
cleanup
revised solution
Line 1: Line 1:
== Problem ==
== Problem ==
For each positive [[integer]] <math>n</math>, let
For each positive [[integer]] <math>n</math>, let
<div style="text-align:center;">
<cmath> \begin{align*}
<math>S_n = 1 + \frac 12 + \frac 13 + \cdots + \frac 1n</math>
S_n &= 1 + \frac 12 + \frac 13 + \cdots + \frac 1n \\
 
T_n &= S_1 + S_2 + S_3 + \cdots + S_n \\
<math>T_n = S_1 + S_2 + S_3 + \cdots + S_n</math>
U_n &= \frac{T_1}{2} + \frac{T_2}{3} + \frac{T_3}{4} + \cdots + \frac{T_n}{n+1}.
 
\end{align*} </cmath>
<math>U_n = \frac{T_1}{2} + \frac{T_2}{3} + \frac{T_3}{4} + \cdots + \frac{T_n}{n+1}</math>.
</div>
Find, with proof, integers <math>0 < a,\ b,\ c,\ d < 1000000</math> such that <math>T_{1988} = a S_{1989} - b</math> and <math>U_{1988} = c S_{1989} - d</math>.
Find, with proof, integers <math>0 < a,\ b,\ c,\ d < 1000000</math> such that <math>T_{1988} = a S_{1989} - b</math> and <math>U_{1988} = c S_{1989} - d</math>.


== Solution ==
== Solution ==
If we re-group the terms of <math>T_{n-1}</math>,


We note that for all integers <math>n \ge 2</math>,
<cmath>\begin{align*}
<cmath>\begin{align*}
T_{n-1} &= \left(1\right) + \left(1 + \frac 12\right) + \left(1 + \frac 12 + \frac 13\right) + \ldots + \left(1 + \frac 12 + \frac 13 + \ldots + \frac 1{n-1}\right) \\  
T_{n-1} &= 1 + \left(1 + \frac 12\right) + \left(1 + \frac 12 + \frac 13\right) + \ldots + \left(1 + \frac 12 + \frac 13 + \ldots + \frac 1{n-1}\right) \\  
&= \sum_{i=1}^{n-1} \left(\frac {n-i}i\right) = n\left(\sum_{i=1}^{n-1} \frac{1}{i}\right) - (n-1) = n\left(\sum_{i=1}^{n} \frac{1}{i}\right) - n \\
&= \sum_{i=1}^{n-1} \left(\frac {n-i}i\right) = n\left(\sum_{i=1}^{n-1} \frac{1}{i}\right) - (n-1) = n\left(\sum_{i=1}^{n} \frac{1}{i}\right) - n \\
&= n \cdot S_{n} - n\end{align*}</cmath>
&= n \cdot S_{n} - n .
\end{align*}</cmath>


Thus, for <math>n = 1989</math>, <math>T_{1988} = 1989 S_{1989} - 1989 \Longrightarrow \boxed{a = b = 1989}</math>.
It then follows that
<cmath>\begin{align*}
U_{n-1} &= \sum_{i=2}^{n} \frac{T_{i-1}}{i} = \sum_{i=2}^{n}\ (S_{i} - 1) = T_{n-1} + S_n - (n-1) - S_1 \\
&= \left(nS_n - n\right) + S_n - n = (n + 1)S_n - 2n .
\end{align*}</cmath>


For the second part, applying this result gives
If we let <math>n=1989</math>, we see that <math>(a,b,c,d) = (1989,1989,1990, 2\cdot 1989)</math> is a suitable solution.  <math>\blacksquare</math>


<cmath>\begin{align*}U_{n-1} &= \sum_{i=2}^{n} \frac{T_{i-1}}{i} = \sum_{i=2}^{n}\ (S_{i} - 1) = T_{n-1} + S_n - (n-1) - S_1\\
&= \left(nS_n - n\right) + S_n - n = (n + 1)S_n - 2n\end{align*}</cmath>


For <math>n = 1989</math>, we get that <math>\boxed{c = 1990, d = 2 \cdot 1989 = 3978}</math>.
{{alternate solutions}}


== See also ==
== See also ==
{{USAMO box|year=1989|before=First question|num-a=2}}
{{USAMO box|year=1989|before=First question|num-a=2}}
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=356633#p356633 Discussion on AoPS/MathLinks]


[[Category:Olympiad Algebra Problems]]
[[Category:Olympiad Algebra Problems]]

Revision as of 16:57, 11 January 2008

Problem

For each positive integer $n$, let \begin{align*} S_n &= 1 + \frac 12 + \frac 13 + \cdots + \frac 1n \\ T_n &= S_1 + S_2 + S_3 + \cdots + S_n \\ U_n &= \frac{T_1}{2} + \frac{T_2}{3} + \frac{T_3}{4} + \cdots + \frac{T_n}{n+1}. \end{align*} Find, with proof, integers $0 < a,\ b,\ c,\ d < 1000000$ such that $T_{1988} = a S_{1989} - b$ and $U_{1988} = c S_{1989} - d$.

Solution

We note that for all integers $n \ge 2$, \begin{align*} T_{n-1} &= 1 + \left(1 + \frac 12\right) + \left(1 + \frac 12 + \frac 13\right) + \ldots + \left(1 + \frac 12 + \frac 13 + \ldots + \frac 1{n-1}\right) \\ &= \sum_{i=1}^{n-1} \left(\frac {n-i}i\right) = n\left(\sum_{i=1}^{n-1} \frac{1}{i}\right) - (n-1) = n\left(\sum_{i=1}^{n} \frac{1}{i}\right) - n \\ &= n \cdot S_{n} - n . \end{align*}

It then follows that \begin{align*} U_{n-1} &= \sum_{i=2}^{n} \frac{T_{i-1}}{i} = \sum_{i=2}^{n}\ (S_{i} - 1) = T_{n-1} + S_n - (n-1) - S_1 \\ &= \left(nS_n - n\right) + S_n - n = (n + 1)S_n - 2n . \end{align*}

If we let $n=1989$, we see that $(a,b,c,d) = (1989,1989,1990, 2\cdot 1989)$ is a suitable solution. $\blacksquare$


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See also

1989 USAMO (Problems • Resources)
Preceded by
First question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_USAMO_Problems/Problem_1&oldid=22326"