Solving Sequence Problem: Find Increasing Sequence of 11 Terms

[sylar]

In a sequence with 101 elements show that one can find an increasing sequence of 11 terms.

Here is my approach: Pick the greatest element of the sequence (or one of the largest elements if there is more than one large element) and put it onto the end of the sequence we are forming. Then make ten groups consisting of the terms of the original sequence so that each group has ten elements. Now find the least elements of each group(if there is more than one least element in a group, then choose one of them). Finally, arranging these 10 least elements in an increasing order we get an increasing sequence of 11 terms.

Is this argument sound? Or can we solve this problem in a more elegant way?

 

[Gib Z]

The statement isn't even true, though it may be if you apply stricter conditions. Take a_1 = a_2 = a_3 ... a_{101} ie a constant sequence. No increasing sequence can be made out of those.

 

[sutupidmath]

yeah, like Gib Z pointed out, that statement is not true, unless we put some further conditions, like for at least 11 terms not to be equal to each other or sth like that!

 

[sylar]

Hey guys, i think you are missing one point. The question doesn't ask us to prove that there exists a strictly increasing sequence; it asks us to show that there exists an increasing sequence. That is, if all terms are equal to each other, then we have an increasing sequence.

Here is the related Wikipedia page: http://en.wikipedia.org/wiki/Increasing_sequence

 

[CRGreathouse]

Is this argument sound?

No, I don't think so. You're not supposed to re-order the terms, are you? If you were you would need only 11 terms.

 

[matticus]

Hey guys, i think you are missing one point. The question doesn't ask us to prove that there exists a strictly increasing sequence; it asks us to show that there exists an increasing sequence. That is, if all terms are equal to each other, then we have an increasing sequence.

Here is the related Wikipedia page: http://en.wikipedia.org/wiki/Increasing_sequence

what is your definition of an increasing sequence...because a constant sequence is in no way increasing...it's constant.

 

[CRGreathouse]

I imagine the intended definition is a sequence a_1,a_2,\ldots with a_1\le a_2\le\cdots.

 

[Dragonfall]

The actual theorem goes like this: if you have 101 distinct integers in a sequence, then you will have a 11-term subsequence that is INCREASING or DECREASING (like a lot of combinatorial theorems, it guarantees A or not A).

Or rather, if you want an increasing or decreasing sequence of n+1, then you need n^2+1 numbers.

The OP's statement can't possibly be right:

101, 100, 99, 98, ..., 1.

 

[HallsofIvy]

The statement isn't even true, though it may be if you apply stricter conditions. Take a_1 = a_2 = a_3 ... a_{101} ie a constant sequence. No increasing sequence can be made out of those.

yeah, like Gib Z pointed out, that statement is not true, unless we put some further conditions, like for at least 11 terms not to be equal to each other or sth like that!

Many texts use the word "increasing" to mean what others would call "non-decreasing" and "strictly increasing" to mean what others would call "increasing". I don't particularly like that terminology myself but I wouldn't take anyone to task for it!

But sylar has clearly misunderstood the question- it's not a matter of picking out 10 numbers from the sequence and putting them into increasing order. If that were what they were asking, you can obviously take any 101 number sequence and change the order so that the entire 101 were "increasing" (non-decreasing).

DragonFall has it right. His example, 101, 100, 99, ... does not have any increasing or non-decreasing subsequence in it. The problem must be to show that you can always find a sequence of 10 numbers that is either non-decreasing or non-increasing.

 

[Dragonfall]

I was half thinking about the problem last night, and I almost worked out a sort of recursion on the general case (n+1, n^2+1); though I wasn't successful, I'm pretty sure the proof can be done by some sort of induction. I'd love to see a full proof if someone knows it.

 

[matticus]

what about the sequence 1, 3, 2, 4, 6, 5, 7, 9, 8...there is no non-increasing/decreasing sequence greater than 3 in this, no matter how far out you go.

certainly the conjecture is not true.

 

[matticus]

x_3n = 3n + 1, x_(3n + 1) = 3(n+1), x_(3n + 2) = 3n + 2. (n = 0, 1, 2...)

suppose the subsequence starts at x_3n. that means that x_3n through x_3n + 10 must either be non-decreasing or non-increasing. however, x_(3n+1) = 3n + 3 > 3n+2 = x_(3n + 2). so the subsequence is not non-decreasing. and x_(3n + 3) = x_3(n+1) = 3(n+1) + 1 = 3n + 4 > x_(3n+2). so the subsequence is not non-increasing.

starting at x_(3n + 1) and x_(3n + 2) leads to similar reasoning. But that exhausts the possibilities.

 

[Dragonfall]

It's not a conjecture, it's a theorem, and the proof must go something like this:

Given n^2+1 numbers, there is an increasing or decreasing sequence of size n+1.

True for n=1.

Now suppose it's true for all n<k.

Now given (n+1)^2+1 numbers, partition the list into n^2+1 (A) and 2n+1(B). By induction hypothesis, WLOG, there is an increasing sequence within the first part of size n+1. Now if any of B is greater than the last element of one such sequence then we are done. Otherwise,

SOMETHING HAPPENS HERE.

QED.

 

[Dragonfall]

x_3n = 3n + 1, x_(3n + 1) = 3(n+1), x_(3n + 2) = 3n + 2. (n = 0, 1, 2...)

suppose the subsequence starts at x_3n. that means that x_3n through x_3n + 10 must either be non-decreasing or non-increasing. however, x_(3n+1) = 3n + 3 > 3n+2 = x_(3n + 2). so the subsequence is not non-decreasing. and x_(3n + 3) = x_3(n+1) = 3(n+1) + 1 = 3n + 4 > x_(3n+2). so the subsequence is not non-increasing.

starting at x_(3n + 1) and x_(3n + 2) leads to similar reasoning. But that exhausts the possibilities.

A subsequence does not need to consist of consecutive elements of the sequence.

1 3 5 7 is a subsequence of 1 2 3 4 5 6 7

 

[HallsofIvy]

what about the sequence 1, 3, 2, 4, 6, 5, 7, 9, 8...there is no non-increasing/decreasing sequence greater than 3 in this, no matter how far out you go.

certainly the conjecture is not true.

No, the conjecture, as DragonFall restated it, was to find either a non-decreasing or non-increasing sub-sequence (not required to be consecutive): 1, 2, 6, etc. gives an increasing sequence.

The original statement was simply for an increasing sub-sequence. That certainly applies here.

 

[sylar]

Sorry for the delayed response. First, i want to thank all the posters who commented on these problem. Second, i admit that i misunderstood the problem and what i wrote here was not true. (Though still I'm right with the definition of an increasing sequence) The statement to prove is: In a sequence of (n^2)+1 distinct elements, there exists an increasing or decreasing subsequence of length n+1.

Our instructor asks questions at the end of the lectures just for fun and this was one of these problems. Yesterday, he told me that this is a very nice problem and he didn't know about it before he saw the proof in a mathematics journal. He added that the proof method was strong induction.

So if you prove the statement or see the proof somewhere, can you post here please? Thanks.