Abstract
Authors
Keywords
?
Paper coordinates
T. Popoviciu, Despre şirurile monotone, Pozitiva, 1 (1940), pp. 41-45 (in Romanian).
About this paper
Journal
Publisher Name
DOI
Print ISSN
Online ISSN
[MR0019133]
google scholar link
??
Original text
Rate this translation
Your feedback will be used to help improve Google Translate
About monotonic sequences
by Tiberiu Popoviciu
There exists a natural numberN_(n)\mathrm{N}_{\mathrm{n}}such that of any sequence of real numbers having at leastN_(n)\mathrm{N}_{\mathrm{n}}In terms, we can extract at least one monotonic byteline sequence ofnnterms but, we can construct a sequence havingN_(n)-1\mathrm{N}_{\mathrm{n}}-1terms of which no partial sequence ofnnThe term is not monotonic. It can be shown thatN_(3)=5\mathrm{N}_{3}=5And(n-1)^(2) < N <= (5)/(6)n(\mathrm{n}-1)^{2}<\mathrm{N} \leqslant \frac{5}{6} n! The exact value ofN_(n)\mathrm{N}_{\mathrm{n}}remains to be found (equal, most likely, to(n-1)^(2)+1(n-1)^{2}+1 ).
There exists a natural numberN_(n)\mathrm{N}_{\mathrm{n}}such that of any sequence of real numbers having at leastN_(n)\mathrm{N}_{\mathrm{n}}In terms, we can extract at least one monotonic byteline sequence ofnnterms but, we can construct a sequence havingN_(n)-1\mathrm{N}_{\mathrm{n}}-1terms of which no partial sequence ofnnThe term is not monotonic. It can be shown thatN_(3)=5\mathrm{N}_{3}=5And(n-1)^(2) < N <= (5)/(6)n(\mathrm{n}-1)^{2}<\mathrm{N} \leqslant \frac{5}{6} n! The exact value ofN_(n)\mathrm{N}_{\mathrm{n}}remains to be found (equal, most likely, to(n-1)^(2)+1(n-1)^{2}+1 ).
- Let's consider a finite string
(1)
c_(1),c_(2),c_(3),dotsc_(m)c_{1}, c_{2}, c_{3}, \ldots c_{m}
ofmmreal numbers. If all the differences
Delta_(C_(i))=C_(i)+1-C_(i)quad,quad i=1,2,dots,m-1\Delta_{C_{i}}=C_{i}+1-C_{i} \quad, \quad i=1,2, \ldots, m-1
are of the same sign or zero, the sequence (1) is said to be monotone. More precisely, the sequence (1) is said to be increasing, non-decreasing, constant, non-increasing or decreasing, as we have
DeltaC_(1) > , >= ,=, <= " resp. " < 0,quadi=1,2,dots,m-1\Delta \mathrm{C}_{1}>, \geqslant,=, \leqslant \text { resp. }<0, \quad \mathrm{i}=1,2, \ldots, \mathrm{~m}-1
Obviously, increasing and constant sequences are special cases of non-decreasing sequences. If the sequence (1) is increasing, non-decreasing, etc., the sequence of opposites
-c_(1),-c_(2),dots,-c_(m)-\mathrm{c}_{1},-\mathrm{c}_{2}, \ldots,-\mathrm{c}_{\mathrm{m}}
is resp. decreasing, non-increasing, etc. and vice versa. We can therefore take as a type of monotone sequence, the decreasing sequence.
2. Given the natural numbersi_(1) < i_(2) < dots < i_(k) <= m\mathrm{i}_{1}<\mathrm{i}_{2}<\ldots<\mathrm{i}_{\mathrm{k}} \leq \mathrm{m}; string
2. Given the natural numbersi_(1) < i_(2) < dots < i_(k) <= m\mathrm{i}_{1}<\mathrm{i}_{2}<\ldots<\mathrm{i}_{\mathrm{k}} \leq \mathrm{m}; string
c_(i_(1)),c_(i_(2)),dots,c_(i_(k))c_{i_{1}}, c_{i_{2}}, \ldots, c_{i_{k}}
is called a partial string of (1). It is clear that a string (1) withmmterms
has((m)/(k))\binom{m}{k}partial strings withkkterms and in total2^(m)-12^{m}-1partial strings with any number of terms (each termc_(i)c_{\mathrm{i}}(it forces itself to create a partial string).
has((m)/(k))\binom{m}{k}partial strings withkkterms and in total2^(m)-12^{m}-1partial strings with any number of terms (each termc_(i)c_{\mathrm{i}}(it forces itself to create a partial string).
We have the almost obvious property.
Theorem 1. If the sequence (I) is increasing, non-decreasing, etc. any partial sequence (having at least 2 terms) is also increasing, non-decreasing, etc.
Theorem 1. If the sequence (I) is increasing, non-decreasing, etc. any partial sequence (having at least 2 terms) is also increasing, non-decreasing, etc.
The converse of the theorem is trivial. The definition itself tells us that for the sequence (1) to be increasing, non-decreasing, etc., it is necessary and sufficient that the partial sequences
c_(i),c_(i+1),quad i=1,2,dotsm-1\mathrm{c}_{\mathrm{i}}, \mathrm{c}_{\mathrm{i}+1}, \quad i=1,2, \ldots \mathrm{~m}-1
to be increasing, non-decreasing, etc.
If we consider monotony without specifying its meaning, we arrive at the following
If we consider monotony without specifying its meaning, we arrive at the following
Theorem 2. The necessary and sufficient condition for the sequence (1) to be monotone is that all partial sequences of three terms are monotone.
For the partial stringc_(j),c_(j),c_(k),i < j < kc_{\mathrm{j}}, c_{\mathrm{j}}, c_{\mathrm{k}}, i<j<k, the necessary and sufficient condition for monotonicity is
(2)
(2)
(c_(i)-c_(i))(c_(k)-c_(i)) > 0\left(c_{i}-c_{i}\right)\left(c_{k}-c_{i}\right)>0
Let us now prove Theorem 2. The condyle is obviously necessary by Theorem 1. Let us prove that it is also sufficient. Suppose that (2) is satisfied, whateveri/_j/_k <= mi \angle j \angle k \leq mIf the sequence (1) were not monotone, the sequence of differences
(3)
(3)
DeltaC_(1),DeltaC_(2),dots,Delta_(C_(m-1))\Delta \mathrm{C}_{1}, \Delta \mathrm{C}_{2}, \ldots, \Delta_{\mathrm{C}_{\mathrm{m}-1}}
would have at least two non-zero terms with opposite signs. LetDeltac_(r)\Delta c_{r}first term!=0\neq 0in (3) andDeltac_(s),s > r\Delta c_{s}, s>rfirst term!=0\neq 0and of opposite sign toDeltac_(r)\Delta c_{r}in (3). We haveDeltac_(r)Deltac_(s) < 0\Delta c_{r} \Delta c_{s}<0, and through its constructionss
Delta_(C_(s))Delta_(C_(i)) <= 0quad,quadi=r+1,r+2,dots,s-1\Delta_{\mathrm{C}_{\mathrm{s}}} \Delta_{\mathrm{C}_{\mathrm{i}}} \leqslant 0 \quad, \quad \mathrm{i}=\mathrm{r}+1, \mathrm{r}+2, \ldots, \mathrm{~s}-1
schools > r+1s>r+1If
​s=r+1s=r+1, we have
​s=r+1s=r+1, we have
DeltaC_(r)DeltaC_(s)=(C_(r+1)-C_(r))(C_(r+2)-C_(r+1)) < 0\Delta \mathrm{C}_{\mathrm{r}} \Delta \mathrm{C}_{\mathrm{s}}=\left(\mathrm{C}_{\mathrm{r}+1}-\mathrm{C}_{\mathrm{r}}\right)\left(\mathrm{C}_{\mathrm{r}+2}-\mathrm{C}_{\mathrm{r}+1}\right)<0
which contradicts (2).
Ifs > r+1s>r+1, we have
Ifs > r+1s>r+1, we have
DeltaC_(s)(Deltar+DeltaC_(r+1)+dots+DeltaC_(s1))=(C_(s+1)-C_(s))(C_(s)-C_(r)) <= O\Delta \mathrm{C}_{\mathrm{s}}\left(\Delta \mathrm{r}+\Delta \mathrm{C}_{\mathrm{r}+1}+\ldots+\Delta \mathrm{C}_{\mathrm{s} 1}\right)=\left(\mathrm{C}_{\mathrm{s}+1}-\mathrm{C}_{\mathrm{s}}\right)\left(\mathrm{C}_{\mathrm{s}}-\mathrm{C}_{\mathrm{r}}\right) \leqslant \mathrm{O}
care andandin contradiction with (2).
The preceding completely proves theorem (2).
3. The question can now be asked whether any string (1) contains monotone partial strings of at least three terms.
The preceding completely proves theorem (2).
3. The question can now be asked whether any string (1) contains monotone partial strings of at least three terms.
We will prove the following Theorem 3 for this.
Any sequence (1) of (at least) five terms has at least one partially monotone sequence of three terms.
Any sequence (1) of (at least) five terms has at least one partially monotone sequence of three terms.
Indeed, at least one of the strings
C_(1),C_(2),C_(3);C_(2),C_(3),C_(4);C_(3),C_(4),C_(5);C_(2),C_(4),C_(5);C_(1),C_(2),C_(4)\mathrm{C}_{1}, \mathrm{C}_{2}, \mathrm{C}_{3} ; \mathrm{C}_{2}, \mathrm{C}_{3}, \mathrm{C}_{4} ; \mathrm{C}_{3}, \mathrm{C}_{4}, \mathrm{C}_{5} ; \mathrm{C}_{2}, \mathrm{C}_{4}, \mathrm{C}_{5} ; \mathrm{C}_{1}, \mathrm{C}_{2}, \mathrm{C}_{4}must be monotonous. Otherwise we should have
C_(1),C_(2),C_(3);C_(2),C_(3),C_(4);C_(3),C_(4),C_(5);C_(2),C_(4),C_(5);C_(1),C_(2),C_(4)\mathrm{C}_{1}, \mathrm{C}_{2}, \mathrm{C}_{3} ; \mathrm{C}_{2}, \mathrm{C}_{3}, \mathrm{C}_{4} ; \mathrm{C}_{3}, \mathrm{C}_{4}, \mathrm{C}_{5} ; \mathrm{C}_{2}, \mathrm{C}_{4}, \mathrm{C}_{5} ; \mathrm{C}_{1}, \mathrm{C}_{2}, \mathrm{C}_{4}must be monotonous. Otherwise we should have
{:[(c_(2)-c_(1))(c_(3)-c_(2)) < 0quad","quad(c_(3)-c_(2))(c_(4)-c_(3)) < 0","quad(c_(4)-c_(2))(c_(5)-c_(4)) < 0],[(c^(4)-c_(3))(c_(5)-c_(4)) < 0quad","quad(c_(2)-c_(1))(c_(4)-c_(2)) < 0]:}\begin{gathered}
\left(c_{2}-c_{1}\right)\left(c_{3}-c_{2}\right)<0 \quad, \quad\left(c_{3}-c_{2}\right)\left(c_{4}-c_{3}\right)<0, \quad\left(c_{4}-c_{2}\right)\left(c_{5}-c_{4}\right)<0 \\
\left(c^{4}-c_{3}\right)\left(c_{5}-c_{4}\right)<0 \quad, \quad\left(c_{2}-c_{1}\right)\left(c_{4}-c_{2}\right)<0
\end{gathered}
or
[(c_(2)-c_(1))(c_(3)-c_(2))(c_(4)-c_(3))(c_(5)-c_(4))(c_(4)-c_(2))]^(2) < 0\left[\left(c_{2}-c_{1}\right)\left(c_{3}-c_{2}\right)\left(c_{4}-c_{3}\right)\left(c_{5}-c_{4}\right)\left(c_{4}-c_{2}\right)\right]^{2}<0
which is absurd.
From the previous theorem we can deduce the following
Theorem 4. Any string of (at least)(5)/(6)n!\frac{5}{6} n!terms has at least one partially monotone sequence ofnnterms (n >= 3n \geqslant 3 ).
From the previous theorem we can deduce the following
Theorem 4. Any string of (at least)(5)/(6)n!\frac{5}{6} n!terms has at least one partially monotone sequence ofnnterms (n >= 3n \geqslant 3 ).
Let the string (1) withm=(5)/(6)n!m=\frac{5}{6} n!We will prove the theorem by induction. The property is already proven forn=3n=3. Suppose it is true forn-1n-1and show that it will also be true fornnIf we putk=(5)/(6)(n-1)!k=\frac{5}{6}(n-1)!, each of the strings
(4)c_(ik+1),c_(ik+2),dots,c_((i+1)k),i=0,1,dots n-1c_{i k+1}, c_{i k+2}, \ldots, c_{(i+1) k}, i=0,1, \ldots n-1
contains by hypothesis, at least a partially monotone sequence ofn-1n-1terms. From the strings (4) let us therefore extract the partial monotone strings ofn-1n-1terms
(5)quadc_(1)^((i+1)),c_(2)^((i+1)),dots,c_(n-1)^((i+1)),i=0,1,dots n-1\quad c_{1}^{(i+1)}, c_{2}^{(i+1)}, \ldots, c_{n-1}^{(i+1)}, i=0,1, \ldots n-1
(4)c_(ik+1),c_(ik+2),dots,c_((i+1)k),i=0,1,dots n-1c_{i k+1}, c_{i k+2}, \ldots, c_{(i+1) k}, i=0,1, \ldots n-1
contains by hypothesis, at least a partially monotone sequence ofn-1n-1terms. From the strings (4) let us therefore extract the partial monotone strings ofn-1n-1terms
(5)quadc_(1)^((i+1)),c_(2)^((i+1)),dots,c_(n-1)^((i+1)),i=0,1,dots n-1\quad c_{1}^{(i+1)}, c_{2}^{(i+1)}, \ldots, c_{n-1}^{(i+1)}, i=0,1, \ldots n-1
The following two cases can then occur
: a) There are at least two among the strings (5) of opposite monotonicity.
: a) There are at least two among the strings (5) of opposite monotonicity.
For example, let it be
non-decreasing and
non-decreasing and
c_(1)^((i)),c_(2)^((j)),dotsc_(n-1)^((j))c_{1}^{(i)}, c_{2}^{(j)}, \ldots c_{n-1}^{(j)}
non-increasing. It can be assumedi < ji<j
Ifc_(n-1)^((1)) <= c_(1)^((j))c_{n-1}^{(1)} \leqslant c_{1}^{(j)}RANGE
Ifc_(n-1)^((1)) <= c_(1)^((j))c_{n-1}^{(1)} \leqslant c_{1}^{(j)}RANGE
c_(1)^((i)),c_(2)^((i)),dots,c_(n-1)^((i)),c_(1)^((i))c_{1}^{(i)}, c_{2}^{(i)}, \ldots, c_{n-1}^{(i)}, c_{1}^{(i)}
and ofnnterms, is a partial sequence of (1) and is monotone
Ifc_(n-1)^((i)) > c_(1)^((j))c_{n-1}^{(i)}>c_{1}^{(j)}the string ofnnterms
Ifc_(n-1)^((i)) > c_(1)^((j))c_{n-1}^{(i)}>c_{1}^{(j)}the string ofnnterms
c_(n-1)^((i)),c_(1)^((i)),c_(1)^((i)),dotsc_(n-1)^((i))c_{n-1}^{(i)}, c_{1}^{(i)}, c_{1}^{(i)}, \ldots c_{n-1}^{(i)}
is monotone and is a sequence extracted from (1).
b) All sequences (5) are monotone of the same sense. We can assume that they are all nondecreasing. If now there is aiiso thatc_(n-1)^((i)) <= c_(n-1)^((i+1))\mathrm{c}_{\mathrm{n}-1}^{(\mathrm{i})} \leqslant \mathrm{c}_{\mathrm{n}-1}^{(\mathrm{i}+1)}then the string ofnnterms
b) All sequences (5) are monotone of the same sense. We can assume that they are all nondecreasing. If now there is aiiso thatc_(n-1)^((i)) <= c_(n-1)^((i+1))\mathrm{c}_{\mathrm{n}-1}^{(\mathrm{i})} \leqslant \mathrm{c}_{\mathrm{n}-1}^{(\mathrm{i}+1)}then the string ofnnterms
c_(1)^((i)),c_(2)^((i)),dots,c_(n-1)^((i)),c_(n-1)^((i+1))c_{1}^{(i)}, c_{2}^{(i)}, \ldots, c_{n-1}^{(i)}, c_{n-1}^{(i+1)}
is monotone and extracted from (1). Otherwise we must havec_(n-1)^((i)) > c_(n-1)^((i+1)),i=1,2,dots,n-1c_{n-1}^{(i)}>c_{n-1}^{(i+1)}, i=1,2, \ldots, n-1and the string ofnnterms
c_(n-1)^((1)),c_(n-1)^((2)),dots,c_(n-1)^((n))c_{n-1}^{(1)}, c_{n-1}^{(2)}, \ldots, c_{n-1}^{(\mathrm{n})}
is monotone and extracted from (1).
Theorem 4 is completely proven.
- It follows from the foregoing that there is a numberN_(n)\mathrm{N}_{\mathrm{n}}such that any string having at leastN_(n)\mathrm{N}_{\mathrm{n}}terms contains at least one partially monotone string ofnnterms, but there is at least one string (1) withN_(n)-1\mathrm{N}_{\mathrm{n}}-1terms that do not contain any partial monotone sequence ofnnterms.
Theorem 4 shows us thatN <= (5)/(6)n!N \leqslant \frac{5}{6} n!On the other hand, the stringn-1,n-2,dots.,2,1,2n-2,2n-3,dots.,n,3n-3n-1, n-2, \ldots ., 2,1,2 n-2,2 n-3, \ldots ., n, 3 n-3, 3n-4,dots,2n-1,dots,(n-1)^(2),(n-1)^(2)-1,dots,(n-2)n-(n-3)3 n-4, \ldots, 2 n-1, \ldots,(n-1)^{2},(n-1)^{2}-1, \ldots,(n-2) n-(n-3)of(n-1)^(2)(n-1)^{2}terms does not contain any partially monotone sequence ofnnterms. It follows thatN_(n) > (n-1)^(2)\mathrm{N}_{\mathrm{n}}>(n-1)^{2}.
numberN_(n)\mathrm{N}_{\mathrm{n}}is equal to 5 forn=3n=3It would be interesting to determine its value fornnsome. It is very likely thatN_(n)=(n-1)^(2)+1\mathrm{N}_{n}=(n-1)^{2}+1, this remains to be demonstrated.
The problem of determining the minimum number of monotone partial sequences ofnnterms that can be extracted from a string having a given numberm >= N_(n)m \geqslant \mathrm{~N}_{\mathrm{n}}of terms. It is easy to see that this number is at least equal to
[(m-N_(n))/(n)]+1\left[\frac{m-\mathrm{N}_{\mathrm{n}}}{n}\right]+1
where[alpha][\alpha]means as usual, the whole part ofalpha\alphaIt is likely that the number we are talking about is equal to the minimum of
((lambda_(1))/(n))+((lambda_(2))/(n))+dots+((lambda_(n-1))/(n))\binom{\lambda_{1}}{n}+\binom{\lambda_{2}}{n}+\ldots+\binom{\lambda_{n-1}}{n}
when the wholelambda_(i) >= 0\lambda_{\mathbf{i}} \geqslant 0check the relationship
lambda_(1)+lambda_(2)+dots+lambda_(n-1)=m\lambda_{1}+\lambda_{2}+\ldots+\lambda_{n-1}=m
This number is equal to
(n-1-r)((m-r)/(n-1))+((m+n-r-1)/(n-1))(n-1-r)\left(\frac{m-r}{n-1}\right)+\left(\frac{m+n-r-1}{n-1}\right)
Whenrris the remainder of the division ofmmraren-1n-1.
It can easily be seen that the problem posed here is equivalent to a combinatorial analysis problem. Given a permutation of the primesmmnatural numbers, it's about how many groups ofnnterms exist in this permutation which terms, keeping their place, form an ascending or descending sequence?
It can easily be seen that the problem posed here is equivalent to a combinatorial analysis problem. Given a permutation of the primesmmnatural numbers, it's about how many groups ofnnterms exist in this permutation which terms, keeping their place, form an ascending or descending sequence?
Observation. The problem of extracting monotone partial sequences can also be posed for infinite sequences of numbers. It is easy to see that from any infinite sequence an infinite and monotone partial sequence can be extracted. However, the problem should not be considered as exhausted in this way. The problem should also be examined for sequences transfinite by an ordinal number (transfinite) given by the terms.
21 August, 940.