Lampjes uit

Aan het begin van het spel zijn alle lampjes aan. Als je op een lampje klikt verandert zijn stand en die van zijn buren. Het doel van het spel is alle lampjes uit te krijgen. Dit is altijd mogelijk.

Nieuwe graaf Opnieuw beginnen

Bewijs

We gebruiken de notatie $G=(V,E)$ voor de graaf $G$ met puntenverzameling $V$ en lijnenverzameling $E$. Het totale aantal lijnen noemen we $n$.

Verzamelingen lijnen als vectoren

Bekijk $A={\mathcal P}(E)$, de verzameling deelverzamelingen van $E$, als vectorruimte over ${\bf F}_2=\{0,1\}$, het lichaam met twee elementen. Een vector $x\in A$ is dus een deelverzameling van $E$ die we ook kunnen schrijven als een rijtje nullen en enen, één per lijn om aan te geven of deze in $x$ zit of niet. De optelling van twee vectoren $x$ en $y$ is het symmetrische verschil $x+y:=x\Delta y=(x\setminus y) \cup (y\setminus x)$. Dit komt neer op het optellen van de nullen en enen, met de regel $1+1=0$.

De cykelruimte

Een cykel is een vector uit $A$ die bestaat uit een aantal lijnen die een rondje vormen. Zij $C$ de deelruimte opgespannen door de cykels. Elke vector van $C$ kun je dus zien als de som van een aantal cykels. Merk op dat in elke cykel elk punt twee buren heeft, en dus dat elk punt van $V$ een even aantal buren in $x$ heeft voor alle $x\in C$. Andersom, als elk punt van $V$ een even aantal buren in $x$ heeft, is $x\in C$. Immers, bekijk de langste wandeling over de lijnen van $x$ waarbij je hooguit één keer over elke lijn loopt. Deze wandeling kan niet eindigen bij een punt waar je nog niet geweest bent, omdat dat laatste punt (en het beginpunt van de wandeling) dan een oneven aantal buren zou hebben. Dus $x$ bevat een cykel. Haal deze cykel even weg uit $x$ en herhaal het argument tot je $x$ helemaal hebt opgedeeld in cykels.

De snederuimte

Als je $V$ in tweeën deelt, dan heet de verzameling lijnen tussen die twee delen een snede. Zij $x$ de snede gegeven door $V=V_1\cup V_2$ en $y$ de snede gegeven door $V=V'_1\cup V'_2$. Dan bestaat $x+y$ uit de lijnen die wel in $x$ maar niet in $y$ zitten en de lijnen die wel in $y$ maar niet in $x$ zitten, ofwel: de lijnen die de grens tussen $V_1$ en $V_2$ overbruggen maar niet die tussen $V'_1$ en $V'_2$, of juist andersom. Het zijn dus precies de lijnen tussen $(V_1\cap V'_1)\cup (V_2\cap V'_2)$ en $(V_1\cap V'_2)\cup (V_2\cap V'_1)$, dus is $x+y$ ook een snede. De verzameling sneden is dus een deelruimte van $A$, die we aangeven met $S$.

Orthogonale complementen

Bekijk de bilineaire vorm $\langle x, y\rangle:=\sum_{i=1}^n x_i y_i$. Deze is $0$ of $1$ afhankelijk van of $x\cap y$ een even of oneven aantal lijnen bevat. Voor een deelruimte $W$ van $A$ schrijven we $W^\perp$ voor het orthogonale complement, de ruimte van de vectoren $x\in A$ zodat $\langle x,y\rangle=0$ voor alle $y\in W$. Dan is $W^\perp$ de kern van de afbeelding gegeven door de matrix met als rijen een basis van $W$. Wegens de rank-nullity theorem geldt dus $\operatorname{dim}\,W+\operatorname{dim}\,W^\perp=n$. Omdat per definitie voor elke $x\in W^\perp$ geldt dat $\langle x, y\rangle=0$ voor alle $y\in W$ hebben we de implicatie $y\in W\Rightarrow y\in W^{\perp\perp}$, dus $W^{\perp\perp}\supseteq W$. Maar $\operatorname{dim}\,W^\perp+\operatorname{dim}\,W^{\perp\perp}=n=\operatorname{dim}\,W+\operatorname{dim}\,W^\perp$ dus $\operatorname{dim}\,W^{\perp\perp}=\operatorname{dim}\,W$ en dus $W^{\perp\perp}=W$.

