rooster van lampen

Opgave - APMO 2007 vraag 5

Een $5\times 5$ rooster van lampen (met elk hun eigen schakelaar) is defect: als je de schakelaar van één lamp omschakelt, schakelen de lampen boven, onder, links en rechts van die lamp ook om (van aan naar uit of omgekeerd).

Guolong speelt wat met de lichtjes (die bij de start allemaal uitstaan) en na een aantal keer te schakelen, brandt er precies één lamp. Welke posities kan deze lamp staan?

Oplossing

Zij $S$ de verzameling lampen met een sterretje in $$\begin{array}{|c|c|c|c|c|}
\hline\star&\star&\hphantom{\star}&\star&\star\\
\hline & & & & \\
\hline\star&\star& &\star&\star \\
\hline & & & & \\
\hline\star&\star& &\star&\star \\
\hline\end{array}$$
en $T$ het spiegelbeeld van $S$ rond een diagonale as. Beide hebben duidelijk invariante pariteit van het aantal lampen dat aan is op ieder tijdstip, dus als alle lampen uit starten, kan nooit precies één lamp uit $S$ of $T$ aan zijn. Dus er blijven nog slechts $5$ posities over: de centrale en de vier diagonaal aangrenzende vakjes.

Het centrale vakje kan door de volgende lampen te switchen: $\begin{array}{|c|c|c|c|c|}
\hline & & &\star&\star\\
\hline & &\star& & \\
\hline &\star&\star& &\star \\
\hline\star& & & &\star \\
\hline\star& &\star&\star& \\
\hline\end{array}$, en de schuindiagonale kunnen door (elk op rotatie na) volgende lampen te switchen: $\begin{array}{|c|c|c|c|c|}
\hline &\star& &\star& \\
\hline\star&\star& &\star&\star\\
\hline & & &\star& \\
\hline\star&\star&\star& & \\
\hline &\star& & & \\
\hline\end{array}$, dus deze $5$ posities zijn inderdaad mogelijk.