100 Lockers, 100 Students

Date: 8/16/96 at 14:39:22
From: Anonymous
Subject: 100 Lockers, 100 Students Open/Close...

There are 100 closed lockers in a hall, and 100 students. Student 1 
walks down the hall and opens all 100 lockers. Student 2 closes all 
even-numbered lockers. Student 3 looks at every third locker (a 
multiple of 3), and if it is open closes it, or vice-versa (this 
student changes the condition of the locker). Student 4 repeats the 
action of student 3, but only changes the condition of lockers that 
are a multiple of 4. This goes on with every student doing the same 
routine for his or her number.

After 100 students go through, how many lockers are open? 
And are the open lockers even or odd?

Date: 8/30/96 at 17:0:58
From: Doctor James
Subject: Re: 100 Lockers, 100 Students Open/Close...

Basically you have a system of 100 states, each of which is binary 
(either open or closed). Each binary 'cell' (b1, b2, b3,...,b100) can 
either be 0 (closed) or 1 (open). All start out 0, and each operation 
changes its value.

Now, since each cell is acted on whenever the student number (1 to 
100) is a factor of it, the cell changes state a number of times 
equal to the number of its factors, right? And if it changes state an 
even number of times, it ends up closed, and if it changes state an 
odd number of times, it ends up open. So this question boils down to:
How many numbers from 1 to 100 have an even number of factors, and how 
many have an odd number of factors?

The factors of a number are those numbers that the original number is 
evenly divisible by. In all cases, the result of such a division is 
also a factor (I will call this a 'cofactor'). This means that unless 
one of the factors is the square root of the number, the number will 
have an even number of factors. If one of the factors is the square 
root of the number, then the cofactor is itself. For all other 
factors, there will be a cofactor, and thus an even number of them. 
Since an even number plus 1 is an odd number, any perfect square, and 
only a perfect square, will have an odd number of factors.

So, all that mess means the following:

Every locker whose number is a perfect square will be open. 
This means that lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 will 
be open, for a total of 10. There is no correlation between evenness 
or oddness and being open.

If I made it too confusing, please write back and let me try again.

-Doctor James,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/