Given N infinite sequences of non-negative integers, some of which diverge to infinity, must there exist two steps i, j in which $x_i \leq x_j$ for all sequences x?
-
$\begingroup$ Do you mean "all of which diverge to $\infty$"? Otherwise, of course not; take one sequence to be $x_n=n$ and the other to be $y_n=1/n$. $\endgroup$– David E SpeyerJan 28, 2014 at 0:30
-
2$\begingroup$ Assuming you want them all to diverge to $\infty$, yes. Let the sequences be $(x^k_1, x^k_2, x^k_3, \ldots)$ for $1 \leq k \leq N$. There is some $M$ such that $j \geq M$ implies $x^k_j > x^k_1$, by the definition of approaching $\infty$. Take $(i,j) = (1,M)$. Or did I misunderstand something? $\endgroup$– David E SpeyerJan 28, 2014 at 0:33
-
4$\begingroup$ In any sequence of non-negative integers there is a constant or an increasing infinite subsequence. Replace all of the sequences by the corresponding subsequences and repeat. Please keep hw out of MO. $\endgroup$– Lev BorisovJan 28, 2014 at 0:39
-
1$\begingroup$ @DavidSpeyer Since I am working with integers, the 1/n shouldn't come into play. Some of the sequences do diverge to infinity, and others fluctuate but never drop below zero. As for the second comment, we need the same indexes for all of the N sets. $\endgroup$– Ratteler50Jan 28, 2014 at 0:42
-
$\begingroup$ @LevBorisov, this is actually not HW, but a lemma we have reduced a theorem we need for CS research to. As for "In any sequence of non-negative integers there is a constant or an increasing infinite subsequence" do we know that the subsequences for all N sequences intersect at all? $\endgroup$– Ratteler50Jan 28, 2014 at 0:45
1 Answer
So I think I found a proof thanks to the user picado on reddit:
For any sequence there's a subsequence $i_1<i_2<i_3<\dots$ with $x[i_1]\leq x[i_2]\leq \dots$ either because it's unbounded, or because if it's bounded there must be a value repeated an infinite number of times.
So take such a subsequence for the first one, and restrict all your other sequences to the same indices. Then the next will again have a subset of the i's as $j_1<j_2<\dots$ with $y[j_1]\leq y[j_2]\leq\dots$
Repeat N (finite) times, and you'll get a sequence of indices $m_1<m_2<\dots$ for all the sequences.
-
2
-
$\begingroup$ @LevBorisov ah totally missed the replace all the sequences with the subsequencs part. Thank you as well for the help. $\endgroup$ Jan 28, 2014 at 1:00
-
$\begingroup$ Sorry about the hw remark, the problem just looked very familiar. Maybe it is an old Putnam problem or something. $\endgroup$ Jan 28, 2014 at 2:27