How can I solve the following problem? I have been given n lamps to form a circular ring. I can use switch to any lamp that turns the lamp and its m nearest lamps from both sides to its negate state, i.e. if lamp is on then it turns off and vice verse. I can choose where the switch starts if effect. How can I find the minimum number of pressing switches that I can shut down all lamps?
For example, if the lamps are 110000 and m=2 then by using the switch for the fourth lamp gives me 101111 and then pressing the fifth lamp gives me the position 000000.
The problem seems to be hard as one of the situations was to consider the case where m=108 and there are 2107 lamps. Is this something like Gauss–Jordan in Z/2Z?