Associated Topics || Dr. Math Home || Search Dr. Math

### Increasing and Decreasing Subsequences; Pigeonhole Principle

```
Date: 03/21/2000 at 10:52:52
From: Elizabeth
Subject: Pigeonhole Principle

I've been stuck on this problem for several days and would appreciate

Consider a list of (n^2)+1 distinct integers. Show/Prove there exists
an increasing OR decreasing subsequence of length at least n+1.

Ex. n = 2 so sequence has length of ((2^2)+1) = 5 and has an
increasing or decreasing subsequence of length (2+1) = 3; so if the
sequence is 4, 1, 2, 3, 5; an increasing subsequence is 1, 2, 3 or 1,
2, 5. If the sequence is 5, 2, 3, 1, 4, an increasing subsequence is
2, 3, 4 and a decreasing subsequence is 5, 3, 1 or 5, 2, 1.

Hint: You can use the Pigeonhole Principle to prove this.

P.S. I'm sure you know what the Pigeonhole Principle is, but just in
case you don't: If you have n pigeonholes and more than n pigeons,
then at least two pigeons must be assigned to the same pigeonhole.

Thank you for your time and consideration, it is greatly appreciated.
```

```
Date: 03/22/2000 at 11:31:11
From: Doctor Wilkinson
Subject: Re: Pigeonhole Principle

This is a very pretty problem, Elizabeth. I don't think much of the
hint, however. I think you should prove this any way you can, and
although I maybe missing something, I don't think the pigeonhole
principle fits the problem very well.

What seems clear is that you want to use induction in some way. I'm
going to give you a useful hint and let you see whether you can get
anywhere with it. If you're still stuck, please get back to me.

When you're doing a proof by induction, you have the power of the
induction hypothesis to work with, so sometimes you can actually make
things easier by proving something more general. In this case, I
suggest a trick that we might call "breaking the symmetry." There is a
sort of bogus symmetry in the problem between the increasing and
decreasing subsequences. Let's look at the following generalization:

Consider a list of mn+1 distinct integers. Show/Prove there exists an
increasing sequence of length m+1 or a decreasing sequence of length
n+1.

(The theorem in the original problem is just the case m = n.)

Let's try to prove this by induction on m. Right away something very
exciting happens, because the case m = 1 is really easy. This suggests
that we may be on the right track.

I'm going to let you try to see whether you can do the induction step.
I'm ready with another hint if you have trouble.

- Doctor Wilkinson, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 03/22/2000 at 11:51:47
From: Doctor Anthony
Subject: Re: Pigeonhole Principle

Let the sequence be represented by a(1), a(2), ..., a(n^2+1).

I shall suppose that there is no increasing subsequence of length n+1
and show that there then MUST be a decreasing subsequence of length
n+1.

For each k = 1, 2, 3, ..., n^2+1 let m(k) be the length of the longest
increasing subsequence which begins with a(k).

Suppose that m(k) <= n for all k. (i.e. no increasing subsequence of
length n+1 or greater)

However  m(k) >= 1 for all k (i.e. we can have increasing subsequences
of length 1 up to n)

It follows that the numbers m(1), m(2), ..., m(n^2+1) are n^2+1
integers that each lie in the range 1 to n.

By the pigeonhole principle, n+1 of the numbers m(1), m(2), ...,
m(n^2+1) are equal.

[For example if n = 3, n^2+1 = 10, n+1 = 4. Then 10 integers each
lying in the range 1 to 3 MUST have 4 of these integers equal. In the
worst case the numbers would be 1, 2, 3, 1, 2, 3, 1, 2, 3, 1 and as
you can see there are 4 1's, and if the last entry were the digit 2 or
3 there would be 4 of those digits.]

So we assume that m(k1) = m(k2) = m(k3) = ... = m(k(n+1))

Suppose that for some i for i = 1 to n, a(ki) < a((k+1)i)  .......[1]

Then since ki < k(i+1), we could take a longest increasing subsequence
beginning with a((k+1)i) and put a(ki) in front to obtain an
increasing subsequence beginning with a(ki). Since this implies that

m(ki) > m((k+1)i)

(which is not allowed, they are equal) we conclude that

a(ki) > a(k(i+1))

which is contrary to [1] above.

Since this is true for each i from i = 1 to n, we have

a(k1) > a(k2) > ... > a(k(n+1))

and we conclude that a(k1), ak2), a(k3), ..., a(k(n+1)) is a
decreasing subsequence of length n+1.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 03/22/2000 at 15:01:48
From: Elizabeth
Subject: Re: Pigeonhole Principle

Dr. Math,

I sort of understand what you are saying, but for one of your examples
you did not use distinct integers (like 1, 1, 1, 2, 2, ...). You also
proved that there is a decreasing subsequence, so would I prove there
is an increasing subsequence in the same manner?

Thanks,
Elizabeth
```

```
Date: 03/22/2000 at 15:36:59
From: Doctor Anthony
Subject: Re: Pigeonhole Principle

I'm afraid you have misunderstood the reasoning in my answer. The
numbers that were equal were NOT the numbers a(k) of the sequence
(which are all different), but the numbers m(k) which are the LENGTH
OF INCREASING SUBSEQUENCES starting at a(k). It will require careful
thought to understand the reasoning (like so many ideas in number
theory) so work through it slowly using an example with, say n = 3,
giving a sequence of 10 DIFFERENT numbers. You will find that the
ideas then begin to make sense.

On your second point, the theorem states that there must be an
increasing OR decreasing subsequence of length n+1. Obviously if you
start with the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, then you do
not have a decreasing subsequence of length 4. To prove the case I
took as a fact that my sequence a(k) did not have an increasing
subsequence of length n+1 and from that assumption proved that it must
then necessarily have a decreasing subsequence of length n+1.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 03/23/2000 at 12:28:32
From: Elizabeth
Subject: Re: Pigeonhole Principle

Dr. Math:

I understand how to approach the induction, but I am not sure of what
my induction hypothesis should be and my induction step from there.

Thanks,
Elizabeth
```

```
Date: 03/23/2000 at 16:49:59
From: Doctor Wilkinson
Subject: Re: Pigeonhole Principle

Hi, again. It seems that Dr. Anthony has found a way to use the
pigeonhole principle after all, but since you ask about the induction
proof I will assume you're still interested in this approach.

My version of the theorem is that if m and n are positive integers,
then any sequence of mn+1 distinct integers must contain either an
increasing subsequence of length m+1 or a decreasing subsequence of
length n+1.

If m = 1, this is easy, because if there is no increasing sequence of
length 2, then the entire sequence must be decreasing.

So suppose the result holds for m = k, and let us try to prove it for
m = k+1. So we have a sequence of (k+1)n+1 or kn+n+1 distinct
integers, and we want to show that it must contain either an
increasing subsequence of length k+2 or a decreasing subsequence of
length n+1.

Now I'm going to look at a special set of terms of the sequence,
namely those terms with the property "everything to the left is
larger." For example, the first term of the sequence always has this
property, since there is nothing to the left. In the sequence 5, 3, 7,
4, 1, 2, 9 the terms with this property are the first term (5), the
second term (3), and the fifth term (1).

Now the terms with this property clearly form a decreasing sequence.
If there is no decreasing sequence of length n+1, then there can be at
most n of these terms. Now pluck these terms out. You must have at
least kn+1 terms remaining, and now you can apply the induction
hypothesis. At this point you're almost home; see if you can finish it
up.

- Doctor Wilkinson, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search