Question

In an $n\times n$ array of numbers all rows are different (two rows are different if they differ in at least one entry). Prove that there is a column which can be deleted in such a way that the remaining rows are still different.

• A. For k= n we obtain the desired result.
• B. For k= 1 we obtain the desired result.
• C. For k= 0 we obtain the desired result.
• D. None of these

Answer 1

The correct option is A For k= n we obtain the desired result.

At least n-k+1 columns can be deleted in such a way that the first k rows are still different. For k= 2 the assertion is true. Indeed, the first two rows differ in at least one place, so we can delete the remaining n-1 columns. Suppose the assertion is true for k, that is we can delete n-k+1 columns and the first k rows are still different. If after the deletion of the columns the (k+1) th row is different from all first k rows, we can put back any of the deleted columns and remain with n- k deleted columns and k+1 different rows. If after the deletion the (k+1)th row coincides with one of the first rows, then we put back the column in which the two rows differ in the original array. For k= n we obtain the desired result.