Author |
Topic: MONOTONIC SUBSEQUENCE (Read 1149 times) |
|
jonderry
Newbie
Posts: 18
|
 |
MONOTONIC SUBSEQUENCE
« on: Aug 18th, 2004, 1:25pm » |
 Quote  Modify
|
I couldn't find a thread on this so here goes.
a) One I came up with is:
463591827
b-c) Here is the best proof I could come up with:
For each element in the full sequence, consider the sequence of the lengths of the longest ascending subsequences ending at each element and the sequence of the lengths of the longest descending subsequences ending at each element.
When considering both of these sequences, note that before the kth 1 in the first sequence, there must be a k in the second sequence and vice versa (because each of these ones represents a new low, going left to right). Similarly, before the kth 2 in the first sequence, there must be a k in the second and vice versa (because the final elements in the subsequences of length 2 form a monotonic subsequence in the other sequence). An analogous argument shows that before the kth j of one sequence, there is a j + 1 in the other.
Thus, when the number of elements in the original is greater than k^2, there is a monotonic subsequence of length k + 1
(in particular, when k = 3, a sequence of length 10 has a monotonic subsequence of length 4).
As an additional note, for sequences of length less than or equal to k^2, we can always find a sequence that has no monotonic sequence of length k + 1.
Such a sequence can be constructed using the following
pattern:
A;H1,L1,H2;H1,L1,H2,L2,H3;H1,L1,H2,L2,H3,L3,H4;....
where A is an arbitrary integer, Hi represents an integer
that is currently the ith highest, and Li represents an
integer that is currently the ith lowest.
Semi-colons delimit the end of sequences whose lengths
are square.
|
|
 IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print