Calculus rather than inequalities

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Calculus rather than inequalities

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: German TST, IMO ShortList 2003, algebra problem 3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#1 h Jul 15, 2004, 9:00 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Consider pairs of the sequences of positive real numbers $a_1\geq a_2\geq a_3\geq\cdots,\qquad b_1\geq b_2\geq b_3\geq\cdots$ and the sums $A_n = a_1 + \cdots + a_n,\quad B_n = b_1 + \cdots + b_n;\qquad n = 1,2,\ldots.$ For any pair define $c_n = \min\{a_i,b_i\}$ and $C_n = c_1 + \cdots + c_n$ , $n=1,2,\ldots$ .

(1) Does there exist a pair $(a_i)_{i\geq 1}$ , $(b_i)_{i\geq 1}$ such that the sequences $(A_n)_{n\geq 1}$ and $(B_n)_{n\geq 1}$ are unbounded while the sequence $(C_n)_{n\geq 1}$ is bounded?

(2) Does the answer to question (1) change by assuming additionally that $b_i = 1/i$ , $i=1,2,\ldots$ ?

Justify your answer.

This post has been edited 2 times. Last edited by djmathman, May 27, 2018, 3:38 PM
Reason: overhauled problem wording to fit https://anhngq.files.wordpress.com/2010/07/imo-2003-shortlist.pdf

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12096 posts

jmerry

#2 h Jul 16, 2004, 9:37 PM • 6 Y

Y by Adventure10, Mango247, ehuseyinyigit, and 3 other users

I'm surprised this was a high school contest problem.

For convenience, let the sequences be nonincreasing rather than strictly decreasing- we can always tweak them after the fact without changing the convergence of the series.
(a) Yes. An example:
Let $r_0=0$ , $r_1=1$ , $r_2=1+2^1$ , $r_3=r_2+2^3$ , ..., $r_{n+1}=r_n+2^{\frac{n(n+1)}{2}}$ .
Let $a_1=1$ , $a_k=2^{-3}$ if $r_1<k \le r_3$ , $a_k=2^{-m(2m+1)}$ if $r_{2m-1}< k \le r_{2m+1}$ .
Let $b_k=2^{-1}$ if $0<k \le r_2$ , $b_k=2^{-m(2m-1)}$ if $r_{2m-2}< k \le r_{2m}$ .
Then $c_k=2^{-\frac{n(n+1)}{2}}$ if $r_{n-1}<k \le r_n$ and
$\displaystyle \sum_{k=1}^{\infty}c_k = \sum_{j=0}^{\infty} \sum_{k=r_j+1}^{r_{j+1}} 2^{-\frac{(j+1)(j+2)}{2}} = \sum_{j=0}^{\infty} \sum_{k=r_j+1}^{r_{j+1}} 2^{-\frac{j(j+1)}{2}}\cdot 2^{-(j+1)} = \sum_{j=0}^{\infty} 2^{-(j+1)} = 1$

On the other hand $\displaystyle \sum_{k=1}^{r_{2n-1}}a_k > \sum_{j=0}^{n-1} \sum_{k=r_{2j}+1}^{r_{2j+1}}a_k = \sum_{j=0}^{n-1} \sum_{k=r_{2j}+1}^{r_{2j+1}}2^{-j(2j+1)} = \sum_{j=0}^{n-1} 1 = n$
and
$\displaystyle \sum_{k=1}^{r_{2n}}b_k > \sum_{j=1}^n \sum_{k=r_{2j-1}+1}^{r_{2j}}b_k = \sum_{j=1}^{n} \sum_{k=r_{2j-1}+1}^{r_{2j}}2^{-j(2j-1)} = \sum_{j=1}^n 1 = n$
Each series $\sum_k a_k$ and $\sum_k b_k$ diverge, while $\sum_k \min(a_k,b_k)$ converges.

