Posts Tagged ‘parity’

Answer: Lights in a Room

November 23, 2010

The problem asked

There’s a room with 64 labeled light bulbs, each of the which can be either on or off, and each of which has its own switch. You walk into the room and find the light bulbs in some arbitrary pattern of on and off. You get to flip one light bulb of your choosing (and you must flip one).

Next, you leave the room and I enter. By looking at the pattern now on the lights, I might be able to get some information – you might be able to send me a message.

If we convene before hand to create a strategy and write a list of pre-recorded messages we want to be able to send by picking one off the list, how long should the list be?

The answer is that the list should be 64 messages long.

By the pigeonhole principle, 64 messages is an upper bound, because when you enter the room you have have to choose between 64 light bulbs.

We’ll prove 64 is attainable constructively.

Since we’re flipping a switch, it’s natural to think about the parity of the bulbs. We’re not interested in the parity of the entire sequence, though; that is forced to change because you flip exactly one switch.

If we wanted to settle for a two-item list, we could simply consider the parities first and second halves of the bulbs independently. We can easily control the parity of the first half by flipping a bulb in the first half if we want to change its parity, or flipping a bulb in the second half if we don’t. This lets us encode a one-bit message, but it’s a wasteful strategy. All the bulbs in the first half are treated the same. It would be better to cut the sequence in half more ways, and do them simultaneously. Let’s call these different halves “slices”.

Another natural slice is to take evens and odds. But in between first half/second half and even/odd slices there is a sequence of slices.

  • (1-32), (33-64)
  • (1-16, 33-48), (17-32, 49-64)
  • (1-8, 17-24, 33-40, 49-56), (9-16, 25-32, 41-48, 57-64)
  • etc.

Or, to put it another way, start the light bulbs’ numbering at zero and make the slices

  1. (0-31 mod 64),(32-63 mod 64)
  2. (0-15 mod 32),(16-31 mod 32)
  3. (0-7 mod 16),(8-15 mod 16)
  4. (0-3 mod 8),(4-7 mod 8)
  5. (0,1 mod 4),(2,3 mod 4)
  6. (0 mod 2),(1 mod 2)

The important thing about this breakdown is that it allows you to zero in on a single light bulb by saying that that it’s in the left half slices 1, 4, 5, and 6 and the right half of slices 2 and 3, for example. That uniquely picks out bulb 24. It also goes the other way. Any bulb has a unique combination of left halves/right halves.

This is perfect! Now we can send six one-bit messages at the same time. To send our first one-bit message, as before we control the parity of the first half of the bulbs. To send the second bit, we control the parity of the bulbs in the left half of slice two. To send the third bit, we control the parity of the bulbs in the left half of slice three, etc. There will always be exactly one bulb that correctly changes / fails to change all six parities in the way we want.

So we can send six bits, or 2^6=64 messages.