Let $A$ be a matrix with $n$ rows and $m$ columns ($m\geq n\geq 2$) such that all the $n$ rows are distinct. (Two rows indexed by $i_1, i_2 \in [n]$ are said to be distinct iff there exists a column $j \in [m]$ where they differ i.e., $A(i_1,j) \ne A(i_2,j)$).
Prove that there exists an $n\times(n-1)$ submatrix $A'$ of $A$ (i.e. $A'$ is obtained from $A$ by picking $n-1$ columns) such that $A'$ also has $n$ distinct rows.
I tried to use induction on $n$ because I think that should be the simplest approach, but I couldn't get further.
The induction step ($n-1 \implies n$) goes like this.
Suppose you have $n-2$ columns such that the $n-1 \times n-2$ submatrix $B$ formed by the first $n-1$ rows and those columns has all distinct rows. These columns of the $n$'th row can only match at most one of the rows of $B$. If it doesn't match any of them, choose another column arbitrarily. If it does match one, let's say the $i$'th row, choose a column where the $i$'th and $n$'th rows differ.