The Art and Craft of Problem Solving

2.2 STRATEGIES FOR GETTING STARTED 29

possible GCD value for pairs of consecutive terms. Neither of these items is hard to
prove if you know some simple number theory tools. We will continue this problem in
Example 7.1. 8 on page 227.

Example 2.2.3 Lockers in a row are numbered 1,2,3, ... , 10 00. At first, all the lockers
are closed. A person walks by and opens every other locker, starting with locker #2.
Thus lockers 2,4,6, ... ,998, 10 00 are open. Another person walks by, and changes
the "state" (i.e., closes a locker if it is open, opens a locker if it is closed) of every
third locker, starting with locker #3. Then another person changes the state of every
fourth locker, starting with #4, etc. This process continues until no more lockers can
be altered. Which lockers will be closed?

Partial Solution: Most likely, there is nothing special about the number 1000
in this problem. Let us make it easier: Simplify the problem by assuming a much
smaller number of lockers, say 10 , to start. Now get your hands dirty by making a
table, using the notation " 0 " for open and "x" for closed. Initially (step 1) all 10 are
closed. Here is a table of the state of each locker at each pass. We stop at step 10 ,
since further passes will not affect the lockers.

step Locker #

2 3 4 5 6 7 8 9 10

1 x x x x x x x x x x

2 x 0 x 0 x 0 x 0 x 0

3 x 0 0 0 x x x 0 0 0

4 x 0 0 x x x x x 0 0

5 x 0 0 x 0 x x x 0 x

6 x 0 0 x 0 0 x x 0 x

7 x 0 0 x 0 0 0 x^0 x

8 x^0 0 x^0 0 0 0 0 x

9 x 0 0 x 0 0 0 0 x x

10 x 0 0 x 0 0 0 0 x 0

We see that the closed lockers are numbered 1,4,9; a reasonable conjec ture is
that only perfect square-numbered lockers will remain closed in general. We won't
prove the conjecture right now, but we can make substantial progress by looking at the
penultimate step. What determines if a locker is open or closed? After filling out the
table, you know the answer: the parity (evenness or oddness) of the number of times
the locker's state changed. A locker is closed or open according as the number of state
changes was odd or even. Apply the penultimate step idea once more: what causes a
state change? When does a locker get touched? Simplify things for a moment, and just
focus on one locker, say #6. It was altered at steps 1, 2, 3 and 6, a total of four times
(an even number, hence the locker remains open). Look at locker #10. It was altered
at steps 1, 2, 5 and 10. Now it's clear:

Locker #n is altered at step k if and only if k di vides n.