Using your Head is Permitted

March 2011 solution

Yes, such an arrangement always exists. We will give two proofs of this fact. The first proof is short and elegant but requires some linear algebra. The second proof is elementary.

First, in linear algebraic terms, we are asking whether there is always an x satisfying Mx=b, where Mx=b is a system of linear equations over GF(2), M is an nxn symmetric matrix with ones on the diagonal, x is a vector of length n and b is the all-ones vector of length n. We will prove more generally that over GF(2) the equation Mx=Diag(M) has a solution for every symmteric M.

Suppose that one uses Gaussian elimination to try and find such an x value, the only failure point of the algorithm is if we find a combination of the rows of M, denoted by a vector v as vTM, such that vTM=0, but vTDiag(M)=1. However, 0 = vTMv = vT(L+D+U)v = vTLv + vTDv + vTUv = vTLv + vTDv + (vTLv)T = vTDv = vTDiag(M) The wording used above was adapted from a solution by Oded Margalit. A more concrete version, showing explicitly how to find x was sent by Gaoyuan Chen. On the other hand, a more abstract proof, showing the above to be true by equality of dimensions, was given by Noga Alon and can be found here. (Thank you John T. Robinson for forwarding this link to me.)

An alternative, elementary proof is by induction on n, the number of employees:

Assuming that the induction assumption is correct, we know that any set of n-1 employees can turn their lights on simultaneously. When they do so, they may find themselves inadvertently also turning on the light in the remaining office. If so, we are done. If not, then we know we have the ability to toggle any set of exactly n-1 lights.

If n is even, by toggling each one of these sets in turn, we have, in effect, toggled all lights an odd number of times. Hence, all lights should now be on and we are done.

If n is odd, the set of n vectors of Hamming weight n-1 spans the space of all vectors of even Hamming weight. Therefore, all we still need to prove is that it's possible, at any point, to reach a point where an odd number of lights is simultaneously on. I claim that among the employees there must be at least one with an even number of friends, making her light switch toggle an odd number of lights and thereby completing the last piece of the puzzle.

To see this, let us sum over the number of friends each employee has. If all employees have an odd number of friends and there are an odd number of employees, the sum total must be odd. However, we counted each pair of friends twice (once as <x,y> and once as <y,x>). Therefore, a contradiction is reached, at least one employee must have an even number of friends, and the claim is proved.

Back to riddle

Back to main page