I have been struggling with a conjecture about latin square, hoping maybe someone on this forum might enlighten me.

Assume positive integers m,n,k and m=kn (k=2,3,...). Let's define an m-by-n matrix A with two constraints:

(1) each row of A is a permutation on {1,2,...,n} (these permutations are not necessarily distinct)

(2) each column of A contains exactly k instances of number j (j=1,2,...,n)

For example, m=6,n=3, k=2

1 2 3 *

3 1 2 *

1 3 2

3 2 1

2 1 3

2 3 1 *

each row is a permutation on {1,2,3}, each column contains 1/2/3 k=2 times

The thing is, I found that for such an A matrix, I can always pick out n rows out of its m rows, so that these n rows constitute a latin square of order n. (e.g., the rows with * in the above example)

I tried many scenarios and found no exceptions.

So is this conjecture true? How to prove it please?

I think it might relate with birkhoff von neumann theorem or theorems in graph theory, but cannot relate those with my problem.

Any idea??? Many thanks in advance!