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) ....... 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  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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.