Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Math Puzzles > Nondecreasing Integer Sequence Two > Nondecreasing Integer Sequence Two
>
>		 Interesting Sum of a Nondecreasing Sequence

Let a1,a2,...,a2005 be a nondecreasing sequence of positive integers, with t defined as t=a2005.
Let bn be the smallest index, m, for which am ≥ n.
In terms of t, what is the smallest possible value of the sum a1+a2+...+a2005+b1+b2+...+bt ?
Answer: 2006t

Solution:

First, some definitions:
a1,a2,...,ap is a nondecreasing sequence of positive integers,
t is defined as t=ap,
bn is the smallest index, m, for which am ≥ n,
the sum Sp,t is defined by Sp,t=a1+a2+...+ap+b1+b2+...+bt;

I will prove by induction that Sp,t=(p+1)(t), regardless of the values of a1 through ap-1.

Proof:

The statement is true when p=1, because a1=t, and b1,b2,...,bt are all equal to 1.
So the sum of the a's is t, and the sum of the b's is also t, so S1,t=2t.

Then, in the induction step, we assume Sp,t=(p+1)(t), and introduce a new element ap+1=t+k, where k is a nonnegative integer.

Each of the b's in the range bt+1 through bt+k, of which there are zero or more, are equal to p+1, so their sum is (p+1)(k)

Sp+1,t+k=Sp,t+ap+1+bt+1+bt+2+...+bt+k
Sp+1,t+k=(p+1)(t)+(t+k)+(p+1)(k)
Sp+1,t+k=(p+2)(t+k),

proving the statement.  Letting p=2005, t=a2005, and finding Sp,t=(p+1)(t) gives you the answer.

More about this puzzle

Notice that, viewed as functions, a and b are inverses.  For example, if a(6)=7, then b(7)=6, although it's a little more complicated if, say a(5) also equals 7, then b(7)=5.  If there is no n for which a(m)=n, then b(n) is given the smallest m'>m for which a(m')≥n.

A good way to visualize this puzzle is with a bar-graph of the "a" sequence, with red bars extending upward from the horizontal "m" axis.  Then the "b" sequence is a set of blue bars extending to the right from the "n" axis.  For example,

m a(m)
1 1
2 1
3 3
4 4
5 4
6 7
7 8
8 9
n b(n)
1 1
2 3
3 3
4 4
5 6
6 6
7 6
8 7
9 8
n 
m

If we let m go from 1 to p, and we let n go from 1 to t, then, from the graph, it is clear that the sum of the a and b sequences is (p+1)t.

Relation to Young's Inequality

Let f be a real-valued, continuous, and strictly increasing function on [0,c] with c > 0. If f(0)=0, a in [0,c], and b in [0,f(c)], then

\[\int_0^af(x)dx+\int_0^bf^{-1}(y)dy\ge ab,\]

where f-1 is the inverse function of f.  Equality holds iff b=f(a).

Here, a(m), where 1≤m≤p, is the discrete analog of f(x), and b(n), where 1≤n≤t is the discrete analog of f-1(y).  In this puzzle, a(p)=t, so equality holds.

Related pages in this website

Young's Inequality is the "integral" version of this puzzle.

 

The webmaster and author of this Math Help site is Graeme McRae.