This is an incredibly well-known problem; it appears in a Ross Honsberger book. The easiest proof is by induction; but it pays to work in a more general setting, and prove that given a table on $m$ distinct rows and $n\geq m$ columns, one can remove $n-m+1$ columns so that the rows in the new table remain distinct. Clearly, one cannot improve on this result, given the example $\begin{bmatrix} 0 & 0 & \cdots & 0 & 0 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ 0 & 0 & \cdots & 0 & 1 \\ \end{bmatrix}$ on $m$ rows and $n=m-1$ columns.

Seems easy for a $\#3$,even for $2004$.Here is another solution:Consider a graph with $n$ vertices where vertices represent rows and two vertices vertices are connected iff the rows which represnt them become the same if we delete one column.Now,if two rows become the same if we remove the $i$ column,the edge between them is colored by the $i$ color.Now,if we assume contrary, we get that we have at least one edge from every color.Now,pick one edge from every color,we have $n$ edges and it is easy to prove that we have a cycle,for example pick a walk of the longest lenght,now the ends will have at most one edge,so we reduced the problem on $n-1$ edge and $n-1$ vertices,so we are done.Now this is a contradiction,because we can't have a cycle with all edges pairwaise different colors(it will contradict our assumption),so we are finished.

See also here: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=607881 The problem is the same, just with different wording.