Competition problem — Combinatorics

Library / /11 of 13

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:

Suppose $2011$ light bulbs are arranged in a row. Each bulb has a button under it. Pressing the button will change the state of the bulb above it (on to off or vice versa) and will also change the two neighboring bulbs, or the single neighboring bulb in the case of one of the two end buttons. Is it always possible, regardless of the initial state of the bulbs, to turn them all off by pressing some buttons?

Solution

Solution:

The answer is yes.
Let us number the bulbs $1$ to $2011$ from left to right. Given any initial state of the bulbs, let us begin by following this algorithm: As long as at least one bulb other than bulb $1$ is on, let $n$ be the number of the rightmost lit bulb and push the button for bulb $n-1$ . This will turn bulb $n$ off and move the location of the rightmost lit bulb to the left. We may continue until either (1) all bulbs are off or (2) only bulb $1$ is on. In the former case, we are done; in the latter case we then push the buttons marked $\times$ :

1	2	3	4	5	6	7	8	$\cdots$	2007	2008	2009	2010	2011
$\times$		$\times$	$\times$		$\times$	$\times$			$\times$	$\times$		$\times$	$\times$

It is evident that every bulb will then change state twice, except the first, which will change state once. Thus all the bulbs will be turned 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.