Competition problem — Combinatorics

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

A regular ( $5 \times 5$ )-array of lights is defective, so that toggling the switch for one light causes each adjacent light in the same row and in the same column as well as the light itself to change state, from on to off, or from off to on. Initially all the lights are switched off. After a certain number of toggles, exactly one light is switched on. Find all the possible positions of this light.

Solution

We assign the following first labels to the 25 positions of the lights:

1	1	1	1
0	0	0	0
1	1	1	1
0	0	0	0
1	1	1	1

For each on-off combination of lights in the array, define its first value to be the sum of the first labels of those positions at which the lights are switched on. It is easy to check that toggling any switch always leads to an on-off combination of lights whose first value has the same parity (the remainder when divided by 2) as that of the previous on-off combination.

The $90^{\circ}$ rotation of the first labels gives us another labels (let us call it the second labels) which also makes the parity of the second value (the sum of the second labels of those positions at which the lights are switched on) invariant under toggling.

1	1	1
1	1	1
0	0	0
1	1	1
1	1	1

Since the parity of the first and the second values of the initial status is 0, after certain number of toggles the parity must remain unchanged with respect to the first labels and the second labels as well. Therefore, if exactly one light is on after some number of toggles, the label of that position must be 0 with respect to both labels. Hence according to the above pictures, the possible positions are the ones marked with

*_{i}

's in the following picture:


$*_{2}$		$*_{1}$
	$*_{0}$
$*_{3}$		$*_{4}$

Now we demonstrate that all five positions are possible:
Toggling the positions checked by

t

(the order of toggling is irrelevant) in the first picture makes the center

(*_{0})

the only position with light on and the second picture makes the position

*_{1}

the only position with light on. The other

*_{i}

's can be obtained by rotating the second picture appropriately.

			$t$	$t$
		$t$
	$t$	$t$		$t$
$t$				$t$
$t$		$t$	$t$

	t		t
t	t		t	t
	t
		t	t	t
			t

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.