2
$\begingroup$

I'm not quite sure how to even start this problem. I'm really just looking for direction on how to begin.

The $t$ mutually orthogonal Latin squares $A_1, A_2, ... , A_t$ of side $n$ have mutually orthogonal subsquares $ S_1, S_2, ... S_t$ occupying their upper left $s$x$s$ corners. Prove that $n$ is greater than or equal to $(t+1)s$.

I know that $t$ must be less than $n$, but I can't find any other information to help me.

1 Answers 1

3

Consider the cells in row $s+1$ to the right of column $s$. These $n-s$ cells must contain each of the $s$ symbols of the subsquares, since none of those symbols appear in the $s$ cells in the left part of the row. Furthermore, this must be true for the cells in corresponding positions in each of the $t$ MOLS, and no single position in two distinct orthogonal squares can contain multiple symbols from the subsquares, since this would create a pairing that already exists within the orthogonal subsquares. Thus $t$ copies of $s$ symbols must be distributed among only $n-s$ positions, yielding the desired inequality.