(b)The answer changes: $\sum_k c_k$ must diverge.
Case 1. Suppose that for all $k \ge N$ , $a_k < \frac{1}{k}$ .
Then $\displaystyle \sum_{k=N}^{\infty} c_k = \sum_{k=N}^{\infty} a_k$ diverges by divergence of $\sum_k a_k$ .
Case 2. There exist infinitely many $m$ such that $a_m \ge \frac{1}{m}$
Let $m_n$ be an infinite sequence with $m_{n+1} \ge 2m_n$ and $a_{m_n} \ge \frac{1}{m_n}$ for all $n \ge 1$ (with $m_0=0$ ). Then $c_{m_n}=\frac{1}{m_n}$ , so
$\displaystyle \sum_{k=1}^{m_n} c_k = \sum_{j=0}^{n-1} \sum_{k=m_j+1}^{m_{j+1}} c_k \ge \sum_{j=0}^{n-1} \sum_{k=m_j+1}^{m_{j+1}} \frac{1}{m_{j+1}} \ge \sum_{j=0}^{n-1}\frac{m_{j+1}-m_j}{m_{j+1}} \ge \sum_{j=0}^{n-1} \frac{1}{2} = \frac{n}{2}$
and $\sum_k c_k$ diverges.
These two case exhaust all possibilities, and we are done.

This post has been edited 2 times. Last edited by darij grinberg, Oct 27, 2018, 8:22 PM
Reason: latex fix

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1343 posts

jgnr

#3 h Jun 19, 2011, 7:04 AM • 2 Y

Y by yojan_sushi, Adventure10

I think I've got another construction for (a), but it's somewhat difficult to explain.

$(a_k)=\boxed{\frac12,\frac12},\frac18,\frac1{16},\frac1{32},\frac1{64},\boxed{\underbrace{\frac1{64},\frac1{64},\ldots,\frac1{64}}_{64times}},\frac1{2^{71}},\frac1{2^{72}},\ldots$

${(b_k)=\frac12,\frac14,\boxed{\frac14,\frac14,\frac14,\frac14},\frac1{128},\frac1{256},\ldots,\frac1{2^{70}},\boxed{\underbrace{\frac1{2^{70}},\frac1{2^{70}},\ldots,\frac1{2^{70}}}_{2^{70}times}}},\ldots$

The boxed blocks are terms whose sum is 1, so $(A_k)$ and $(B_k)$ are clearly unbounded. Since $c_i=\frac1{2^i}$ , then $(C_k)$ is bounded.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1276 posts

va2010

#4 h Apr 1, 2015, 5:05 PM • 3 Y

Y by Adventure10, Mango247, Ritwin

I'd like to point out that fedja posted a beautiful solution here

fedja wrote:

This question is asked now and then. The answer is that the series with the maxima in the denominators can converge despite both initial series diverge and the reason is exactly as you put it: ak and bk can overtake each other infinitely many times and accumulate large sums when at rest from the work as maxima. Formalizing it isn't hard and did did an excellent job in this respect. The question is whether we can make it "obvious", i.e., to see it in our heads without touching pen or paper at all. Of course, we can talk about decreasing sequences ak,bk>0 and consider ∑kmin(ak,bk). Now just imagine two people walking. The condition is that neither of them is allowed to increase his speed at any time and that the slowest one carries a stick, which is magically teleported to the other person when he becomes slower. The question is whether both people can walk to infinity while the stick will travel only finite distance on foot. Now the strategy should become clear. Fix any upper bound v for speeds and any upper bound d for the distance the stick is allowed to travel on foot. Let the first person walk at speed v until he goes the distance 1. The second person should crawl slowly (but steadily) all that time at the speed dv/2, so he travels only distance d/2 with the stick. At that moment, the first person slows down enormously to the speed d2v/4, so while the second person continues to go at the speed dv/2 and moves distance 1, the first person (who now has the stick) goes only d/2. By the end of this cycle, both people moved by at least 1 but the stick traveled only distance d on foot. We also end up with the new bound for the speed, which is vd2/4. Now repeat the cycles making the allowed distances for the stick smaller and smaller so that the corresponding series converges. We do not care how fast the speed bounds decay because no matter what the bound is, we still can cover the unit distance in some finite time. During each cycle, each person moves by distance 1 or more, so both ultimately walk away. However, the stick goes only finite distance on foot.

Also, see NIMO Winter Contest 2013.6 for an equivalent problem.

This post has been edited 1 time. Last edited by va2010, Apr 1, 2015, 5:06 PM
Reason: added links to NIMO problem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1276 posts

va2010

#5 h May 25, 2015, 3:55 PM • 2 Y

