wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> MONOTONIC SUBSEQUENCE
        
(Message started by: jonderry on Aug 18^th, 2004, 1:25pm)

Title: MONOTONIC SUBSEQUENCE
Post by jonderry on Aug 18^th, 2004, 1:25pm

I couldn't find a thread on this so here goes.

a) One I came up with is:
[hide]463591827[/hide]

b-c) Here is the best proof I could come up with:
[hide]
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.
[/hide]