board game: 10 by 10 light bulbs, minimum switches to get all off?

Question

Hy all! My problem is as follows: There's a board of 10 by 10 light bulbs. (So it's a square with 10 columns and 10 rows.) Every single bulb has got its own switch. However, something went wrong and when you use a switch not only does it change the state of the proper light bulb but states of all other 18 bulbs in its column (9) and row (9). (a state change obviously means: off lights turn on, on lights turn off) So one click changes the required bulb's state AND all the bulbs in its row and column. How many clicks (switches used) will be needed at least to turn off all the bulbs if they are all on?

I've literally spent hours thinking it over and over. It's kinda straight-forward that the order of the clicks are irrelevant and using the same switch more than once is meaningless. (I mean using the same switch twice is like not using it at all, and using it three times is like only once {only parity (even/odd) matters}.) Consequently, there are 2^100 possibilities, so unfortunately more than a computer could check in reasonable time. Anyway, I would like to have a number with some kind of mathematical proof.

My 'conjecture' is 100. I think one has to use all the switches to change the state of the whole table. (which works because all light bulbs would change 19 times) Although, there may be a better way (with a lesser number of switches)... Any thoughts? :D

Answer 1

The minimum number of switches required is $100$.

This puzzle can be turned into a linear algebra problem over ${\Bbb Z}/2{\Bbb Z}$ by letting the vector $v\in({\Bbb Z}/2{\Bbb Z})^{100}$ record which switches are pressed ($1$ if pressed, $0$ if not), the vector $w\in({\Bbb Z}/2{\Bbb Z})^{100}$ record which lights are initially on ($1$ if on, $0$ if off), and the $100$-by-$100$ matrix $M$ over ${\Bbb Z}/2{\Bbb Z}$ record which switches affect which lights. A given $v$ will then solve the puzzle iff $Mv=w$.

As the questioner points out, $v=(1,\dots,1)^T$ is a solution. To show that this is the only solution, it's enough to show that $M$ is invertible.

Suppose that we press all the switches which are either in row $r$ or in column $c$. If a light is not in row $r$ and not in column $c$, its state will be changed twice. If a light is in row $r$ but not in column $c$, its state will be changed $10$ times, and similarly for a light in column $c$ but not in row $r$. The light at $(r,c)$ will have its state changed $19$ times. Therefore, the only light whose state ends up changing is the one at $(r,c)$. Since any desired light can be toggled, this shows that any configuration of lights can be turned off, so $M$ has full range and so must be invertible.

This puzzle is similar to the electronic game Lights Out.

Answer 2

The only way to light all the squares is to flip all the switches.

The only simple way to prove this is to show that the linear map $f : \Bbb F_2^{100} \to \Bbb F_2^{100}$, that takes the set of switch we flip and gives the set of lights turned on, is injective. Since $f$ is an endomorphism of a finite dimensional vector spaces, it is enough to show that it is surjective, and for symmetry and linearity reasons, to show that there is a way to light up any single light, for example thoe one in the bottom left corner (because the single lights generate $\Bbb F_2^{100}$)

In fact, I prefer to view $\Bbb F_2^{100}$ as $\Bbb F_2[X,Y]/(X^{10}+1, Y^{10}+1)$ instead, so that the map $f$ is now multiplication by $P = 1+X+X^2+...+X^9+Y+Y^2+...+Y^9$.

Let's try to invert $P$ : since in characteristic $2$, $(1+u)^{-1} = 1+u+u^2+u^3+\ldots$ if $u$ is nilpotent, let's just check that $(X+...+X^9+Y+...+Y^9)^2 = X^2+\ldots+X^{18}+Y^2+\ldots+Y^{18} = 1+X^2+X^2+\ldots X^8+X^8+1+Y^2+Y^2+\ldots+Y^8+Y^8 = 0$. (here the fact that the square has an even size is crucial)

Thus $P$ has an inverse, which is in fact $P$ itself : $P^2 = 1$.

And thus the map $f$ is an involution, and this tells you that to obtain a particular picture with the lights, the only way to get it is to switch the switches corresponding to the lights that would be turned on if you switched the lights that you want turned on on your picture (is there a less confusing way to say this ?).

For example, if you want to light the bottom left square, you have to switch the bottom row and the left column ; and if you want to light everything, you have to switch everything.