Transversals in long rectangular arrays (Q856842)

A transversal in an \(m\times n\) array, \(m \leq n\), is a set of \(m\) cells such that no two cells are in the same row or column and no two cells contain the same symbol. The authors prove that if \(n \geq 2m^3\) and in an \(m \times n\) array every symbol appears at most \(\frac{mn-1}{m-1}\) times then there exists a transversal in this array.