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

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

-
Somewhat related to math.stackexchange.com/questions/273395/… –  Gerry Myerson Jan 19 '13 at 23:19
If you had an odd number of rows, you could switch every bulb in a single column, so reducing the of clicks. But you do not in this case. –  Henry Jan 19 '13 at 23:25
See my answer to the related MO question, "Randomly switching street lights, in a square city". This is known as the Berlekamp switching game. –  Joseph O'Rourke Jan 19 '13 at 23:26
I've found the Berkelamp switching game in Google. At first sight, it looks kinda related but it's a completely different problem tbh. :) Here you don't have those 20 extra switches for example. –  Healpowah Jan 19 '13 at 23:33
There may be a parity argument which works here. Because the light at the switch point is only switched once (and not twice) - count the number of switches which have been switched in the row and column of a particular light. If you use the row and column totals, you can tell which lights are on and off - but there is a parity adjustment for switch points, because the row and column totals will double-count. –  Mark Bennet Jan 19 '13 at 23:45

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.

-
Thanks. You've really enlightened me. So briefly, you could say there are 2^100 different click combinations and 2^100 states of the board. We just have to prove that all states are possible. You just did that too. Thanks a lot again! :) –  Healpowah Jan 20 '13 at 0:17
Yes, bijectivity is enough to solve the problem, even without the linear algebra framework. In "Lights Out" there is a nonzero kernel and things are not so simple. –  David Moews Jan 20 '13 at 0:23

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.

-