Hint: Combinatorics Q3

First part: just be systematic and look for a solution with lots of structure.

What we're trying to accomplish would seem to be helped by having relatively few entries in each row of any given label. So ...

Second part: Much harder.

Consider columns of a supposed labeling. A pair of entries of the same label in the same row of two different columns is a "danger sign". Indicate this danger by connecting the two columns with an edge carrying that label (columns may well be connected by more than one edge). Can two columns be connected with two edges having the same label?

So the maximum allowable number of edges is?

On the other hand any pair of equal labels in any row produces an edge. So the minimum number of labels occurring is?

It would be great if the first answer were smaller than the second -- unfortunately it's not (if you've done it all correctly they'll be equal). But there's one more twist in the tale -- since we have the maximum allowable number of edges we know (in principle) exactly how many of each label there are. On the other hand since we have the minimum possible number of labels, we know how they are produced. Something doesn't match.