Y by Adventure10, Ritwin

The main idea behind a good deal of these constructions is that the monotonically decreasing condition can be dropped. Indeed, this is because we can divide terms into a bunch of very close but decreasing terms. Then fedja's construction becomes clear: take $d = 1.5$ and take the sums:

$1 + \frac{d}{4} + 1 + \frac{d}{16} \cdots$ which obviously diverges and
$\frac{d}{2} + 1 + \frac{d}{8} + 1 \cdots$ which also diverges. But when you take the minimum, you get

$\frac{d}{2} + \frac{d}{4} + \frac{d}{8} + \frac{d}{16} \cdots = d$ , which is convergent. A very nice problem, and an even nicer solution!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

688 posts

#6 h Apr 30, 2017, 9:28 PM • 1 Y

Y by Adventure10

This post has been edited 5 times. Last edited by Shaddoll, Apr 30, 2017, 9:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1576 posts

#7 h Dec 28, 2019, 1:56 AM • 1 Y

Y by Adventure10

1) Yes. We define $\{c_i\}=\frac{1}{2^i}$ , and partition $\{a_i\}$ and $\{b_i\}$ into C-runs, which are contiguous blocks of terms equal to the corresponding terms in $\{c_i\}$ , and leeks, which are everything else. Note that the C-runs in $\{a_i\}$ and $\{b_i\}$ are disjoint, and perfectly cover $\{c_i\}$ . Now, we recursively define $a,b$ as follows: After a C-run which ends with $\frac{1}{2^i}$ , construct a leek which consists of $2^i$ copies of $\frac{1}{2^i}$ while the other sequence has its own C-run. The first few terms, for example, are as follows: $\{a_i\}=\underline{\frac{1}{2}},\frac{1}{2},\frac{1}{2},\underline{\frac{1}{16},\frac{1}{32},\frac{1}{64},\frac{1}{128},\frac{1}{256},\cdots}\\$ $\{b_i\}=\frac{1}{2},\underline{\frac{1}{4},\frac{1}{8}},\hspace{0.18cm}\frac{1}{8},\hspace{0.18cm}\frac{1}{8},\hspace{0.18cm}\frac{1}{8},\hspace{0.3cm}\frac{1}{8},\hspace{0.3cm}\frac{1}{8}\cdots$ where the C-runs are underlined. This way, $A_n,B_n$ are both unbounded, since each leek adds $1$ to the cumulative sum, however $C_n$ is bounded by 1.

2) The answer is no. Note that $\{b_i\}$ must have infinitely many C-runs, or else $A_i$ and $C_i$ will have the same convergence. Now, define the sequence $\{x_i\}$ to be the indices of the ends of all the C-runs in $\{b_i\}$ . Note that $c_{i}\ge \frac{1}{x_j}\forall 1\le i\le x_j$ , so $C_{x_j}-C_{x_k}\ge\frac{x_j-x_k}{x_j}=1-\frac{x_k}{x_j}$ . As the $\{x_i\}$ are unbounded, construct a subsequence $\{y_i\}$ such that $y_n\ge 2y_{n-1}$ . Now, we have $C_{y_n}\ge \sum_{i=2}^n C_{y_i}-C_{y_{i-1}}\ge \sum_{i=2}^n 1-\frac{y_{n-1}}{y_n}\ge \frac{n-1}{2}$ So, $C_i$ is unbounded.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

everythingpi3141592

83 posts

everythingpi3141592

#8 h Jan 16, 2024, 4:02 PM

Y by

Could someone tell what is the motivation behind the construction in the first part? I tried to construct by taking $a_1 = 1$ and $b_1 = 100$ , and continually reducing $b$ by $1$ and keeping $a$ constant untill we reach $(1, 1)$ . And then, we further reduce $b$ , untill we repeat the same procedure, but by continually reducing $a$ by some number untill again, $b$ become $100$ times $a$ . What general strategies did people use to find the powers of $2$ solution?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3783 posts

vsamc

#9 h May 26, 2024, 3:31 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7578 posts

#10 h May 27, 2024, 5:25 PM

Y by

solved very nice but i read the solution and stuff at first so im gonna come back and review in the future

