Competition problem — Combinatorics

Library / /19 of 23

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:

A $2 \times n$ grid has a light bulb in each square. Each bulb has a switch that flips the state of its corresponding bulb as well as all (horizontally or vertically) adjacent bulbs. Determine whether it is always possible, regardless of the initial state of the bulbs, to turn all the bulbs off if

a) $n=2011$

b) $n=2012$ .

Solution

Solution:

The answer to both questions is no. Call a lamp "hot" if it is in one of the squares marked $\times$ in the following two patterns:

For $2 \times 2011$ :

$\times$		$\times$		$\times$	$\cdots$	$\times$		$\times$
$\times$		$\times$		$\times$	$\cdots$	$\times$		$\times$

For

2 \times 2012

	$\times$	$\times$	$\times$		$\times$	$\times$	$\times$	$\cdots$		$\times$	$\times$	$\times$
		$\times$				$\times$		$\cdots$			$\times$

It is not hard to see that any flip of a switch affects precisely zero, two, or four hot bulbs, which keeps the parity of the number of lit hot bulbs the same. Thus if we begin with only one lit hot bulb, the number of lit hot bulbs will always be odd and we can never turn all the bulbs off.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.