\documentclass[fleqn,10pt]{wlpeerj}
\usepackage{amsthm}
\usepackage[english]{babel}
\usepackage{array}
\newtheorem{stelling}{Stelling}[section]
\newtheorem{gevolg}{Gevolg}[stelling]
\newtheorem{lemma}{Lemma}[stelling]
\newtheorem{definitie}{Definitie}[section]
\newtheorem{voorbeeld}{Voorbeeld}[section]
\newtheorem{opmerking}{Opmerking}[section]
\newcommand{\bewijs}[1] {\noindent \emph{Bewijs} \qquad \text{#1} }
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Zn}{\mathbb{Z}_n}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\abs}[1]{\lvert #1\rvert}
\newcommand{\p}[1]{\left( #1 \right)}
\newcommand{\pmM}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)}
\newcommand{\pmMr}[1]{\left(\begin{smallmatrix*}[r] #1 \end{smallmatrix*}\right)}
\newcommand{\pM}[1]{\left(\begin{matrix} #1 \end{matrix}\right)}
\newcommand{\pMr}[1]{\left(\begin{matrix*}[r] #1 \end{matrix*}\right)}
\newcommand{\dmM}[1]{\left|\begin{smallmatrix} #1 \end{smallmatrix}\right|)}
\newcommand{\dmMr}[1]{\left|\begin{smallmatrix*}[r] #1 \end{smallmatrix*}\right|)}
\newcommand{\dM}[1]{\left|\begin{matrix} #1 \end{matrix}\right|}
\newcommand{\dMr}[1]{\left|\begin{matrix*}[r] #1 \end{matrix*}\right|}
\addto\captionsenglish{\renewcommand{\contentsname}{Inhoud}}
\addto\captionsenglish{\renewcommand{\figurename}{Figuur}}
\title{Het SET-spel, een toepassing op eindige meetkunde}
\author[1]{Luc Van den Broeck}
\affil[1]{EDUGO campus De Toren, Oostakker}
\keywords{SET, eindige meetkunde, duivenhokprincipe, dubbele telling}
\begin{abstract}
Het kaartspel SET, dat gespeeld wordt met 81 kaarten waarop verschillende geometrische afbeeldingen staan, werd in het begin van de jaren '90 populair en heeft sindsdien ook de belangstelling van wiskundigen gewekt. In dit artikel modelleren we het kaartspel aan de hand van een vierdimensionale vectorruimte over het veld $\F_3$. Deze vectorruimte kunnen we interpreteren als meetkundige ruimte met een eindig aantal punten. Via deze interpretatie worden drie kaarten uit het kaartspel die een set vormen voorgesteld door drie collineaire punten. We proberen in dit artikel een bewijs te geven van de stelling dat de kleinste verzameling van speelkaarten die altijd minstens \'e\'en set bevat, bestaat uit 21 kaarten. De berekeningen steunen aanvankelijk alleen op combinatorische tellingen en op het duivenhokprincipe. In de laatste bewijzen van dit artikel maken we ook gebruikt van de methode van de dubbele telling.
\end{abstract}
\begin{document}
\flushbottom
\maketitle
\thispagestyle{empty}
\section{Het kaartspel en de meetkundige modellering}
\subsection {Het kaartspel}
Het SETspel is in het jaar 1974 door toeval ontstaan. De populatiegenetica Marsha Jean Falco deed in Camebridge onderzoek naar epilepsie bij Duitse herdershonden en maakte voor verdere analyse fiches van de genetische data in de cellen van de proefdieren. De regelmaat in deze steekkaarten bracht haar op een idee. Samen met haar echtgenoot richtte ze een bedrijf op, SET Enterprises, dat deze fiches commercialiseerde in de vorm van een kaartspel. De volgende afbeelding toont de 81 kaarten van dit spel.
\begin{figure} [h]
\centering
\includegraphics[width=0.8 \textwidth]{kaartensetgame.jpg}
\caption{De 81 kaarten van het SETspel}
\end{figure}
De kaarten uit het SETspel hebben vier verschillende eigenschappen, die telkens in drie genetische vari\"eteiten voorkomen:
\begin{enumerate}
\item het aantal symbolen: \'e\'en, twee of drie,
\item de vorm: ruitje, rechthoekje of golfje,
\item de kleur: rood, groen of paars,
\item de vulling: leeg, gestreept of vol.
\end{enumerate}
De bedoeling van dit spel is zoveel mogelijk sets te ontdekken in een willekeurige verzameling van 12 kaarten. Een set is een trio van kaarten waarvoor elk van de eigenschappen aan de volgende voorwaarde voldoet: ofwel is de eigenschap gelijk bij de drie kaarten ofwel komt de eigenschap in drie vari\"eteiten voor. Wie het meeste sets kan vinden, is de winnaar.
Het snel kunnen vinden van SETS is een vaardigheid die ook jonge kinderen goed onder de knie kunnen krijgen. Dit verklaart deels de populariteit van dit spel. Overtuig jezelf van de eenvoud van de spelregels door enkele sets te zoeken in de onderstaande selectie van 12 kaarten. Een opvallend bijvoorbeeld bestaat uit de kaarten met de holle, rode ruiten. Er is een kaart met \'e\'en ruit, eentje met twee ruiten en eentje met drie. Er is ook een set te vinden waarbij alle eigenschappen in drie vari\"eteiten voorkomen. Zulke sets zijn moeilijker op te sporen. Je vindt er eentje in de drie meest linkse kaarten op de onderste rij.
\begin{figure} [ht]
\centering
\includegraphics[width=0.6 \textwidth]{twaalfkaarten.jpg}
\caption{Zoek de sets}
\end{figure}
Je zou ook een setspel kunnen bedenken met vijf eigenschappen die in drie vari\"eteiten kunnen voorkomen. Als je een methode zou kunnen vinden om geurkaarten te ontwikkelen dan zou je bijvoorbeeld de volgende vari\"eteiten kunnen bedenken: vanille, aarbei en mokka. In dit artikel doen we onderzoek naar het vierdimensionale SET-spel met 81 kaarten. Maar soms zullen we het ook even over het driedimensionale SETspel hebben met 27 kaarten of over het tweedimensionale met 9 kaarten.
\subsection{Een meetkundig model}
We kunnen de drie verschillende vari\"eteiten van een eigenschap voorstellen door de cijfers 0, 1 en 2. Het zou dus handig zijn om te werken in het eindige veld $\F_3$. Gewoonlijk duiden we de element van dit veld aan met de symbolen 0, 1 en 2 maar vaak is het eenvoudiger om de symbolen -1, 0 en 1 te gebruiken. We zullen in deze tekst afwisselen tussen deze notaties, naargelang de bruikbaarheid.In het eindige veld $\F_3$ sommeren en vermenigvuldigen we de elementen modulo 3. De samenstellingregels worden samengevat in de volgende Cayleytabellen.
\begin{center}
\begin{tabular} {c c}
\begin{tabular}{c|c c c }
$+_3$ & $0$ & $1$ & $2$ \\\hline
$0$ & $0$ & $1$ & $2$ \\
$1$ & $1$ & $2$ & $0$ \\
$2$ & $2$ & $0$ & $1$
\end{tabular}
&
\begin{tabular}{c|c c c }
$\times _3$ & $0$ & $1$ & $2$ \\\hline
$0$ & $0$ & $0$ & $0$ \\
$1$ & $0$ & $1$ & $2$ \\
$2$ & $0$ & $2$ & $1$
\end{tabular}
\end{tabular}
\end{center}
Als we vier verschillende eigenschappen van het gewone SETspel in rekening willen brengen, doen we dit best via viertallen. We werken dus in de verzameling $\F_3^4$. De element van deze verzameling kunnen we 'kaarten' noemen maar we mogen ze ook 'punten' noemen. Deze benaming legt een eerste link naar de meetkunde.
In de verzameling $\F_3^4$ kunnen we snel nagaan of een drietal kaarten een set vormt. Zo is het duidelijk dat de kaarten $(1,0,2,2), (2,0,2,0)$ en $(0,0,2,1)$ aan de voorwaarden voldoen. De eerste en de laatste co\"ordinaat komen immers in drie vari\"eteiten voor. De tweede en de derde co\"ordinaat zijn identiek over de drie speelkaarten. Algebra\"isch stellen we vast dat de som van deze viertallen gelijk is aan $(0,0,0,0)$ als we modulorekenen met grondtal 3:
\[(1,0,2,2)+(2,0,2,0)+(0,0,2,1) \stackrel{3}{=} (3,0,6,3)\stackrel{3}{=} (0,0,0,0)\]
Dit is een nodige en voldoende voorwaarde opdat drie punten een set zouden vormen. Dit inzicht leidt meteen tot een eerste stelling.
\begin{stelling}
Drie punten in $\F_3$ vormen een set als en slechts als ze collineair zijn.
\end{stelling}
\begin{bewijs}
Neem drie willekeurige punten $a, b, c \in \F_3^4$. Ze vormen een set wanneer de overeenkomstige co\"ordinaten van de drie punten ofwel de verzameling $\{0, 1, 2\}$ overspannen ofwel onderling gelijk zijn. In elk van deze gevallen is de som van de co\"ordinaten gelijk aan 0 (modulo 3). Hieruit volgt dat $a+b+c=0$. We merken op dat in het rechterlid de nulvector staat (het neutraal element van $\F_3^4$ voor de optelling) en niet het getal nul. Het is niet moeilijk om in te zien dat ook het omgekeerde waar is: als de som van drie getallen uit $\F_3$ nul is dan zijn deze getallen alledrie gelijk of dan overspannen ze de verzameling $\{0, 1, 2\}$.
Om aan te tonen dat de punten $a$, $b$ en $c$ collineair zijn, bewijzen we nu dat de richtingsvectoren $b-a$ en $c-b$ gelijk zijn.
\begin{align*}
& a+b+c=0\\
\Leftrightarrow \quad & a+b=-c\\
\Leftrightarrow \quad & a+2b=b-c\\
\Leftrightarrow \quad & a-b=b-c \hspace{300pt} \qed
\end{align*}
\end{bewijs}
\begin{opmerking}
Aangezien we de viertallen $a$ en $b$ punten noemen, kunnen we $ab$ formeel een rechte noemen. Elke rechte bestaat uit drie punten, die samen een set vormen.
\end{opmerking}
\subsection{Een visuele voorstelling}
Visueel kunnen we de vectorruimte $\F_3^3$ op een natuurlijke manier voorstellen als een verzameling van 27 punten, geordend in een kubusvormig kristalrooster. Bij uitbreiding stellen we de vectorruimte $\F_3^4$ voor als een stapeling van drie van deze kristalroosters. In figuur 3 zien we de 81 punten van het gewone SETspel. Drie van de punten zijn in blauw geaccentueerd. Ze vormen een set. Je kan snel zien dat de stippen één eigenschap gemeen hebben, nl.~ de ligging op de bovenste laag van elke kubus. De drie andere eigenschappen komen in alle varianten voor: de punten liggen in drie verschillende profielvlakken, ze liggen in drie verschillende fontvlakken en ze liggen in drie verschillende kubussen.
\begin{figure} [h]
\centering
\includegraphics[width=0.8 \textwidth]{setvierdimensionaal.jpg}
\caption{Visuele voorstelling van 81 kaarten met een set}
\end{figure}
Het is ook eenvoudig een SETspel met 9 kaarten meetkundig voor te stellen. Je denkt dan aan 9 punten in een vlak rooster. In dit rooster vind je 12 verschillende rechten. Zoals je in figuur 4 kan zien, zijn er 4 keer 3 evenwijdige rechten in dit vlak (drie rode, drie blauwe, drie groene en drie paarse). De term \emph{rechte} moet hier in ruime zin ge\"interpreteerd worden. Hoewel het punt in het midden een speciale rol lijkt te spelen, verschilt het in niets van alle andere punten. Door elk punt gaan immers vier rechten (van een verschillende kleur).
\begin{figure} [ht]
\centering
\includegraphics[width=0.3 \textwidth]{affiene_vlak_orde_3.jpg}
\caption{Affiene vlak van orde 3}
\end{figure}
De technische naam van dit vlak is het affiene vlak van orde 3. Net zoals in de gewone affiene vlakke meetkunde, kunnen we de puntenverzameling aanvullen met punten op oneindig. Twee of meer evenwijdige rechten hebben hetzelfde punt op oneindig. Dit punt bepaalt dan de richting van evenwijdige rechten. Aangezien het affiene vlak van orde 3 over 4 richtingen beschikt, kunnen we 4 punten op oneindig toevoegen. Zo verkrijgen we het projectieve vlak van orde 3 dat afgebeeld is in figuur 5. Dit projectieve vlak heeft als eigenschap dat elke rechte 4 punten bevat en dat elk punt op 4 rechten ligt. De beschouwing over het projectieve vlak was een tussendoortje dat verder weinig belang heeft voor het oplossen van het SETprobleem.
\begin{figure} [ht]
\centering
\includegraphics[width=0.4 \textwidth]{projectievevlakordedrie.jpg}
\caption{Projectieve vlak van orde 3}
\end{figure}
\subsection{Rechten, vlakken en hypervlakken}
Rechten, vlakken en hypervlakken zijn linaire deelvari\"eteiten van de vierdimensionale ruimte $\F_3^4$. Net zoals in de gewone ruimtemeetkunde worden ze bepaald door een steunvector en een aantal onafhankelijke richtingsvectoren.
Een rechte met steunvector $a$ en richtingsvector $u$ kunnen we omschrijven met $p=a + r \cdot u$, waarbij $p$ een willekeurig punt op de rechte voorstelt. Een vlak met steunvector $a$ en met lineair onafhankelijke richtingsvectoren $u$ en $v$ kunnen we op een gelijkaardige manier omschrijven door het voorschrift $p= a + r \cdot u + s \cdot v$. En tot slot kan een driedimensionaal hypervlak in de vierdimensionale ruimte op de volgende manier omschreven worden:$p= a + r \cdot u + s \cdot v + t \cdot w$. De vector $a$ is een steunvector en de vectoren $u$, $v$ en $w$ zijn onderling onafhankelijke richtingsvectoren. Een hypervlak in de vierdimensionale ruimte noemen we een volume (Engels: solid).
\section{Eenvoudige tellingen}
\subsection{Aantal richtingsvectoren}
Om het aantal richtingsvectoren te tellen in een SETruimte gebruiken we best de co\"ordinaten -1, 0 en 1. Laten we beginnen met het aantal richtingsvectoren in de driedimensionale ruimte $\F_3^3$. Klassiek hebben richtingsvectoren hun beginpunt in de oorsprong. Voor het eindpunt zijn er bijgevolg nog 26 punten over. Tegengestelde eindpunten, zoals (1, 0, 1) en (-1, 0, -1), geven dezelfde richting aan. Vandaar dat er slechts 13 onderscheiden richtingsvectoren zijn in $Z_3^3$. Je ziet ze afgebeeld in figuur 6.
\begin{figure} [ht]
\centering
\includegraphics[width=0.45 \textwidth]{richtingen.jpg}
\caption{Alle richtingen in een SETruimte met 27 punten}
\end{figure}
Op een gelijkaardige manier maken we een telling van de richtingsvectoren in $\F_3^4$. Als we de oorsprong verbinden met de 80 punten die verschillen van de oorsprong dan hebben we elke richting tweemaal geteld. Hieruit leiden we af dat de vierdimensionale SETruimte 40 richtingsvectoren heeft. Figuur 6 toont 40 richtingsvectoren die hun beginpunt hebben in het punt (0, 0, 0, 0). De vectoren in deze figuur zijn enkel symbolisch getekend. Je mag ze niet interpreteren als vectoren in een driedimensionale ruimte.
\begin{figure} [ht]
\centering
\includegraphics[width=\textwidth]{richtingen2.jpg}
\caption{Alle richtingen in een SETruimte met 81 punten}
\end{figure}
In de tweedimensionale SETruimte zijn er $\frac{9-1}{2}=4$ richtingsvectoren. Dit resultaat was al gekend als het aantal punten op oneindig in het projectieve vlak van orde 3. Algemeen kunnen we stellen dat de $n$-dimensionale ruimte $\F_3^n$ een aantal richtingsvectoren bevat dat gelijk is aan $\frac{3^n-1}{2}$.
\subsection{Aantal rechten, vlakken en hypervlakken}
Een rechte wordt bepaald door een steunpunt en een richtingsvector. In $\F_3^4$ zijn er 81 steunpunten en 40 richtingsvectoren. Elke rechte kan op drie manieren beschreven worden door de keuze van een van de drie punten op deze rechte als steunpunt. Hieruit volgt dat het aantal rechten in de vierdimensionale SETruimte gelijk is aan $\frac{81 \times 40}{3}=1080$.
Een vlak wordt bepaald door een steunpunt en twee onafhankelijke richtingsvectoren. In $\F_3^4$ zijn er 81 keuzemogelijkheden voor het steunpunt en $\binom{40}{2}=780$ stellen van onafhankelijke richtingsvectoren. Via deze telling wordt elk vlak meermaals geteld. Elk vlak kan immers omschreven worden via 9 steuntpunten en $\binom{4}{2}=6$ stellen van richtingsvectoren. Elke van de $81 \times 780$ vlakken wordt dus $9 \times 6$ keer geteld. In totaal zijn er bijgevolg $\frac{81 \times 780}{9 \times 6}=1170$ vlakken.
Tot slot, een volume wordt bepaald door \'e\'en steunpunt en drie onafhankelijk richtingsvectoren. Er zijn 81 punten die als steunpunt kunnen fungeren. Iets moeilijker is het om de drie onafhankelijke richtingen te kiezen. Voor de eerste richting zijn er 40 mogelijkheden, voor de tweede 39 en voor de derde 36 (want er zijn nog twee overblijvende richtingen die samen met de eerste en de tweede richting in hetzelfde vlak liggen). In totaal lijken er dus $81 \times \frac{40 \times 39 \times 36}{3 \times 2 \times 1}$ volumes te zijn. Via deze telling wordt elk volume meermaals bereikt. Een vast volume heeft immers 27 steunpunten en $\frac{13 \times 12 \times 9}{3 \times 2 \times 1}$ drietallen van onafhankelijke richtingen. Elk volume wordt bijgevolg $27 \times \frac{13 \times 12 \times 9}{3 \times 2 \times 1}$ keer geteld. Door de deling van $81 \times \frac{40 \times 39 \times 36}{3 \times 2 \times 1}$ en $27 \times \frac{13 \times 12 \times 9}{3 \times 2 \times 1}$ vinden we 120 volumes.
Er bestaat nog een heel andere manier om het aantal volumes te tellen. Daartoe kijken we naar de cartesische vergelijking van een volume:$ ax+by+cz+du+f=0$. Deze vergelijking ligt vast door de keuze van de parameter $f$ en de keuze van de normaalrichting $(a,b,c,d)$. Voor de parameter $f$ zijn er 3 mogelijkheden. Voor de normaalrichting zijn er 40 mogelijkheden. Het product van deze aantallen is 120.
\subsection{Tellingen binnen een rechte, binnen een vlak en binnen een volume}
De manier van tellen uit de vorige paragrafen kunnen we nu overdoen in een beperktere SETruimte, bijvoorbeeld in $\F_3^2$ of in $\F_3^3$. Zonder verdere verklaringen vermelden we de volgende resultaten.
\begin{itemize}
\item aantal punten per rechte $=3$
\item aantal punten per vlak $=3^2=9$
\item aantal rechten per vlak $=\frac{9 \times 4}{3}=12$
\item aantal punten per volume $=3^3=27$
\item aantal rechten per volume $=\frac{27 \times 13}{3}=117$
\item aantal vlakken per volume $=\frac{27 \times 13 \times 12}{9 \times 4 \times 3}=39$
\end{itemize}
\subsection{Bundels}
In plaats van te tellen hoeveel rechten er in een bepaald volume zitten, kan je ook tellen hoeveel volumes er rond een bepaalde rechte zitten in de normale SETruimte $\F_3^4$. Bij zulke opdrachten spreken we van het aantal elementen van een bundel. Hieronder enkele resultaten die de lezer zelf kan verifi\"eren.
\begin{itemize}
\item aantal rechten rond een punt $= 40$
\item aantal vlakken rond een punt $= \frac{40 \times 39}{4 \times 3}=130$
\item aantal volumes rond een punt $= \frac {40 \times 39 \times 36}{13 \times 12 \times 9}=40$
\item aantal vlakken rond een rechte $= \frac{39}{3}=13$
\item aantal volumes rond een rechte $= \frac {39 \times 36}{12 \times 9}=12$
\item aantal volumes rond een vlak $= \frac{36}{9}=4$
\end{itemize}
De verzameling van alle rechten door een punt, wordt ook een waaier genoemd. Deze zelfde terminologie gebruiken we voor de verzameling vlakken door een rechte en de verzameling volumes door een vlak.
Deze eenvoudige tellingen staan momenteel nog los van het doel van deze tekst, nl. het vinden van de kleinste verzameling kaarten die noodzakelijk een set bevat. In de volgende paragrafen zoeken we de kleinste sethoudende verzameling in $\F_3^2$, in $\F_3^3$ en in $\F_3^4$.
\section {De kleinste sethouders}
In het gewone SETspel kan je een verzameling van 20 kaarten trekken zonder dat deze een set bevat. Hieronder zie je hier een voorbeeld van. Dit voorbeeld garandeert uiteraard niet dat er in elke verzameling van 21 kaarten noodzakelijk een set zit. Om dit te bewijzen, is er meer nodig dan een toevallig ontdekt voorbeeld.
In dit hoofdstuk trachten we de kleinste sethouders in verschillende SETruimten te detecteren. We zullen hier ook een bewijs van geven aan de hand van eenvoudige tellingen en aan de hand het veralgemeend duivenhokprincipe.
\begin{figure} [ht]
\centering
\includegraphics[width=0.7\textwidth]{geenset.jpg}
\caption{Een verzameling van 20 kaarten zonder set}
\end{figure}
\subsection{In een SETspel met 9 kaarten}
In een SETspel met 9 kaarten kunnen we makkelijk een setvrije verzameling van 4 kaarten vinden. Maar elke verzameling van 5 kaarten zal gegarandeerd een set bevatten. De kleinste sethouder telt dus 5 elementen. We vertalen dit vermoeden in een meetkundige stelling.
Het bewijs van deze stelling ontlenen we aan Benjamin Lent Davis en Diane Maclagan. Davis en Maclagan kozen in http://www.aimath.org/~kaur/misc/set.pdf voor een bewijs uit het ongerijmde.
\begin{figure} [h]
\centering
\includegraphics[width=0.5\textwidth]{setvijfpunten.jpg}
\caption{Vijf willekeurige punten (paars) in een vlak}
\end{figure}
\begin{stelling}
In $\F_3^2$ bevat elke verzameling $M$ van 5 punten minstens 3 collineaire punten.
\end{stelling}
\begin{bewijs}
Veronderstel dat de verzameling $M$ geen collineaire punten heeft. Verdeel de ruimte $\F_2^3$ nu in drie evenwijdige rechten, $R_1$, $R_2$ en $R_3$. Als we 5 punten van $M$ verdelen over 3 disjuncte verzamelingen en er liggen geen drie punten op dezelfde rechte dan moeten twee rechten twee punten bevatten en \'e\'en rechte \'e\'en punt. Noem dit ge\"isoleerde punt $A$ en stel dat $A \in R_1$.
Door het punt $A$ gaan 4 rechten. E\'en van deze rechten, nl. $R_1$, bevat geen extra punt van $M$. Er blijven dus nog 3 rechten over waarop de 4 overblijvende punten van $M$ liggen. Via het veralgemeende duivenhokprincipe weten we nu dat \'e\'en van deze rechten 2 punten van $M$ moet bevatten naast het punt $A$. Deze rechte bevat in totaal dus 3 punten van $M$. \qed
\end{bewijs}
\subsection{In een SETspel met 27 kaarten}
In een SETspel met 27 kaarten kunnen we ten hoogste een setvrije verzameling vinden met 9 kaarten. We kunnen deze setvrije verzameling laten zien door een foto te nemen van een 9-tal van deze kaarten. Maar visueel is het dan niet meteen duidelijk dat deze verzameling setvrij is. Daarom stellen we deze verzameling meetkundig voor. Probeer in gedachte te achterhalen waarom geen drietal van de paarse punten in figuur 9 op \'e\'en rechte gelegen is.
\begin{figure} [ht]
\centering
\includegraphics[width=0.5\textwidth]{setloos.jpg}
\caption{Negen setloze punten punten (paars) in een volume}
\end{figure}
De kleinste verzameling kaarten die gegarandeerd een sethouder is in een spel met 27 kaarten telt 10 kaarten. Om dit te bewijzen is het uiteraard niet voldoende om een setloze verzameling met 9 kaarten te vinden, zoals in figuur 9. We vertalen deze stelling over de minimale sethouders nu in een meetkundige context. Het bewijs van deze stelling is opnieuw ontleend aan Benjamin Lent Davis en Diane Maclagan.
\begin{stelling}
In $\F_3^3$ bevat elke verzameling $M$ van 10 punten 3 collineaire punten.
\end{stelling}
\begin{bewijs}
Stel $M$ een deelverzameling van $\F_3^3$ waarin geen drietal punten collineair is. Verdeel de SETruimte $\F_3^3$ in drie evenwijdige vlakken, $V_1$, $V_2$ en $V_3$. Aangezien in geen van deze vlakken 5 punten van $M$ kunnen liggen, zal het hoogste aantal punten per vlak 4 zijn en het laagste aantal punten per vlak 2 (in de configuratie (2, 4, 4)) of 3 (in de configuratie (3, 3, 4)) zijn. Kies nu een vlak met 2 of 3 punten en noem het $V_1$. Er blijven dus nog 7 of 8 punten van $M$ over die niet tot het vlak $V_1$ behoren.
\begin{figure} [ht]
\centering
\includegraphics[width=0.7\textwidth]{settienpunten.jpg}
\caption{Tien willekeurig punten (paars) in een volume}
\end{figure}
Neem twee punten uit $V_1$ en noem deze $A$ en $B$. Je kan met een eenvoudige telling nagaan dat het aantal vlakken in $\F_3^3$ door de rechte $AB$ gelijk is aan 4. E\'en van deze 4 vlakken, nl. $V_1$, bevat hoogstens \'e\'en extra punt van $M$. De andere 3 vlakken moeten dus minstens 7 andere punten van $M$ bevatten. Via het veralgemeende duivenhokprincipe kunnen we dan besluiten dat \'e\'en van deze vlakken minstens 3 van deze overblijvende punten bevat. Samen met de oorspronkelijke punten $A$ en $B$, liggen er dus minstens 5 verschillende punten van $M$ in dit vlak. \qed
\end{bewijs}
\subsection{In een SETspel met 81 kaarten}
Voor het gewone SETspel met 81 kaarten zullen niet op een gelijkaardige manier kunnen aantonen hoe groot de kleinste sethouder is. Er zullen moeilijkere redeneringen nodig zijn dan het tellen van elementen in een bundel gecombineerd met het duivenhokprincipe. Niettegenstaande deze weinig hoopgevende inleiding, doen we toch een poging om met analoge redeneringen tot een resultaat te komen. De stellingen en bewijzen hieronder zijn afkomstig van wiskundecollega Dirk Danckaert.
\begin{stelling}
Elke deelverzameling $M$ van $\F_3^4$ met 47 punten bevat minstens 3 collineaire punten.
\end{stelling}
\begin{bewijs}
De 47 punten van $M$ bevatten $\binom{47}{2}=1081$ koppels van punten die elk een rechte bepalen. Er zijn slechts 1080 rechten in $\F_3^4$. Minstens \'e\'en van deze rechten bevat dus 2 van deze tweetallen (veralgemeende duivenhokprincipe) en dus 3 van deze punten. \qed
\end{bewijs}
\begin{stelling}
Elke deelverzameling $M$ van $\F_3^4$ met 42 punten bevat minstens 3 collineaire punten.
\end{stelling}
\begin{bewijs}
Neem een vast punt $A$ uit $M$ en combineer dit punt met elk van de 41 andere punten. Je vindt zo 41 rechten door $A$. Er zijn slechts 40 rechten door een vast punt $A$. E\'en van deze rechten zal dus, naast $A$ zelf, nog 2 andere punten van $M$ bevatten (veralgemeende duivenhokprincipe). Zo vinden we een rechte waarop 3 punten van $M$ liggen. Omdat rechten in $\F_3$ slechts drie punten bevatten, is deze rechte volledig bevat in $M$. \qed
\end{bewijs}
\begin{stelling}
Elke deelverzameling $M$ van $\F_3^4$ met 30 punten bevat minstens 3 collineaire punten.
\end{stelling}
\begin{bewijs}
Neem een vast punt $A$ uit $M$ en combineer dit punt met elk van de $\binom{29}{2}=406$ paren van overblijvende punten. Tenzij \'e\'en van deze drietallen al collineair zou zijn, vind je zo 406 vlakken door het punt $A$. Er zijn in totaal slechts 130 vlakken rond een punt. E\'en van deze vlakken bevat dus minstens 4 van deze paren punten (veralgemeende duivenhokprincipe). Dat kan enkel als dit vlak 4 of meer van de 29 punten bevat. Mocht het immers slechts 3 van de 29 punten bevatten dan kunnen hieruit slechts 3 paren gevormd worden. Samen met het punt $A$ bevat dit vlak dus 5 punten uit de verzameling $M$. Wegens stelling 3.1 is dit vlak niet setloos \qed
\end{bewijs}
\begin{stelling}
Elke deelverzameling $M$ van $\F_3^4$ met 29 punten bevat minstens 3 collineaire punten.
\end{stelling}
\begin{bewijs}
Neem twee vaste punten $A$ en $B$ uit $M$ en combineer dit punt met elk van de 274 overblijvende punten van $M$. Tenzij \'e\'en van deze drietallen al collineair zou zijn, vind je 27 vlakken door de rechte $AB$. De vlakkenwaaier door $AB$ heeft slechts 13 elementen. E\'en van deze vlakken zal dus minstens 3 van de 27 punten bevatten (veralgemeend duivenhokprincipe). Samen met de punten $A$ en $B$ liggen er dus 5 punten van $M$ in dit vlak. Dit betekent dat dit vlak niet setloos is. \qed
\end{bewijs}
\begin{stelling}
Elke deelverzameling $M$ van $\F_3^4$ met 28 punten bevat minstens 3 collineaire punten.
\end{stelling}
\begin{bewijs}
Deel de ruimte $\F_3^4$ op in de disjuncte unie van drie evenwijdige volumes. E\'en van deze volumes bevat 10 punten van $M$ (veralgemeend duivenhokprincipe). Dit betekent dat dit volume niet setloos is. \qed
\end{bewijs}
\begin{stelling}
Elke deelverzameling $M$ van $\F_3^4$ met 25 punten bevat minstens 3 collineaire punten.
\end{stelling}
\begin{bewijs}
We tonen eerst aan dat ofwel de stelling bewezen is ofwel er minstens 4 van deze punten coplanair zijn . Neem alle $\binom {25}{3}=2300$ drietallen van punten uit de verzameling $M$. Ofwel zijn er 3 coplanair. Zo niet vinden we 2300 vlakken. Er zijn slechts 1170 vlakken in $\F_3^4$. E\'e van deze vlakken bevat dus minstens twee drietallen uit $M$ en dus minstens 4 punten.
Combineer nu deze 4 punten met elke van de overige 21 punten van $M$. Ofwel ligt \'e\'en van deze 21 punten in het vlak van de vier punten. Er liggen dan 5 punten van $M$ in dit vlak waardoor het niet setloos is. Ofwel ligt geen van de 21 punten in het vlak van de 4 punten. We hebben dan een waaier van 21 volumes door het vlak van 4 punten. Deze waaier heeft slechts 4 elementen. E\'en van deze volumes bevat dus minstens 6 van de overige 21 punten (duivenhokprincipe). Samen met de 4 eerste punten liggen er dan 10 punten van $M$ in dit volume waardoor het niet setloos is. \qed
\end{bewijs}
\section {De techniek van de dubbele telling}
Met de technieken die we hierboven gebruikten, wordt het zeer moeilijk om de ondergrens voor de sethoudende verzamelingen verder naar beneden te halen dan 25. Daarom zetten we hier een nieuw wapen in: de techniek van de dubbele telling. We namen dit idee opnieuw over van Davis en Maclagan. Om zachtjesaan op te bouwen, hernemen we eerst een reeds bewezen stelling, zij het met een nieuw bewijs.
\begin{stelling}
In $\F_3^3$ bevat elke verzameling $M$ van 10 punten 3 collineaire punten.
\end{stelling}
\begin{bewijs}
Stel dat de verzameling $M$ geen drietal collineaire punten bevat.
We splitsen de ruimte $\F_3^3$ nu op in vlakkenlagen met 3 evenwijdige vlakken, $V_1$, $V_2$ en $V_3$. Geen van deze vlakken kan 5 punten bevatten. De enige twee mogelijkheden voor de puntenconfiguraties zijn $(2, 4, 4)$ en $(3, 3, 4)$. Stel dat de puntenconfiguratie $(2, 4, 4)$ in totaal $a$ keer voorkomt bij zulke opsplitsingen in vlakkenlagen en dat de puntenconfiguratie $(3, 3, 4)$ in totaal $b$ keer voorkomt. We kunnen de aantallen $a$ en $b$ berekenen uit een stelsel met twee vergelijkingen.
Het aantal manier om $\F_3^3$ in 3 evenwijdig vlakken op te splitsen is 13. Je kan dit als volgt zien. Als \'e\'en van deze vlakken vast ligt, liggen de drie evenwijdige vlakken vast. Je hoeft dus alleen maar naar bijvoorbeeld het vlak door de oorsprong te kijken. In $\F_3^3$ zijn er 13 vlakken door de oorsprong. Bijgevolg zijn er ook 13 opsplitsingen in 3 evenwijdige vlakken. Hieruit volgt dat
\begin{equation}
a+b=13.
\end{equation}
De tweede vergelijking vinden we door \'e\'en bepaalde verzameling op twee manieren te tellen. Het gaat hier over de verzameling van alle vlakken die door twee punten van $M$ gemarkeerd worden. Elk element van deze verzameling is te schrijven als $\big( V, \{x, y\} \big)$ waarbij $x$ en $y$ elementen zijn van $M$ en waarbij $V$ een vlak is dat de punten $x$ en $y$ omvat.
Bij de eerste telling tellen we eerst de puntenparen en daarna de vlakken die erdoor gaan. Er zijn in totaal $\binom{10}{2}=45$ puntenparen en door elke puntenpaar gaan er 4 vlakken. Zo komen we op 180 elementen.
Bij de tweede telling tellen we eerst de vlakken en daarna de puntenparen die erin liggen. Bij de $a$ configuraties van de vorm $(2, 4, 4)$ kunnen we op $\binom{2}{2}+\binom{4}{2} +\binom{4}{2}=13$ manieren een paar kiezen van twee punten die in hetzelfde vlak van de vlakkenlaag liggen. Maar bij de $b$ configuraties van de vorm $(3, 3, 4)$ zijn er slechts $\binom{3}{2}+\binom{3}{2} +\binom{4}{2}=12$ manieren om twee punten te kiezen die in hetzelfde vlak van de vlakkenlaag liggen. In totaal komen we dus op $13a+12b$ elementen in deze verzameling.
Door de gelijkstelling van de twee tellingen vinden we dat
\begin{equation}
13a+12b=180.
\end{equation}
Uit (1) en (2) leiden we af dat $a=24$ en $b=-11$. Dit is onmogelijk. De getallen $a$ en $b$ zijn immers natuurlijke getallen. De basisveronderstelling was dus fout. \qed
\end{bewijs}
Na dit bewijs kunnen we op een gelijkaardige manier te werk gaan om de eindstelling te bewijzen. Ditmaal zullen er in plaats van 2 onbekenden 7 onbekenden in een bepaald stelsel moeten gezocht worden.
\begin{stelling}
In $\F_3^4$ bevat elke verzameling $M$ van 21 punten 3 collineaire punten.
\end{stelling}
\begin{bewijs}
Stel dat de verzameling $M$ geen drietal collineaire punten bevat.
We splitsen de ruimte $\F_3^4$ nu herhaaldelijk op in 3 evenwijdige volumes, $V_1$, $V_2$ en $V_3$. Omdat er geen tien punten in \'e\'en volume mogelijk zijn, kunnen enkel de volgende zeven puntenconfiguraties voorkomen: $(3, 9, 9), (4, 8, 9), (5, 7, 9), (6, 6, 9), (5, 8, 8), (6, 7, 8)$ en $(7, 7, 7)$. Het aantal keer dat elke configuratie bij deze opsplitsingen in evenwijdige volumes kan voorkomen, is respectievelijk gelijk aan $a, b, c, d, e, f$ en $g$. Deze 7 onbekenden proberen we nu te berekenen aan de hand van een stelsel.
Het aantal manier om $\F_3^4$ in 3 evenwijdig volumes op te splitsen is 40. Je kan dit als volgt zien. Als \'e\'en van deze volumes vast ligt, liggen de drie evenwijdige volumes vast. Je hoeft dus alleen maar naar bijvoorbeeld het volume door de oorsprong te kijken. In $\F_3^4$ zijn er 40 volumes door de oorsprong. Bijgevolg zijn er ook 40 opsplitsingen in 3 evenwijdige volumes. Hieruit volgt dat
\begin{equation}
a+b+c+d+e+f+g=13.
\end{equation}
Een volgende vergelijking vinden we door een speciale verzameling op twee manieren te tellen. Het gaat over de verzameling van alle koppels $\big( V, \{x, y\} \big)$ waarbij $x$ en $y$ elementen zijn van $M$ en waarbij $V$ een volume is dat de punten $x$ en $y$ omvat. Deze verzameling bestaat uit vlakken die gemarkeerd zijn door een paar van punten uit $M$. Als we eerst de puntenparen tellen, nl. $\binom{21}{2}=210$, en daarna het aantal volumes door een puntenpaar, nl. 13, dan vinden we $210 \cdot 13=2730$ elementen in deze verzameling. Als we eerst de opsplitsing in evenwijdige volumes vastleggen en daarna de puntenparen tellen die in eenzelfde volume van de volumeopsplitsing liggen, dan vinden we:
\[\Big( \binom{3}{2} +\binom{9}{2} +\binom{9}{2} \Big) a + \Big( \binom{4}{2} +\binom{8}{2} +\binom{9}{2} \Big) b +\Big( \binom{5}{2} +\binom{7}{2} +\binom{9}{2} \Big) c +\Big( \binom{6}{2} +\binom{6}{2} +\binom{9}{2} \Big) d\]
\[+ \Big( \binom{5}{2} +\binom{8}{2} +\binom{8}{2} \Big) e +\Big( \binom{6}{2} +\binom{7}{2} +\binom{8}{2} \Big) f +\Big( \binom{7}{2} +\binom{7}{2} +\binom{7}{2} \Big) g.\]
De tweede vergelijking verkrijgen we door gelijkstelling van de twee tellingen:
\begin{equation}
75a+70b+67c+66d+66e+64f+63g=2730.
\end{equation}
Analoog kunnen we een derde vergelijking opstellen. We tellen nu alle koppels $\big( V, \{x, y,z \} \big)$ van volumes en drietallen punten die dit vlak markeren. Tellen we eerst de drietallen, nl. $\binom{21}{3}=1330$ en daarna de volumes die door elk drietal gaan, nl. 4, dan komt de telling uit op $1330 \cdot 4=5320$. Tellen we eerst de opsplitsing in evenwijdige volumes en daarna de puntentrio's dan vinden we:
\[\Big( \binom{3}{3} +\binom{9}{3} +\binom{9}{3} \Big) a + \Big( \binom{4}{3} +\binom{8}{3} +\binom{9}{3} \Big) b +\Big( \binom{5}{3} +\binom{7}{3} +\binom{9}{3} \Big) c +\Big( \binom{6}{3} +\binom{6}{3} +\binom{9}{3} \Big) d\]
\[+ \Big( \binom{5}{3} +\binom{8}{3} +\binom{8}{3} \Big) e +\Big( \binom{6}{3} +\binom{7}{3} +\binom{8}{3} \Big) f +\Big( \binom{7}{3} +\binom{7}{3} +\binom{7}{3} \Big) g.\]
De gelijkstelling van de twee tellingen levert de laatste vergelijking op:
\begin{equation}
169a+144b+129c+124d+122e+111f+105g=5320.
\end{equation}
Normaliter zijn de vergelijkingen (3), (4) en (5) samen niet krachtig genoeg om samen de 7 onbekenden $a, b, c, d, e, f$ en $g$ te kunnen bepalen. Ditmaal hebben we echter geluk. We zoeken enkel positieve oplossingen. En de rechterleden van de vergelijkingen zijn op dezelfde manier lineair afhankelijk van elkaar als de co\"effici\"enten van $a$ en de co\"effici\"enten van $g$. Erg toevallig maar ook erg nuttig. Als we nu 693 keer (3) nemen verminderd met 16 keer (4) en vermeerderd met 3 keer (5) dan vinden we
\[5b+8c+9d+3e+2f=0\]
waaruit volgt dat
\[b=c=d=e=f=0.\]
Na substitutie van de gevonden variabelen kunnen we (4) en (5) samenvoegen tot het stelsel:
\[\left\{
\begin{array}{l}
a +g = 40 \\
75a +63g = 2730.
\end{array}
\right.\]
Dit betekent dat $a=17,5$ en $g=22,5$ wat in strijd is met de veronderstelling dat $a$ en $g$ natuurlijke getallen zijn. Het uitgangspunt dat geen drietal punten van $M$ collineair is, was dus fout. \qed
\end{bewijs}
\tableofcontents
\end{document}
