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 
your help.

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/