Generalized Latin squares
Task number: 4001
Let’s have a square \( n \times n \) and for each column a list of \( n \) not necessarily different symbols. The union of the lists contains \( n^2 \) symbols, and in this union there are \( n \) different symbols and each of them exactly \( n \) times.
Show that the symbols can be arranged on the fields of the square so that each column contains symbols from the prescribed list, and no two symbols are repeated in any row.
Observe that if each column were prescribed a list of all \( n \) symbols, we would get a Latin square.
Solution
We incrementally fill in the rows. After filling in the first \( i \) rows, the current lists contain \( n-i \) symbols that have not been used yet, and each symbol has \( n-i \) occurrences.
We create a set system on the set of symbols, where \( S_j \) is the set of symbols usable to complete the \( j \)-th column (i.e. it will be created from the current list for \( j \) column by removing duplicates).
We verify the Hall condition: for each \( J \subseteq [n] \), \( \bigcup_{j \in J} S_j \) must contain at least \( | J | \) different symbols: The union of the corresponding lists has \( | J | (n-i) \) elements and each symbol can have at most \( n-i \) occurrences.
Thus, for the system \( (S_j)_{j \in [n]} \) there is a system of distinct representatives and this system of distinct representatives corresponds to filling in the \( (i + 1) \)-th row.
