lamp algorithm

[BMAD]

N lamps are set in a circle, and for each integer M you have a tool that can toggle the state (on/off) of any set of M consecutive lamps.

Find a possible N which satisfies the following statements:

The sum of its digits is less than 10.

By applying the tool for M=105 several times, we can toggle a single lamp.

If we remove one lamp and start from a random initial setting for the remaining N-1 lamps, the probability that there exists a way to apply the tool for M=32 several times and switch all the lamps off is positive and less than 0.0011%.

[Rob_G]

Lets say N=6 and M=5. If we use the tool to toggle 1,2,3,4,5 will it always do those 5 lamps or can we apply it to 1,2,3,4,5 then 3,4,5,6,1 etc?

[BMAD]

no.

[plasmid]

This is a tough problem. At least for me. This is what I've got right now.

I'll start by trying to consider cases where an M=105 tool can toggle a single lamp.

First notice that for any N>105, if you apply M=105 to every lamp in the circle when they all start in the off position, then every lamp will end up being switched 105 times and will be turned on. If you have N = 105*n + 1 then you can turn 105*n lamps back off with the tool and leave the extra lamp turned on. Likewise if you have N = 105*n - 1 lamps that have been turned on and you use M=105 on lamps 1, 106, 211, 105x+1 etc for all x, then all the lamps will be turned back off except for lamp #1 which was toggled an extra time on the last use of the tool to be turned back on. So all cases where N = 105*n +/- 1 can have one lamp toggled by a M=105 tool. I cannot rule out the possibility that other values of N would work, and I wouldn't be surprised if there were other such values.

Now I'll consider (some) cases where you can use an M=32 tool to turn all the lamps off.

First notice that with an M=32 tool, you can use it on lamp 1 and lamp 2 to toggle lamps #1 and #33. If you use it again on lamps 33 and 34, you will toggle 33 back to its original state and 65 to a different state. By repeatedly using it like this, you can toggle two lamps: lamp 1 and lamp n*32+1. If N-1 (the number of lamps when you're using the M=32 tool) is odd, then 32 is relatively prime with respect to N-1, and therefore you can always find some n that will toggle lamps 1 and any desired other lamp. That means that if N-1 is odd, then any initial random setting with an even number of lamps turned on can get all the lamps turned off by an M=32 tool, therefore the probability that a random configuration can get all the lamps off would have to be at least 50%. So only even solutions for N-1 (odd solutions for N) are possible.

But I cannot come up with a good way of calculating the probability that an M=32 tool can get all the lamps off from an initially random configuration of an even number of lamps. In principle, one could brute-force the answer by calculating the total number of different states that could be reached with an M=32 tool starting with all lamps off (you only have to consider 2^lamps cases since a lamp being flipped any even or any odd number of times would produce the same result) and divide that by 2^lamps. That should give you the probability that you can get all the lamps off from a random initial state.

[plasmid]

Possibly solved, but not completely proven.

In the previous post when I was talking about the M=32 tool, I said that you can use it on lamps 1 and 2, 32+1 and 32+2, 64+1 and 64+2 ... 32*n+1 and 32*n+2 in order to toggle pairs of lamps, and that you could toggle any desired pair if the number of lamps in the circle is relatively prime to the number of lamps switched by the M-tool.

Simply apply that logic to the M=105 tool. If the number of lamps is relatively prime with 105 (i.e. it does not have 3, 5, or 7 as factors) then you can use that approach to toggle any desired pair of lamps. Use the M=105 tool once, then toggle pairs of lamps that it turned on until you've turned off 104 of them - all except for the single lamp you wanted to toggle. So any number of lamps relatively prime with 105 can have a single lamp toggled. This includes the 105*n +/- 1 cases that I mentioned before because 105*n +/- 1 will of course not be divisible by any factors of 105 and will be relatively prime.

Consider what would happen if you tried to use this approach with an M-tool that was not relatively prime with respect to the number of lamps. You could turn on lamp 1 and propagate the M+1 lamp around the circle (perhaps multiple times) until it gets back to lamp 1 without reaching every other lamp. I suspect but have not fully convinced myself that if you take the product of all common factors of (M) and (number of lamps) and call that F, then you could reach every F*n + (starting lamp number) lamp. For example with the M=105 tool, if N were a multiple of 3 and had no other factors in common with M, you could toggle lamps 2, 5, 8, 11, etc in pairs.

The implication of this is that you can now consider F sets of lamps (one set would be F*n for all n, another is F*n+1, etc up to F*n+(F-1)) where any pair of lamps within a set can be toggled. That means that you can reduce any arbitrary arrangement to be represented by the number of lamps that are turned on within each of those sets. You can turn all the lamps in a set off if there are an even number of lamps on within that set.

For the M=32 tool, the maximum product of common factors for 32 and any other number is, of course, 32. That means there are a maximum of 32 such sets. For a random initial arrangement, there will be a 50% chance that an even number of lamps within each of those 32 sets is on and therefore all lamps within that set can be turned off. So the odds that you will get an initial configuration where all lamps can be turned off is (1/2)³² =~ 2e-10, or 2e-8 %. If there were only 16 sets of lamps (the next smallest number that could be a common factor with 32) then odds that you will get an initial configuration where all lamps can be turned off is (1/2)¹⁶ =~ 0.000015, or 0.0015%, which does not meet the OP's requirement of being less than 0.0011%. So the number of lamps in the M=32 scenario must be a multiple of 32.

N must be relatively prime with respect to 105, (N-1) must be a multiple of 32, and the sum of the digits of N must be less than 10. Looking at cases where N = 32*m+1 and trying to find one that is relatively prime with respect to 105 (not divisible by 3, 5, or 7) with digits summing to less than 10, the first one that I found is 1121.

Note that I have not completely proven that there aren't any other ways of toggling a random configuration of lamps all off, I have only showed that it can't be done using the algorithm of propagating pairs of lamps to toggle. So it's entirely possible that someone super clever might come up with a way of turning lamps off with an M=32 tool with probability greater than 0.0011%. (Actually, if you're able to toggle one lamp in each set on instead of off using my approach, then you could apply the M-tool to that set of lamps that is on and end up with them all being off, so the odds of turning off a set of lamps are at least twice as large as what I calculated earlier. But that would not change my answer.)