For any two n-dim vector $v$ and $v'$ define $v\leq v'$ iff for each $1\leq i\leq n$, $v_i\leq v_i'$. Suppose further that the entry of vectors can only take values from $m$ distinct values $\{a_1, a_2, \cdots, a_m\}$.
Claim: for a sequence of vectors $v_1\leq v_2 \leq \cdots \leq v_s$ for $s=mn+1$, we must have some $i,j$ such that $v_i=v_j$.
This seems to be trivial, but is there any formal and simple proof for that? Or does this follow from some famous theorem (e.g. some Erdos theorem)?
I guess the OP means that the values are ordered linearly, i.e. $a_1<\dots<a_m$. In that case the statement is even true for $s=mn-n+2$.
To see this, define the numbers $1\leq c(i,k)\leq m$ such that $v_i=(a_{c(i,1)},\dots,a_{c(i,n)})$. In addition, consider the integers $w_i:=c(i,1)+\dots+c(i,n)$. Then, for any pair $1\leq i<j\leq s$, we have $v_i\leq v_j$, hence $c(i,k)\leq c(j,k)$ for any $1\leq k\leq n$, hence also $w_i\leq w_j$. Moreover, $w_i=w_j$ can only hold when $c(i,k)=c(j,k)$ for each $1\leq k\leq n$, i.e. when $v_i=v_j$. Now observe that $n\leq w_1\leq\dots\leq w_s\leq mn$, hence for $s=mn-n+2$ we have $w_i=w_j$ for some $i<j$, so $v_i=v_j$ by the discussion above. The proof is complete.
