Monotonic Subsequences
by 'Literka'.
|
|
Monotonic Subsequences by 'Literka'. |
||
be a sequence of real numbers of length 
.
Then there is a monotonic subsequence of this sequence of length at least n+1.
be a sequence of different real numbers of length 
(i.e. n>0 is a natural number and k=
). Assume that the maximal length of monotonic subsequence of this sequence is less or equal than n. Then there exists a function B(i,j)
for n>=i,j>0 (sign >= means bigger or equal) such that 
for some k>m>0,
and B(i2,j)=
Then i1>i2 if and only if t>s,
and B(i,j2)=
Then j1>j2 if and only if s>t.
} be a sequence of different real numbers of length
(i.e. n>0 is a natural number and k= ). Assume that the maximal length of monotonic subsequence of this sequence is less or equal than n. Then the numbers
are the entries of some matrix B of size n x n (n rows, n columns) such that rows of this matrix are increasing subsequences of A and columns of this matrix B are decreasing subsequences of A.
}
of different real numbers, where k=
. Take a subsequence A of first
numbers of G. Of course, we can assume that the assumptions of Theorem 2 for A are satisfied, otherwise there is nothing to prove. Compare
with B(n,n) (B is a function from the assertion of Theorem 2) and add
to a subsequence of A , which is n-th row of B or to the n-th column of B (we can regard B as a matrix).
(not necessarily closed intervals) where the function f is constant.
be intervals where f is constant. Assume that f(x) =
for 
. Then there exist:
is a union of sets of a rectangle partition U
(which is a sum of areas of rectangles) is equal to the length of
for 
. Then
be a partition of P and k=
. Assume that all elements
have equal area (hence area must be 1/k for each
). Assume that every vertical or horizontal straight line crosses at most n sets from this partition. Then partition is a rectangle partition and all
are squares.
} be a sequence as in the assumption of Theorem 2. Let
=[i/k,(i+1)/k) and define h: [0,1] -> R setting h(x)=
for
. Lemma 1 gives a partition
of P and Lemma 2 shows that there is a monotonic subsequence of length bigger than n or all
are squares. This is a statement of Theorem 2.
. Then we define that a sequence is monotonic if corresponding sequences of each coordinate are monotonic sequences. It appears that similar theorems to the 1-dimensional case can be formulated. The same is for any n-dimensional space.
(Notice: we use the same word "monotonic" for different definitions of this word):.
For any vector x of
we can create a sequence of real numbers taking scalar products of M with a vector x.
If for even one non-zero vector x a sequence created this way is monotonic, then we call a sequence M monotonic.
Software that you really need.