[math-fun] Circle of lights puzzle
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
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
Thanks, Allan. The OEIS entry in question counts " Total number of subsets of the n-th roots of 1 that add to zero. " Is every subset S that adds to zero accessible from the empty set via moves of the specified kind? Note that this is potentially different from the question of expressing the indicator function of S as a sum of indicator functions of subsets of the allowed kind. I'm having a sense of deja vu; I think this question came up before on math-fun about five years ago. (In fact, I think I'm the one who brought it up!) Jim Propp On Thu, Dec 14, 2017 at 6:21 PM, Allan Wechsler <acwacw@gmail.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This appears suspiciously similar to results in this paper by Klaus Sutner <https://pdfs.semanticscholar.org/7cea/26fce139375ee51b180a14b02bce0709c1a7.pdf> stated in terms of any finite graph--with a proof of solution (Theorem 3.2). 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
participants (3)
-
Allan Wechsler -
James Propp -
W. Edwin Clark