First we solve the first part. The idea is to choose $\{c_n\}:=\left\{2^{-1},2^{-2},\dots,\right\}$ and then choose
$\{a_n\}:=\left\{2^{-1},2^{-1},2^{-3},2^{-4},2^{-5},2^{-5},\dots,2^{-5},\dots,\right\}$ $\{b_n\}:=\left\{2^{-1},2^{-2},2^{-2},2^{-2},2^{-2},2^{-6},\dots,2^{-36},\dots,\right\}$ in which both $\{a_n\}$ and $\{b_n\}$ contain infinitely many runs of identical fractions summing to $1$ and therefore have divergent $A_n$ and $B_n$ .

Now we prove that the second part is impossible. Consider the set $S$ of indices $i$ where $a_i\ge b_i$ . Define $T$ to be the set of indices $i$ where $a_i\le b_i$ . The sum of all $a_i$ for $i\in T$ is convergent due to convergence of $C_n$ . Hence the sum of all $a_i$ for $i\in S$ is divergent.

Split the indices of $S$ into runs of consecutive values $[d_i+1,d_i+r_i]$ . If $d_1=0$ then ignore the first run; it will not affect the solution. For $j\in [d_i+1,d_i+r_i]$ we have
$a_j\le a_{d_i}\le b_{d_i}=\frac{1}{d_i}.$

Now notice
$\frac{1}{d_i+1}+\dots+\frac{1}{d_i+r_i}=\ln(d_i+r_i)-\ln(d_i)+O(1)$ is convergent, thus $\frac{d_i+r_i}{d_i}\le M$ for some constant $M$ .

Now notice
$M\sum_{j=1}^{r_i}\frac{1}{d_i+j}\ge \frac{d_i+r_i}{d_i}\sum_{j=1}^{r_i}\frac{1}{d_i+j}\ge \sum_{j=1}^{r_i}\frac{1}{d_i}\ge \sum_{j=1}^{r_i}a_{d_i+j}$ and summing over all $i$ yields a convergent value on the LHS and a divergent value on the RHS, a contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1664 posts

awesomeming327.

#11 h Jun 10, 2024, 2:24 PM

Y by

Define the following sequence recursively: $s_1=1$ , $s_n=s_{n-1}+2^{s_{n-1}}$ for all $n\ge 2$ . Define $t_n$ to be the nonnegative integer $k$ such that $s_{k}<t_n\le s_{k+1}$ where $s_0$ is defined as $0$ . Then, define
$a_i=\begin{cases} \frac{1}{2^n}, & \text{if $t_n$ odd}\\ \frac{1}{2^{s_{t_n}}}, & \text{if $t_n$ even} \end{cases}$ and define
$b_i=\begin{cases} \frac{1}{2^n}, & \text{if $t_n$ even}\\ \frac{1}{2^{s_{t_n}}}, & \text{if $t_n$ odd} \end{cases}$ Note that $s_{t_n}<n$ so $c_n=2^-n$ for all $n$ . Thus, $C_n\le 1$ for all $n$ . However,
$A_{s_{2k}}\ge \sum_{j=1}^{k}{\sum_{t_n=2j}{\frac{1}{2^{s_{t_{n}}}}}}$ The number of values $n$ such that $t_n=2j$ is $s_{2j+1}-s_{2j}=2^{s_{t_n}}$ , therefore
$\sum_{t_n=2j}{\frac{1}{2^{s_{t_{n}}}}}= 1$ so $A_{s_{2k}}\ge k$ is unbounded. Similarly, $B$ is unbounded.

$~$
Redefine $s$ so that $a_n<b_n$ if and only if $t_n$ is odd. If $t$ is bounded then $C$ has the same convergence as either $A$ or $B$ . If $t$ is unbounded,
$C_{s_k}\ge \sum_{j=1}^{k}{\frac{s_{k+1}-s_k}{s_{k+1}+1}}=k-\sum_{j=1}^{k}{\frac{s_k+1}{s_{k+1}+1}}$ and it is easy to see why this is unbounded.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

243 posts

pie854

#12 h Oct 4, 2024, 1:05 PM

Y by

darij grinberg wrote:

