The numbers 1,2,3...101 are written down in a row in some order. Is it always po
ID: 2964847 • Letter: T
Question
The numbers 1,2,3...101 are written down in a row in some order. Is it always possible to cross out 90 numbers in a way such that all 11 numbers will stay either in increasing or decreasing order? I know the answer is yes but need help verifying the proof and clear explanation of how the ordered pairs are assigned to each number (from Erdos-Szekeres theory on monotonic subsequences). Please show example using some 11 numbers that would be left after crossing out 90 random numbers. I need a very clear explanation of exactly how this is concluded using realy numbers and not simply variables, step by step. Thank you!
Explanation / Answer
Assume that the result is false. For each number x in the sequence, for the ordered pair (a,b), where a is the length of the longest increasing subsequence beginning with x, and b is the length of the longest decreasing subsequence ending with x. Since we assumed the result to be false, we know that 1 <= a <= 10 and 1<=b<=10. Thus, we have 101 order pairs where 100 are distinct (entries less than 10). Thus, for two members of the sequence, say s and t, are associated with some ordered pair (f,g). We may assume s preceeds t for generality in the sequence
If s<t, then s, together with ther longest increasing subsequence beginning with t, is an increasing subsequence of length f+1, contradicting the fact that f is the length of the longest increasing subsequence beginning with s. Hence s>=t. But, then t, together with the longest decreasing subsequence ending with s, is a subsequence of length (g+1), contradicting that the longest decreasing sequence ending with t is of length g. Therefore our assumption is wrong. Thus, we can conclude the statement is true.