1
$\begingroup$

There is a $6\times6$ board ($36$ squares) which has a lightbulb in each square. A move consists in selecting a $3\times 1 $ or $1\times 3$ piece of the board and inverting all the lightbulbs in that piece. Prove if there is exactly one lighted bulb then it is not possible to turn all of them off.

$\endgroup$
1
$\begingroup$

We use a parity (colouring) argument. Colour the squares of the top row, in order, blue (B), white (W), red (R), B, W, R.

Colour the squares of the second row W, R, B, W, R, B. Colour the third row R, B, W, R, B, W. And on the fourth row start again.

Any move changes the state of one square of each colour. Suppose for example that the initially lit bulb is on a blue squares. Then there has to be a total of an odd number of changes in the blue squares, to make them all be unlit. But then there will be an odd number of changes in the red squares, so at least one of them (indeed an odd number) will be lit.

$\endgroup$
  • 1
    $\begingroup$ wow that was fast, how did you get so good at this? $\endgroup$ – Jorge Fernández Hidalgo Jun 18 '14 at 4:41
  • 1
    $\begingroup$ I have been around a fairly long time. $\endgroup$ – André Nicolas Jun 18 '14 at 4:43
2
$\begingroup$

Number the squares on the board as shown: $$\matrix{1&2&3&1&2&3\cr 2&3&1&2&3&1\cr 3&1&2&3&1&2\cr 1&2&3&1&2&3\cr 2&3&1&2&3&1\cr 3&1&2&3&1&2\cr}$$ At any stage, let $S$ be the sum of the numbers in the squares containing lighted bulbs. Any allowable move affects three squares numbered $1,2,3$. There are $8$ possible changes:

  • if all bulbs are off, then we turn them all on and $S$ increases by $6$;
  • if the bulb on square $1$ is on and the others off then we lose the $1$ and gain $2$ and $3$, so $S$ changes by $4$;

and so on: if you go through the details you will find that $S$ always changes by an even number. Therefore, if we are ever to end up with all bulbs off (that is, $S=0$), then we must start with a single bulb on one of the squares marked $2$.

But now do the same thing with the board labelled $$\matrix{2&3&1&2&3&1\cr 3&1&2&3&1&2\cr 1&2&3&1&2&3\cr 2&3&1&2&3&1\cr 3&1&2&3&1&2\cr 1&2&3&1&2&3\cr}$$ If we end up with all bulbs off, the initial bulb must be on a square labelled $2$ in both diagrams. But there is no such square. Therefore it is not possible to turn all bulbs off.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.