Cykelruimte en snederuimte zijn complementair

Zij $s\in S$ een snede, dus een splitsing van $V$ in twee delen. Als je vanaf een zekere plek rond gaat rondlopen door de graaf, zul je voor elke keer dat je de splitsing oversteekt, deze nog een keer moeten oversteken om weer terug te komen waar je begonnen was. Elke cykel $c$ heeft dus een even aantal lijnen gemeen met $s$, ofwel $\langle c,s\rangle=0$ voor alle $c\in C$ en $s\in S$, dus $C\subseteq S^\perp$. Als $x$ nu een vector is die niet in $C$ zit, is er minstens één punt $v\in V$ met een oneven aantal lijnen in $x$. Zij $s$ de snede bestaande uit alle lijnen van dat punt. Dan is $\langle s,x\rangle=1\neq 0$ dus $x\not\in S^\perp$, dus $C=S^\perp$. Nemen we van deze uitdrukking het complement, dan vinden we bovendien $C^\perp=S^{\perp\perp}=S$.

Alle lijnen als som van cykels en een snede

Met de notatie $C+S$ bedoelen we de ruimte bestaande uit alle $c+s$ met $c\in C$ en $s\in S$. Als $\langle x,c+s\rangle=0$ voor alle $c\in C$ en $s\in S$ dan geldt in het bijzonder dat $\langle x,c+0\rangle=0$ en $\langle x,0+s\rangle=0$, dus $(C+S)^\perp\subseteq C^\perp\cap S^\perp$. Andersom volgt uit de bilineariteit van $\langle\cdot,\cdot\rangle$ dat als $\langle x,c\rangle=0$ en $\langle x,s\rangle=0$, dan $\langle x,c+s\rangle=0+0=0$. Hieruit volgt $(C+S)^\perp\supseteq C^\perp\cap S^\perp$ dus $(C+S)^\perp=C^\perp\cap S^\perp=S\cap C$ ofwel $C+S=(S\cap C)^\perp$. Als $x\in S\cap C$, dan $\langle x,x\rangle=0$ dus $x$ heeft een even aantal enen. Maar dan is ook $\langle E,x\rangle=0$, dus $E\in (S\cap C)^\perp$ ofwel $E\in C+S$. Dus er bestaat een snede $s\in S$ zodat $E-s\in C$. Bij elke graaf kun je dus een zekere snede weghalen, zodat alle punten een even aantal buren overhouden.

Oplossing van het spel

Zij $G'=(V',E')$ de graaf verkregen door een punt $p$ aan $V$ toe te voegen en die met alle punten te verbinden die een even aantal buren hebben. (Nu hebben alle punten, behalve $p$ misschien, een oneven aantal buren.) Zij $V'=V_1\cup V_2$ de tweedeling behorende bij de snede na wiens verwijdering alle punten een even aantal buren overhouden. Als $p$ in $V_2$ zit, klik dan op alle lampjes in $V_1$. Elk lampje in $V_1$ wordt nu een oneven aantal keer geschakeld: één keer omdat erop geklikt wordt en een even aantal keer omdat op een buur geklikt wordt. Elk lampje in $V_2$ (behalve mogelijk $p$) wordt ook een oneven aantal keer geschakeld: het heeft een even aantal buren in $V_2$ maar in totaal een oneven aantal buren, dus een oneven aantal buren in $V_1$. Alle lampjes zijn een oneven keer geschakeld, en zijn nu dus uit.