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!
