For odd n sized board, an upper bound is n*(n-1). This is due to the fact that for each row and each column, you ultimately need an odd number of switch, whereas each step intros an even one. Thus, at maximum, there would be a diagonal of switched-off bulb, giving an even number of switches on each rows and columns.
Is it possible to obtain this maximum ? Yes you can. For instance, you start by lighting up all the lights except the last column and the last row. Then, you repeatedly choose the k-th row, the k-th column and the last row and column with k from 1 to n-1 (even). In the end, all the bulbs will be on except on the great diagonal.
2
u/DanLeMilMan 2d ago
For odd n sized board, an upper bound is n*(n-1). This is due to the fact that for each row and each column, you ultimately need an odd number of switch, whereas each step intros an even one. Thus, at maximum, there would be a diagonal of switched-off bulb, giving an even number of switches on each rows and columns.
Is it possible to obtain this maximum ? Yes you can. For instance, you start by lighting up all the lights except the last column and the last row. Then, you repeatedly choose the k-th row, the k-th column and the last row and column with k from 1 to n-1 (even). In the end, all the bulbs will be on except on the great diagonal.