BrainDen.com - Brain Teasers
• 0

## Question

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.

## 6 answers to this question

• 0

Gm.

17, 5. Strange dependence...

bushindo, Is solution simple enough?

##### Share on other sites
• 0

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.

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

##### Share on other sites
• 0

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

##### Share on other sites
• 0

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

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.

##### Share on other sites
• 0

Well, it seems nobody wants to provide a proof so

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 Si for i from 1 to 17. Assume no such 5-long increasing or decreasing subsequence can be made.

Label each Si with a pair of numbers (Di,Ii) where Di is the length of the longest decreasing subsequence

ending at Si, and Ii is the length of the longest increasing subsequence ending at Si. Now, 1 <= Di <= 4

and 1 <= Ii <= 4 by our assumption that no 5-long can be made. So, there are only 4*4=16 possible pairs, (Di,Ii).

But since there are 17 numbers Si with associated labels (Di,Ii), there must be at least one pair of duplicate labels.

So, suppose the duplicates are (Dj,Ij) and (Dk,Ik) with j<k. If Sj<Sk then the increasing

subsequence ending at Sj can have Sk appended to it, thereby making it one longer (and increasing Ik by 1). But Ik

is already as large as possible, by definition. A similar thing happens to Dk if Sj>Sk. 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

##### Share on other sites
• 0

Well, it seems nobody wants to provide a proof so

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 Si for i from 1 to 17. Assume no such 5-long increasing or decreasing subsequence can be made.

Label each Si with a pair of numbers (Di,Ii) where Di is the length of the longest decreasing subsequence

ending at Si, and Ii is the length of the longest increasing subsequence ending at Si. Now, 1 <= Di <= 4

and 1 <= Ii <= 4 by our assumption that no 5-long can be made. So, there are only 4*4=16 possible pairs, (Di,Ii).

But since there are 17 numbers Si with associated labels (Di,Ii), there must be at least one pair of duplicate labels.

So, suppose the duplicates are (Dj,Ij) and (Dk,Ik) with j<k. If Sj<Sk then the increasing

subsequence ending at Sj can have Sk appended to it, thereby making it one longer (and increasing Ik by 1). But Ik

is already as large as possible, by definition. A similar thing happens to Dk if Sj>Sk. 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

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 L1.

2) Select the first 11 integers, and then removing L1. We have another set of 10 integers. There is 1 increasing or decreasing subsequence with a different last integer, call this L2.

3) Select the first 12 integers, and then removing L1 and L2. We have another set of 10 integers. There is 1 increasing or decreasing subsequence with a different last integer L3.

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

## Create an account

Register a new account