MelonGirl wrote:

not directly related to last few posts, but I pm-ed you about this sometime back, so I guess I'll post it here as well for anyone who's worked on the problem.

Quote:

On each square of a chessboard is a light which has two states-
on or off. A move consists of choosing a square and changing
the state of the bulbs in that square and in its neighboring
squares (squares that share a side with it). Show that starting
from any configuration we can make finitely many moves to
reach a point where all the bulbs are switched off

This is under the algorithms chapter (2). People have found ways to do this with linear algebra and brute force (similar to the row reduction method here.)

Does anyone know of a purely combinatorial algorithm approach to this problem?

Let the cells of the chessboard be vertices of a graph $G$ . Connect any two neighboring vertices (squares). So, you can change the binary state (0,1) of any vertex and all of its neighbors. It does not matter what a graph $G$ is. For any simple graph the same claim holds. It was posted already here, in this forum. Here is a solution using linear algebra. There is a T. Gallai's result saying that the vertices of any graph can be partitioned into two sets $V_1,V_2$ such that the subgraphs induced on $V_1$ and $V_2$ have all vertices of even degrees. It's possible the above problem to be proved as a corollary of Gallai's theorem. In this blog post, the converse approach is shown.