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? 😀
Best Answer
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.