0
$\begingroup$

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?

$\endgroup$
7
  • $\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$ Jan 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$ Jan 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$ Jan 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$
    – Ratteler50
    Jan 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$
    – Ratteler50
    Jan 28, 2014 at 0:45

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Yup, that's what I meant. $\endgroup$ Jan 28, 2014 at 0:57
  • $\begingroup$ @LevBorisov ah totally missed the replace all the sequences with the subsequencs part. Thank you as well for the help. $\endgroup$
    – Ratteler50
    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

Not the answer you're looking for? Browse other questions tagged or ask your own question.