La $a_{i,j}$ være tallet i rad i kolonne j. La $v_{i,k}(j) = a_{i,j}+a_{k,j}$ og $w_{i,k}(j) = \frac{a_{i,j}+a_{k,j}}{2}$. Vi viser først en påstand.
$\textbf{Påstand:}$ Hvis vi ser på radene modulo 2, så eksisterer det to rader med like tall på 7 av plassene.
$\textit{Bevis:}$ Vi sier at differansen mellom to rader er antall kolonner hvor de har ulike tall modulo 2. Vi ser at $v_{i,k}(j) = 1$ hviss rad i og rad k har to ulike tall i kolonne j. Vi summerer nå over alle differansene mellom radene:
\[
\sum_{j=1}^{13} \sum_{1\leq i < k \leq 13} v_{i,k}(j) =\sum_{j=1}^{13} f(j)(13-f(j)) \leq 13\cdot (6\cdot 7)
\]
Her er $f(j)$ lik antall enere modulo 2 i kolonne j. Vi har at $\sum_{1\leq i < k \leq 13} v_{i,k}(j) = f(j)(13-f(j))$ fordi hver $v_{i,k}(j) =1$ korresponderer med et valg av ener og et valg av nuller. Antall valg av to rader er $\binom{13}{2} = 78$. Vi har altså at gjennomsnittsdifferansen mellom to rader er mindre eller lik $\frac{13\cdot 6\cdot 7}{78} = 7$. Det betyr at det eksisterer to rader med differanse 6 eller mindre, eller så er differansen mellom to rader alltid nøyaktig 7. Hvis det eksisterer to rader med differanse 6 eller mindre så er de like i 7 av kolonnene.
Det holder nå å vise at det ikke er mulig at alle radene innbyrdes har differanse 7. Vi kan tenke på radene som binærstrenger. Differansen mellom to rader er da lik hamming-avstanden mellom deres korresponderende binærstrenger. La $g$ være en funksjon som gir antall enere i en binærstreng. Vi har da at differansen mellom binærstreng x og y er $g(x\oplus y) = g(x)+g(y)-2g(x\land y) = 7$ for alle x og y. La oss si at vi har tre binærstrenger x, y og z. Da vet vi at en av $g(x) + g(y)$, $g(y)+g(z)$ eller $g(z)+g(x)$ er delelig på 2. UTAG anta at det er $g(x)+g(y)$. Dette er en motsigelse fordi $g(x)+g(y)\equiv g(x\oplus y) =7 \pmod 2$. Dermed er påstanden vist.
Vi kan nå ta fatt på oppgaven. Av påstanden ovenfor kan vi UTAG anta at $a_{1,j} \equiv a_{2,j} \pmod 2$ for $1\leq j \leq 7$. Da er $w_{1,2}(j)$ også et heltall. Det følger av EGZ teoremet på disse $2\cdot 4-1$ tallene at det eksisterer $w_{1,2}(j_1)$, $w_{1,2}(j_2)$, $w_{1,2}(j_3)$ og $w_{1,2}(j_4)$. Slik at summen deres er delelig på 4. Dermed har vi at
\[
0 \equiv 2\sum_{k=1}^4 w_{1,2}(j_k) \equiv \sum_{k=1}^4 v_{1,2}(j_k) \pmod 8
\]
Kombomaraton
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa