There are 100 closed lockers in a row, numbered 1 to 100, and 100 students.

arithmetic/lockers New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

There are 100 closed lockers in a row, numbered 1 to 100, and 100
students.  The first student opens every locker.  The second closes
every second locker.  The third opens or closes every third locker, and
so on: student N changes the state of every Nth locker.  After the
100th student goes by, which lockers remain open, and why?

Show solution

It's quite simple.

Every locker gets flipped a number of times equal to the number of
its factors. For example, locker #12 gets flipped 6 times, as students
#1, 2, 3, 4, 6, and 12 go by.

The factors for every number come in pairs. This makes sense. To say
that A is a factor of N is to say that there exists a number B such
that A * B = N. Therefore, for every factor A of a number, there is
a factor B. This means that, with one exception, every locker will
be flipped an *even* number of times, leaving it in its initial state.

The one exception to factors coming in pairs occurs when a number has
factors A and B *equal* to each other. If there exists a number A such
that A * A = N, N will have an odd number of factors. This obviously
only happens when N is a perfect square.

At the end, lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 will be
open. The others are closed.

-- Jonathan Haas <positron@quip.eecs.umich.edu>