In each position of an $n \times n$ matrix there is a number. We know that all the rows of the matrix are different from each other. Show that we can delete a column so that the rows of the matrix that remain continue to be different to each other.
I have absolutely no attempt. Any advice would be appreciated!
Define an increasing sequence $s_0,...,s_n\in \{1,...,n\}$ as follows.
$s_0 = 1$ and $s_k$ is equal to the number of distinct rows in the $n\times k$ matrix consisting of the first $k$ columns of $M$.
It is evident that this is an increasing sequence and if $s_{k-1} = s_k$, then we can delete the $k$-th column without any rows becoming equal.
But $s_k \leq n$ for all $k$ and $s_0 = 1$ which implies that there must exist a $k\in \{1,...,n\}$ such that $s_{k-1} = s_k$.