Re: [math-fun] math-fun Digest, Vol 178, Issue 23
"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?"
OEIS http://oeis.org/A103314 looks very apropos.
A070894 looks even better. The set of bulbs changed by a move has a center-of-light at zero. (Arrange the bulbs evenly around the circle. And then all go on or all go off.) The original center is non-zero, and a move changes it to a weighted combination of zero and the old value: but never to zero. So you can't even turn them all off. Please refute this, if you're the last one to bed. -- Don Reble djr@nk.ca
That argument sounds correct to me, at least for the non-degenerate cases where n >= 2. For n=1, the lights start out all-on, which solves it provided you're allowed to make zero moves. Arguably there are no legal moves when n=1 since there is no valid d. Question: Given an initial configuration of all-off (or all-on), are all of the zero COL patterns attainable? I think http://oeis.org/A103314 gives the count if you include the all-off case, which http://oeis.org/A070894 does not. Tom Don Reble writes:
"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?"
OEIS http://oeis.org/A103314 looks very apropos.
A070894 looks even better.
The set of bulbs changed by a move has a center-of-light at zero. (Arrange the bulbs evenly around the circle. And then all go on or all go off.) The original center is non-zero, and a move changes it to a weighted combination of zero and the old value: but never to zero.
So you can't even turn them all off. Please refute this, if you're the last one to bed.
-- Don Reble djr@nk.ca
Don's proof is right (and you'll shortly see the exact same argument in my December blog-essay). So, the one-light-on configurations are NOT accessible from the zero-lights-on configuration. Can anyone devise two configurations that are not mutually accessible even though the turned-on lights have the same center of mass in both configurations? What if we insist that the center of mass in both configurations is the center of the circle? Jim On Friday, December 15, 2017, Don Reble <djr@nk.ca> wrote:
"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?"
OEIS http://oeis.org/A103314 looks very apropos.
A070894 looks even better.
The set of bulbs changed by a move has a center-of-light at zero. (Arrange the bulbs evenly around the circle. And then all go on or all go off.) The original center is non-zero, and a move changes it to a weighted combination of zero and the old value: but never to zero.
So you can't even turn them all off. Please refute this, if you're the last one to bed.
-- Don Reble djr@nk.ca
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It turns out that "center-of-light" isn't as useful as "sum-of-light" or "average-of-light". If you use "center-of-light", then you don't need to go past 4 lights to find an example of two configurations in the same accessibility class but with different centers of light: 1000 vs. 1101. A single move will transform one into the other, yet their centers of light are clearly different. However, their sums-of-light, and their averages-of-light, are the same (where "average" is simply the sum divided by the total number of lights, as opposed to the total number of lit lights). I tested up to 12 lights, and didn't find any examples of two configurations with the same sum-of-light (or average-of-light) that were not mutually accessible. And of course, I didn't find any examples of two configurations with different sum-of-light (or average-of-light) that were mutually accessible (which has already been established, since moves preserve these properties, even when the sum is not (0, 0)). Tom James Propp writes:
Don's proof is right (and you'll shortly see the exact same argument in my December blog-essay).
So, the one-light-on configurations are NOT accessible from the zero-lights-on configuration.
Can anyone devise two configurations that are not mutually accessible even though the turned-on lights have the same center of mass in both configurations?
What if we insist that the center of mass in both configurations is the center of the circle?
Jim
On Friday, December 15, 2017, Don Reble <djr@nk.ca> wrote:
"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?"
OEIS http://oeis.org/A103314 looks very apropos.
A070894 looks even better.
The set of bulbs changed by a move has a center-of-light at zero. (Arrange the bulbs evenly around the circle. And then all go on or all go off.) The original center is non-zero, and a move changes it to a weighted combination of zero and the old value: but never to zero.
So you can't even turn them all off. Please refute this, if you're the last one to bed.
-- Don Reble djr@nk.ca
participants (3)
-
Don Reble -
James Propp -
Tom Karzes