Best Answer plasmid, 29 April 2014 - 03:31 PM

Possibly solved, but not completely proven.

Spoiler for number of lamps that can have a single lamp toggled with an M 105 tool

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.

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.

Spoiler for turning off lamps with an M 32 tool

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)

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)

^{32}=~ 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)^{16}=~ 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.
Spoiler for putting that all together

Go to the full post
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.)

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.)