There is a bulb in each cell of an n x n board. Initially all the bulbs are off. If a bulb is touched, that bulb and all the bulbs in the same row and column change state (those that are on, turn off, and those that are off, turn on). Show that it is possible by touching m bulbs to turn all the bulbs on. What is the minimum possible value of m?
Answer
n odd, n is minimum
n even, n2 is minimum
Solution
If n is odd, touch each bulb in the first column. Then bulbs in the first column are each switched n times, which is odd and so end up on. All other bulbs are switched just once, and so end up on. n is obviously minimal, because if m < n, then there is a bulb which is not switched at all (there must be a column with no bulb touched and a row with no bulb touched, so the bulb in that column and row is not switched).
In n is even, touch each bulb. Then each bulb is switched 2n-1 times, so ends up on. We show that it is not possible to do better.
Note first that there is no benefit in touching a bulb more than once, so each must be touched zero of one times. Thus we can represent the scheme as an array of 0s and 1s, where 0 means that the corresponding bulb is not touched, and 1 means that it is touched.
Let A, B, C, D be four values at the corners of a rectangle. We claim that A+B has the same parity as C+D. Let LAB be the number of 1s in the row AB are touched, similarly LBC (the number of 1s in the column BC), LCD, LDA. Since bulb A is switched we must have LAB + LDA + A odd (note that LAB + LDA double-counts the no. of touches of A). Similarly, LBC + LCD + C is odd, so A + C + (LAB + LBC + LCD + LDA) is even. Similarly, considering B and D, we find that B + D + (LAB + LBC + LCD + LDA) is even, so A+C and B+D have the same parity. Adding B+C to both, we get that A+B and C+D have the same parity. It follows that either A = D and B = C, or A ≠ D and B ≠ D.
Keeping A and B fixed, we can now vary C (and hence D). It follows that either the row through B matches that through A, or it has every cell different (to the corresponding cell in row A). Similarly for the other rows. So we have k rows of one type and n-k rows which are equal to its "complement". Suppose first that k = n, so that all rows are the same. If we have all 1s, then we have a solution. If we have all 0s, we obviously do not have a solution. So suppose there is a 0 and a 1 in each row. Then the total count at a 1 is n-1 higher than at a 0 (because of the extra n-1 1s in the same column). So they cannot both be odd (because n is even). Contradiction.
Finally suppose there is a row and a complement row. So position A in one is 1, then position B in the same column in the other has 0. If a row has h 1s, then a complement row has n-h 1s. The column has z 1s, so A has z+h-1 or z+n-h-1 1s, and B has z+h or z+n-h 1s. But since n is even, z+h and z+n-h have the same parity, so A and B have opposite parity. Contradiction. So the only solution for n even is all 1s.
© John Scholes
jscholes@kalva.demon.co.uk
21 January 2004
Last corrected/updated 21 Jan 04