OEIS http://oeis.org/A103314 looks very apropos. On Thu, Dec 14, 2017 at 5:45 PM, James Propp <jamespropp@gmail.com> wrote:
Does anyone know the origin of the following Olympiad study problem?
"Given a circle of n lights, exactly one of which is initially on, it is permitted to change the state of a bulb provided that one also changes the state of every dth bulb after it (where d is a divisor of n strictly less than n), provided that all n/d bulbs were originally in the same state as one another. Is it possible to turn all the bulbs on by making a sequence of moves of this kind?"
I've found a statement of the problem at http://www.math.northwestern.edu/~mlerma/problem_solving/ putnam/training-complex and I learned from a Google search that the problem appears in the book "Mathematical Olympiad Challenges", but the excerpt I was able to view online doesn't explain who came up with the problem. (Maybe this is explained elsewhere in "Mathematical Olympiad Challenges", but I don't currently have access to a copy.)
Was this ever used as an Olympiad problem, or does it come from some earlier problem book? Does it have a credited inventor?
See http://somethingorotherwhatever.com/circular-lights-out/ for Christian's nice implementation.
I also wonder whether anyone has ever computed, for various values of n, the number of different patterns of lights that are reachable from the all-lights-off position (or equivalently from the all-lights-on position). I tried entering "lights" and "circle of lights" into the OEIS but the former gave too many hits (141) while the latter gave none at all.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun