# Challenging Problem

Printable View

• Nov 22nd 2009, 10:59 AM
amm345
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?
• Nov 22nd 2009, 11:15 AM
qmech
Does this work?
We start with a 3x3 matrix with all entries 1.

$\displaystyle A=\left(\begin{array}{ccc}1&1&1\\1&1&1\\1&1&1\\\en d{array}\right)$

Click the (1,1) entry
$\displaystyle A=\left(\begin{array}{ccc}0&0&1\\0&1&1\\1&1&1\\\en d{array}\right)$

Click the (1,3) entry
$\displaystyle A=\left(\begin{array}{ccc}0&1&0\\0&1&0\\1&1&1\\\en d{array}\right)$

Click the (3,3) entry
$\displaystyle A=\left(\begin{array}{ccc}0&1&0\\0&1&1\\1&0&0\\\en d{array}\right)$

Click the (3,1) entry
$\displaystyle A=\left(\begin{array}{ccc}0&1&0\\1&1&1\\0&1&0\\\en d{array}\right)$

Click the (2,2) entry
$\displaystyle A=\left(\begin{array}{ccc}0&0&0\\0&0&0\\0&0&0\\\en d{array}\right)$
• Nov 22nd 2009, 11:18 AM
Koaske
Quote:

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.