0
$\begingroup$

Let $A$ be an $m \times n$ matrix with entries from $\{1,2,...,k\}$. What is the minimum $k$ (as a function of $m$ and $n$) needed so that we can fill $A$ where no two columns are identical.

Thank you.

1 Answers 1

7

This looks like homework.

Hint 1: If there are $m$ rows and $k$ symbols, how many possible distinct columns are there?

Hint 2: If the answer to hint 1 must be greater then or equal to the actual number of columns $n$, what does this mean that $k$ must be greater than or equal to?

Bonus hint: How might you deal with a fractional answer to hint 2?