October 14–October 20, 2008
Problem
Suppose there's a row of n lights, which (simultaneously) turn on and off each minute according to the following rules:
- If a light is currently on, then the next minute it will turn off.
- If a light is currently off, and exactly one light adjacent to it is currently on, then the next minute it will turn on. Otherwise it will stay off.
For which n is it possible to find an initial configuration of on/off lights, such that at least one light will be on at any time?
To clarify:
For some n, there are on/off configurations so that there will always be at least one light on. For example, when n = 2, start with [on,off]; then the lights will follow the pattern [on,off] --> [off,on] --> [on,off] ... Conversely, there are some n where no configuration works; no matter how we start the pattern of lights, eventually all the lights turn off permanently.
The problem is to find all possible (or as many as possible) values of n, and corresponding starting configurations for n, so that there will be some light on. The prize will go to the person who finds working on/off configurations for the most n's.
Solution
here.List of solvers
Rajneesh Hegde, Lloyd Sakazaki, and Michael Draper solved the problem completely: any n except n=1 and n=3 has a configuration. Many others found configurations for "fewer" values of n. (Fewer in quotes, since some of these solutions still involved infinitely many n.)
Michael Draper wins the prize!