**Source:**Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) - He found it at http://puzzletweeter.com/

**Problem:**

**Consider an n x n chessboard, where each square is arbitrarily chosen to be either black or white. Your goal is to make all squares in the chessboard white. At each step, you are allowed to "switch" a square, but each switch will toggle not only the particular square being switched, but also the 4 squares that are adjacent to it: Two vertically up and down and two horizontally up and down the square being switched. Note : At corners only 4/3 squares are toggled, while at the center all 5 squares are toggled.**

Show how you can make the entire chessboard white.

Update (May 20 2013):

**Solution:**Posted by JDGM in comments! Very academic solution to a very interesting problem! :) Thanks
This is the "All Ones Problem"

ReplyDeleteThe squares to switch are the solution to a system of n² equations Ax = B in Z₂.

A is the n² by n² matrix whose kᵗʰ row represents which lights are toggled when the kᵗʰ square is "switched", and B is the state of the starting board.

The system is always solvable because A has maximal rank (n² by n² symmetric matrix with non-zero determinant). Solve it and the 1s and 0s in x tell which squares to switch or not.

"Lights Out Puzzle" on Mathworld gives a very clear worked example of this method.

Thanks for the solution. Interesting. I remember reading about it some time back.

ReplyDelete