Sequence 0-100

[dennislopes]

Hello,

 

I am trying to solve this problem, but always I tried to solve with the

worst case. This strategy was failed. Can someone help me with this

problem?

 

I have a sequence of number from 0 to 100 listed without repetition

in any order. I need to prove that is always possible erase 90 number

from this sequence and get a increasing or decreasing sequence with

the left numbers

 

Thanks in advance

[Qfwfq]

I need to prove that is always possible erase 90 number

from this sequence and get a increasing or decreasing sequence with

the left numbers

If I haven't misunderstood your query, there are sequences for which it isn't possible, so you're wanting to be lucky! :)

 

The most obvious counterexample is the sequence 100, 99, 98, 97.... decreasing down to 3, 2, 1, 0, lift-off!

[Bo]

the question was increasing OR decreasing, so that's not a valid counterexample...

 

Bad proof: I cant think of a counterexample that holds for both increasing and decreasing series :)

 

Bo

[C1ay]

I have a sequence of number from 0 to 100 listed without repetition

in any order. I need to prove that is always possible erase 90 number

from this sequence and get a increasing or decreasing sequence with

the left numbers

 

Thanks in advance

Are you trying to say that the 10 leftmost numbers will all be an increasing series or a decreasing series after erasing the 90 rightmost numbers? If not, please give us a more descriptive statement of your problem.

[pgrmdave]

I think that he means that if you have a random sequence of the numbers 0 to 100, then if you will be able to take ten of those in order, but not necesarily consecutive order, to be either an increasing, or decreasing set.

 

example:

 

5,10,86,43,52,95,17,25,16,24,35,58,64,77,55,61,20...11,29

 

You have the set (of five because I didn't write them all out):

5,10,43,52,58

[C1ay]

I think that he means that if you have a random sequence of the numbers 0 to 100, then if you will be able to take ten of those in order, but not necesarily consecutive order, to be either an increasing, or decreasing set.

 

example:

 

5,10,86,43,52,95,17,25,16,24,35,58,64,77,55,61,20...11,29

 

You have the set (of five because I didn't write them all out):

5,10,43,52,58

IOW, 10 of the 100 will be in decreasing or increasing order regardless of the arrangement?

[Qfwfq]

Hi Bo! Back from holidays?

the question was increasing OR decreasing, so that's not a valid counterexample...

I thought I must have got it wrong, but I hadn't seen the "increasing or decreasing" right. :) :)

 

C1ay, I found it obvious that the "left" numbers meant the remaining ones and not the Socialist or the Communist ones. He means there will be a subsequence of 10 elements.

[UncleAl]

Given 0-100 in random order (101 numbers). Can you arrange them so no set of 10 numbers in their given order distributed anywhere in the 101 number sequence is uniformly increasing or decreasing?

 

The first number of the set is a given; you always have that one. The second number of the set must be larger or smaller; you always have that one too. Are there eight more numbers of the ones remaining that continue the trend?

 

The problem is 20% smaller now. "8^>)

[dennislopes]

Hello,

 

Sorry if I am not clear with the question.

 

I need to prove that if I write in a paper all numbers from 0 to 100 (in any order, without repetition and using all numbers), I always can erase 90 of this numbers and get the left numbers in an increasing or decreasing order. Per example, I will do this with a sequence of numbers from 0 to 5 in any order:

 

1) 0 2 1 4 3 5

2) 5 4 1 3 2 0

3) 4 5 0 1 3 2

 

I always can erase 4 numbers and the 2 numbers left will be in a increasing or decreasing order:

 

1) 2 1 -------> decreasing order

2) 2 0 -------> decreasing order

3) 0 2 -------> increasing order

 

On this trivial example, you can see that this is always possible, but I cannot generalize this for 100 numbers (0 to 100)

 

I am sure that with the sequence of numbers from 0 to 100, I always have a way of erase 90 numbers and get left numbers in a increase/decreasing order. I was arranjed the numbers in different orders and always I have a way to get the left numbers according the rule, but I cannot explain this in a formal mathematical way.

 

This exercise I have extracted from a old book of my college. Unafortunatelly, this book don't have the answers and I am very curious to know how to solve it

 

PS: I am very happy with the numbers of reply to my question. Thanks for your help

 

Dennis

[Qfwfq]

I think I understood yesterday and I have an idea to work on, I would need to find more time without other problems around.