Several years ago, I got a 5x5 lights out game for Christmas. It is a puzzle game in which the goal is to turn off all the lights which are on at the start (from 1 to all 25). Lights are turned on and off by pressing them. However, pressing any one light will change both that light and all the orthogonally neighboring lights.

But now, two of the lights are broken. The two lights still light up correctly, but pressing either of them will not have any effect. However, if a puzzle was solvable with all 25 lights working, it was still solvable with the two broken lights.

How many different pairs of lights can be broken like that?

I can't prove it yet, but I believe that any pair of broken lights where one or both are in the set consisting of the center light and its four diagonally adjacent neighbors will become unsolvable for at least one otherwise solvable configuration. That makes 5*4/2 pairs when both are members of that set and 5*20 pairs when only one is for a total of 110 pairs that fail to meet the criteria. The remaining 25*24/2 = 300 - 110 = 190 pairs can be broken without affecting the ability to solve ANY solvable pattern.

Any solution always consists of pressing some subset of lights once each--pressing a light twice is the same as not pressing it at all and so can be ignored. The trick seems to involve finding non-empty collections that, when pressed, do absolutely nothing--sort of identity elements for the system. I know of three such, but I can't prove that set is complete. 

Given a solution which uses broken lights, one can, by adding one or more of these "identity" patterns, transform the solution into a new solution that uses different lights and thus avoid the broken ones. The catch is that all three "identity" patterns do not touch the five lights mentioned above, and so if these lights are required in the solution, they are also required in any transformed solution and if they're broken, you're out of luck.

There's still a ways to go, but I think this is a fruitful direction to explore.

Posted by Paul on 2008-04-15 04:44:22