Combinatorics: Existence of a Latin Square Let $k_n$ be the smallest number such that given an n by n grid with $k_n$ arbitrary numbers in the top left corner and n arbitrary numbers in every other cell, a number can be chosen from each cell such that the chosen numbers form a Latin square, i.e. no row or column has repeated entries. Show that $k_n > \frac{n}{2}$.
I know that by Galvin's theorem that $k_n$ is at most $n$. To show that $k_n \gt \frac{n}{2}$, it suffices to provide an entry assignment for an arbitrary $n$ such that no latin square can be formed. Here is an example for $n=2$:
$1$, $13$
$12$, $23$
And $n=3$:
$1$, $134$, $134$
$124$, $234$, $234$
$124$, $234$, $234$
I cannot, however, get it for $n=4$, much less the general case. In the above examples, I am only considering entries of value less than or equal to $n+1$, but I am sure that there needs to be more than that many possible numbers, but I suspect there is no way it needs more than $2n$ numbers.
Any help is greatly appreciated. 
 A: For $n=4$, a possible solution is
\begin{array}{cccc}
    12   & 1234 & 1234 & 1234 \\
    1256 & 3456 & 3456 & 3456 \\
    1256 & 3456 & 3456 & 3456 \\
    1256 & 3456 & 3456 & 3456
\end{array}
and you can verify yourself (or by looking at the general solution below) that this cannot be completed.
The general solution has the form
\begin{array}{c|ccc}
     A & A \cup B & \cdots & A \cup B \\ \hline
     A \cup C & B \cup C & \cdots & B \cup C \\
     \vdots & \vdots & \ddots & \vdots \\
     A\cup C & B \cup C & \cdots & B \cup C 
\end{array}
where $|A| = \lfloor \frac n2\rfloor$ and $|B| = |C| = \lceil \frac n2\rceil$. When $n$ is even, all three sets are disjoint; when $n$ is odd, $A$ is still disjoint from each of the two other sets, but $B$ and $C$ share one element, so that $|A \cup B| = |A\cup C| = |B \cup C| = n$ in either case.
Fill in the bottom right $(n-1) \times (n-1)$ square first. There are $(n-1)^2$ entries, chosen from $n$ possible values; by the pigeonhole principle, some value $x \in B \cup C$ occurs at least $$\left\lceil \frac{(n-1)^2}{n}\right\rceil = \left\lceil n-2 + \frac1n\right\rceil = n-1$$ times in that square. That means it appears in each of those rows and columns.
Without loss of generality, $x \in B$. Then all entries in the top row must come from $A \cup B - \{x\}$: $x$ is forbidden from the last $n-1$ entries, and wasn't an option for the first entry to begin with. But now we have only $n-1$ values to choose from to fill $n$ entries of the top row, which is impossible.
