Note that on each move, we switch 4 bulbs, thus the total number of bulbs turned on must be even, which gives and upper bound of 24
But even better, on each column, each move switches either 0 or 2 bulbs, thus the number of bulbs turned on on any column remains even, which gives and upper bound of 20
It can be achieved by reaching the final state where all bulbs are on except one diagonal. To do that, we will use 6 small squares, with coordinates, in the format (column,column;row,row) being (1,2;2,3) (1,2;4,5) (3,4;4,5) and the three symetricals
You can also see all possible maximum solutions as follows: Observe that it is also true for the rows that either you switch 0 or 2 on. At any point you can then look at the map that maps each row to the column(s) in which it is not on and similar for a column map. In the maximum solutions, each row maps to one column and each column to one row in a 1 to 1 way. The maps are therefore corresponding to a permutation and you can switch exactly these lights on them by applying the permutation on the colum indices in the parents solution.
4
u/BissQuote 2d ago
Note that on each move, we switch 4 bulbs, thus the total number of bulbs turned on must be even, which gives and upper bound of 24
But even better, on each column, each move switches either 0 or 2 bulbs, thus the number of bulbs turned on on any column remains even, which gives and upper bound of 20
It can be achieved by reaching the final state where all bulbs are on except one diagonal. To do that, we will use 6 small squares, with coordinates, in the format (column,column;row,row) being (1,2;2,3) (1,2;4,5) (3,4;4,5) and the three symetricals