Consider pairs of the sequences of positive real numbers $a_1\geq a_2\geq a_3\geq\cdots,\qquad b_1\geq b_2\geq b_3\geq\cdots$ and the sums $A_n = a_1 + \cdots + a_n,\quad B_n = b_1 + \cdots + b_n;\qquad n = 1,2,\ldots.$ For any pair define ${\color{red}c_n = \min\{a_i,b_i\}}$ and $C_n = c_1 + \cdots + c_n$ , $n=1,2,\ldots$ .

(1) Does there exist a pair $(a_i)_{i\geq 1}$ , $(b_i)_{i\geq 1}$ such that the sequences $(A_n)_{n\geq 1}$ and $(B_n)_{n\geq 1}$ are unbounded while the sequence $(C_n)_{n\geq 1}$ is bounded?

(2) Does the answer to question (1) change by assuming additionally that $b_i = 1/i$ , $i=1,2,\ldots$ ?

Justify your answer.

I think there's a typo. Should be $c_i$ in the colored text.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7578 posts

#13 h Saturday at 8:39 PM

Y by

oops i should have gotten this its ok i guess

Part 1.
The answer is yes. Consider the following:
$\{A_n\}=\left\{\frac{1}{2^0}, c_2,c_3,\frac{1}{2^3}, \frac{1}{2^3},\frac{1}{2^3},\frac{1}{2^3},\frac{1}{2^3}, \frac{1}{2^3},\frac{1}{2^3},\frac{1}{2^3},\dots\right\}$ $\{B_n\}=\left\{c_1, \frac{1}{2^1},\frac{1}{2^1},c_4,c_5,c_6,c_7,c_8,c_9,c_{10},c_{11},\dots\right\}$ where $c_n=\frac{1}{2^n}$ . Three things hold: we have $c_n=\min\{a_n,b_n\}$ , we have $a_1\ge a_2\ge \dots$ and $b_1\ge b_2\ge \dots$ , and the sums of $\{A_n\}$ and $\{B_n\}$ are divergent as each set contains infinitely many consecutive groups of identical terms summing to $1$ .

Part 2.
The answer is no. (This makes sense intuitively, since the convergence of sequence $C$ in the first part was allowed because the sequences $A$ and $B$ decreased so quickly; here, sequence $B$ decreases at quite a slow rate.)

..so how to start? The sequence $A$ must have some values smaller than those in sequence $B$ , and some values larger. We'd like to create a contradiction; that is, show that sequence $C$ has infinite sum.

How do we show that sequence $C$ has infinite sum? The easiest way is the one that has been used in the first part already: to find infinitely many long subsequences of sequence $C$ , each with a finite sum, so that the total of all the subsequences is infinite.

How do we do that? Let's say that we've found several of these subsequences already, and our "pointer" (the next element that is past all of the previous subsequences) is at $c_N$ . We'd like to find an element $c_M$ so that $c_N+\dots+c_M$ is a finite, "predictable" (doesn't keep decreasing, for example, since an infinite geometric series wouldn't give us the desired contradiction) sum.

So how do we find such an element $c_M$ ? Let's first create an inequality: $c_N+\dots+c_M\ge \ell c_M$ , where $\ell=M-N+1$ . What's the other information we have? Well, there are infinitely many $c_M=\frac{1}{M}$ , since otherwise the sum of all $c_M$ for large $M$ becomes equal to the sum of all $a_M$ , which isn't allowed.

Small point to mention: why do we choose $c_M=\frac{1}{M}=b_M$ ? Well, this is the only information we've been given, and it should intuitively yield something important as the denominator of $M$ is a linear variable, in a sense, just like $\ell$ . If we try to choose a $c_M=a_M$ , in addition, we end up with $c_M\le \frac{1}{M}$ , which is actually "worse" to use compared to $c_M=\frac{1}{M}$ , since we're trying to make $\ell c_M$ as large as possible.

Okay, so now we just need to show that, for a fixed $N$ , there exists some large $M$ where the resultant $\ell c_M$ sum (and the ones after it) will all combine together and diverge. We have:
$\ell c_M=\frac{M-N+1}{M}$ and by choosing $M>>N$ we can make this close to $1$ . That solves the problem, as we've just found a subsequence with sum equal to $1-\epsilon$ and can do this process infinitely, so that the sum of sequence $C$ is divergent. Nice

unfortunately wasn't able to solve this but typing it out like this helps I think coolio time to lock in $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a