Introduction
Cutler and Öhman (2006) attribute to Pebody (via personal communication) a construction of a set of $k:=\lfloor n/3 \rfloor+1$ partial Latin squares which are unavoidable (i.e., any Latin square of order $n$ has a non-empty intersection with at least one of these $k$ partial Latin squares). This claim was repeated by Andrén (2012). (The construction is described below.) However, neither of these papers provide a proof.
Question: How can we prove this set is unavoidable?
My attempts to prove this claim become somewhat complicated and I feel like I'm heading in the wrong direction (and I feel like I'm missing something more obvious).
Construction
In the $n=7$ case, we can collapse the $k$ partial Latin squares down to the following:
$$\begin{array}{|ccc|ccc|c|}\hline\{1,2,3\}&\{1,2,3\}&\{1,2,3\}&\emptyset&\emptyset&\emptyset&\emptyset\\\{1,2,3\}&\{1,2,3\}&\{1,2,3\}&\emptyset&\emptyset&\emptyset&\emptyset\\\{1,2,3\}&\{1,2,3\}&\{1,2,3\}&\emptyset&\emptyset&\emptyset&\emptyset\\\hline\emptyset&\emptyset&\emptyset&\{4,5,6\}&\{4,5,6\}&\{4,5,6\}&\emptyset\\\emptyset&\emptyset&\emptyset&\{4,5,6\}&\{4,5,6\}&\{4,5,6\}&\emptyset\\\emptyset&\emptyset&\emptyset&\{4,5,6\}&\{4,5,6\}&\{4,5,6\}&\emptyset\\\hline\emptyset&\emptyset&\emptyset&\emptyset&\emptyset&\emptyset&\{7,8,9\}\\\hline\end{array}$$
In general, the construction has the block structure: $$ \begin{array}{|c|c|c|} \hline A & \cdot & \cdot \\ \hline \cdot & B & \cdot \\ \hline \cdot & \cdot & C \\ \hline \end{array} $$ where
- $A$ is a $k \times k$ block, with every cell containing $\{1,2,\ldots,k\}$.
- $B$ is a $k \times k$ block, with every cell containing $\{k+1,k+2,\ldots,2k\}$.
- $C$ is a $(n-2k) \times (n-2k)$ block, with every cell containing $\{2k+1,2k+2,\ldots,n\}$ (where we know $n-2k<k$).
Computation
I've verified the claim computationally for $n \leq 7$, and it holds in these cases. In the $n=8$ case, this Latin square (for example) comes quite close, with just one clash in the bottom-right corner: $$\begin{array}{|ccc|ccc|cc|} \hline 4 & 5 & 6 & 1 & 2 & 3 & 7 & 8 \\ 5 & 4 & 7 & 2 & 1 & 6 & 8 & 3 \\ 6 & 7 & 8 & 4 & 5 & 1 & 3 & 2 \\ \hline 1 & 2 & 4 & 3 & 7 & 8 & 5 & 6 \\ 2 & 1 & 5 & 8 & 3 & 7 & 6 & 4 \\ 3 & 6 & 1 & 7 & 8 & 2 & 4 & 5 \\ \hline 7 & 8 & 3 & 5 & 6 & 4 & 2 & 1 \\ 8 & 3 & 2 & 6 & 4 & 5 & 1 & \mathbf{7} \\ \hline \end{array}$$
UPDATE: We can also set up a system of linear equations, with variables describing the number of copies from any family of symbols in a given block. I found this system of equations has no solutions for $n \leq 100000$ or so, which verifies the claim in these cases.
