Suppose $n$ is even. Consider an $n$ x $n$ Latin square L, defined by $L_{ij} = i+j (mod n)$
I want to show that if I choose $n$ values from distinct rows and columns, then at least two of the chosen entries will be equal. The following is how I thought of it, and seems like a simpler way to think of it, but I still can't figure out exactly what's happening.
In a set of $n$ equations of the form:
$e_i: a_i + b_i = c_i (mod n)$
Where $1\leq a_i, b_i\leq n$, and $a_i \neq a_j$ and $b_i \neq b_j$ for all $i \neq j$
Then I wish to show that there exist two $c$'s, $c_x$ and $c_y$ such that $c_x = c_y$
For example, for $n=4$:
$1 + b_1 = c_1$
$2 + b_2 = c_2$
$3 + b_3 = c_3$
$4 + b_4 = c_4$
If we take $\{b_1, b_2, b_3, b_4\}$ any permutation of $\{1, 2, 3, 4\}$ and reduce each of our $c$'s mod $4$, there will always be some $c_i$ which is repeated.
For instance, if $b_1 = 4, b_2 = 1, b_3 = 2, b_4 = 3$ then $c_1 \equiv c_3 \equiv 1 (mod 4)$ and $c_2 \equiv c_4 \equiv 3 (mod 4)$
Let $\sigma$ and $\tau$ be two permutations of $\{1, \cdots, n\}$. We know that $L_{\sigma(i)\tau(i)}$, $i = 1, \cdots, n$ are $n$ values from different rows and columns.
If they are pairwise distinct, then they are just $1, \cdots, n$, so
$$ \sum_{i=1}^n L_{\sigma(i)\tau(i)} = 0+1 +\cdots + (n-1) = \frac{n(n-1)}2 \equiv \frac n2 \pmod n. $$
On the other hand,
$$ \sum_{i=1}^n L_{\sigma(i)\tau(i)} \equiv \sum_{i=1}^n \sigma(i)+\tau(i) = 2(0+1+\cdots + (n-1)) = n(n-1) \equiv 0 \pmod n. $$