6 replies to this topic

[bushindo]

I saw this problem in a test long ago.

Assume that we have a sequence of 17 distinct integers. Show that there exist at least 1 subsequence of 5 integers that form an increasing or decreasing sequence.

For instance, let the sequence of 17 distinct integers be

9, 13,  6,  1, 11,  7, 16,  3, 15, 10,  2,  5, 12,  4, 14,  8, 17

Then there is a increasing subsequence of length 5 in (1,3,5,8,17). There is also a decreasing subsequence of (16,15,10,5,4). Show that the statement in the second paragraph is true for all sequences of 17 distinct integers.

[alanklm]

Gm.
17, 5. Strange dependence...

bushindo, Is solution simple enough?

[magician]

I think I have a solution, but if everyone else is like me, a spoiler button is like a big sign saying "click here", so I'll hold off for a bit and just give a hint.

Spoiler for something to note

note that the same relationship is true of 10 and 4...

Spoiler for bigger hint

think about perfect squares...

[superprismatic]

Spoiler for as I recall

Erdos and another settled this before I was born. I learned the theorem on my Polish mother's knee!

[bushindo]

Spoiler for as I recall

Erdos and another settled this before I was born. I learned the theorem on my Polish mother's knee!

That's some childhood you got, maybe it's a polish thing. I got mostly spanks on my mother's knee. I'll supplement the hint that magician gave earlier

Spoiler for

The same relationship applies to sequences of 4 from 10 distinct numbers (and also sequences of 3 from 5 integers ). From here, induction may be applied.

[superprismatic]

Well, it seems nobody wants to provide a proof so

Spoiler for here's mine

Although I can't see a good way to prove it using induction, I do have a fairly simple proof:

Denote the 17-long sequence by S_i for i from 1 to 17. Assume no such 5-long increasing or decreasing subsequence can be made.
Label each S_i with a pair of numbers (D_i,I_i) where D_i is the length of the longest decreasing subsequence
ending at S_i, and I_i is the length of the longest increasing subsequence ending at S_i. Now, 1 <= D_i <= 4
and 1 <= I_i <= 4 by our assumption that no 5-long can be made. So, there are only 4*4=16 possible pairs, (D_i,I_i).
But since there are 17 numbers S_i with associated labels (D_i,I_i), there must be at least one pair of duplicate labels.
So, suppose the duplicates are (D_j,I_j) and (D_k,I_k) with j<k. If S_j<S_k then the increasing
subsequence ending at S_j can have S_k appended to it, thereby making it one longer (and increasing I_k by 1). But I_k
is already as large as possible, by definition. A similar thing happens to D_k if S_j>S_k. So, duplicate labels cannot
occur, and we come to a contradiction. So our assumption that there is no 5-long increasing or decreasing subsequence must be wrong.

Edited by superprismatic, 04 January 2010 - 10:58 PM.

[bushindo]

Well, it seems nobody wants to provide a proof so

Spoiler for here's mine

Although I can't see a good way to prove it using induction, I do have a fairly simple proof:

Denote the 17-long sequence by S_i for i from 1 to 17. Assume no such 5-long increasing or decreasing subsequence can be made.
Label each S_i with a pair of numbers (D_i,I_i) where D_i is the length of the longest decreasing subsequence
ending at S_i, and I_i is the length of the longest increasing subsequence ending at S_i. Now, 1 <= D_i <= 4
and 1 <= I_i <= 4 by our assumption that no 5-long can be made. So, there are only 4*4=16 possible pairs, (D_i,I_i).
But since there are 17 numbers S_i with associated labels (D_i,I_i), there must be at least one pair of duplicate labels.
So, suppose the duplicates are (D_j,I_j) and (D_k,I_k) with j<k. If S_j<S_k then the increasing
subsequence ending at S_j can have S_k appended to it, thereby making it one longer (and increasing I_k by 1). But I_k
is already as large as possible, by definition. A similar thing happens to D_k if S_j>S_k. So, duplicate labels cannot
occur, and we come to a contradiction. So our assumption that there is no 5-long increasing or decreasing subsequence must be wrong.

That's a nice proof. I didn't think of that. Here's a clumsier proof using induction

Spoiler for

Without loss of generality, let's assume we already know that this statement is true for subsequence of length 4 from any 10 distinct integers.

Given a set of 17 distinct integers, we show that in the first 16 integers, there are 7 increasing or decreasing length-4 subsequences with different end-points. We do this by the following method

1) Select the first 10 integers, there is 1 increasing or decreasing sequence of length 4. Let the last integer of this sequence be called L₁.
2) Select the first 11 integers, and then removing L₁. We have another set of 10 integers. There is 1 increasing or decreasing subsequence with a different last integer, call this L₂.
3) Select the first 12 integers, and then removing L₁ and L₂. We have another set of 10 integers. There is 1 increasing or decreasing subsequence with a different last integer L₃.
4) Repeating step 3) up until the 16th integer, we have 7 different subsequences of length 4 with 7 different last integers.

Of these 7 subsequences, there must be 4 sequences that are of the same direction (increasing or decreasing). Without loss of generality, let's assume that we have 4 increasing sequences. Assuming no qualifying subsequence of length 5 in the first 16 integers, the last integers of these 4 increasing subsequence must form a decreasing subsequence of length 4. Consequently, when we add in the 17th integers, there is bound to be a subsequence of length 5.

I didn't feel inclined to prove the opening statement, which is that we can get subsequences of 4 out of 10 integers. But the outline above can be generalized enough to make the induction process fully rigourous.

Edited by bushindo, 05 January 2010 - 12:17 AM.