covermatrices

In feit zegt de vraag dat voor elke unie van een i-rij en i-kolom geen getal meer dan een keer voorkomt.

a) FTSOC stellen we voor dat er een constructie bestaat voor $n$ is oneven (behalve 1). Een element zit oftewel in 1 unie (als en slechts als het op de diagonaal ligt), oftewel 2. Elke unie bevat elk getal, dus als $n$ oneven is, moet tenminste elk getal een keer op de diagonaal voorkomen. Maar op de diagonaal zijn er maar $n$ plaatsen, en er zijn $2n-1$ verschillende getallen, dus kan dit alleen als $2n-1\leq n$ en dat kan voor natuurlijke getallen alleen voor 1. Dus bestaat er geen constructie van dit soort voor 1997.

b) We zullen dit bewijzen via inductie, we stellen dus voor dat het werkt voor $n$, en dat we dan ook een matrix van grootte $2n$ kunnen construeren. (basis geval is triviaal: $\{1\}$)

Laat A een covermatrix zijn, we construeren nu de volgende matrix:

\[
\begin{pmatrix}
A & B\\
C & A\\
\end{pmatrix}
\]

Waar $B$ and $C$ matrices zijn van grootte $n\times n$. Voor deze nieuwe constructie zullen we $2n$ nieuwe elementen hebben, die zullen we gelijk verdelen tussen $B$ en $C$.
Voor B en C kunnen we eender welke Latijns vierkant nemen.
Een voorbeeld is door die te rangschikken op rechten evenwijdig met de hoofddiagonaal.
Voor $n=4$ is de volgende matrix bvb. een Latijns vierkant ($a,b,c,d$ zijn willkeurige elementen, niet noodzakelijk behorende tot $A,B,C$)

\[
\begin{pmatrix}
a & b & c & d\\
d & a & b & c\\
c & d & a & b\\
b & c & d & a\\
\end{pmatrix}
\]

Nu voor elke i-rij en i-kolom zullen $n-1$ van de inputs van $A$ zijn, en deze zijn allemaal verschillend wegens het IH. En de andere $n$ inputs zullen van $B$ of $C$ zijn, en wegens constructie zijn alle elementen in elke rij, en kolom verschillend, dus is onze inductie succesvol.

Dus omdat onze inductie begint met het triviale voorbeeld, kunnen we matrixen construeren voor alle machten van 2.