Thread: Challenging Problem

An ingenious engineer constructed the following switchboard: It is a rectangular array of 3×3 switches each of which can be ON or OFF, but the wiring is such that if a button is pressed all neighbouring buttons toggle their state as well. Thus, for instance if the the centre button is pressed, also the buttons at its west, north, south and east positions are pressed; if the top right button is pressed, this affects also the top centre, and right centre buttons (in matrix notation, the positions (1, 2) and (2, 3)).

a) Is it possible, beginning with the state of all switches ON, by pushing some buttons to arrive at the state of all switches OFF?

b) Is it possible, beginning with any state, to arrive at the state of all switches OFF?

We start with a 3x3 matrix with all entries 1.



Click the (1,1) entry


Click the (1,3) entry


Click the (3,3) entry


Click the (3,1) entry


Click the (2,2) entry

Originally Posted by amm345

An ingenious engineer constructed the following switchboard: It is a rectangular array of 3×3 switches each of which can be ON or OFF, but the wiring is such that if a button is pressed all neighbouring buttons toggle their state as well. Thus, for instance if the the centre button is pressed, also the buttons at its west, north, south and east positions are pressed; if the top right button is pressed, this affects also the top centre, and right centre buttons (in matrix notation, the positions (1, 2) and (2, 3)).

a) Is it possible, beginning with the state of all switches ON, by pushing some buttons to arrive at the state of all switches OFF?

b) Is it possible, beginning with any state, to arrive at the state of all switches OFF?

a) Yes. Here's one way (there are probably other ways too): Push the center switch, then all 4 corner switches in order (clock-wise or counter clock-wise).

b) Not sure about this, but I think it can be done. Don't know how to prove it though, sorry.