Nine squares, each one either black or white, are arranged in a 3×3 grid. Figure 2.24 sh...

Nine squares, each one either black or white, are arranged in a 3×3 grid. Figure 2.24 shows one possible

arrange ment. When touched, each square changes its own state and the states of some of its neighbors (black S white and white S black). Figure 2.25 shows

how the state changes work. (Touching the square whose number is circled causes the states of the squares marked * to change.) The object of the game is to turn all nine squares black. [Exer cises 35 and 36 are adapted from puzzles that can be found in the interactive CD-ROM game The Seventh Guest (Trilobyte Software/Virgin Games, 1992).]

(a) If the initial configuration is the one shown in Figure 2.24, show that the game can be won and describe a winning sequence of moves.

(b) Prove that the game can always be won, no matter what the initial configuration.