Nerds, Jocks, and Lockers

Question

Here's an oldie but goodie from The Daily WTF; I paraphrase to avoid copyright issues:

A middle school math teacher, who also happened to be the P.E. coach, made the following deal with the non-athletic "nerds" in each new math class he taught on their first day:

Outside the classroom was the main hallway, along one wall of which was an uninterrupted row of lockers numbered 1 through 100. As it was morning of the first day of school, the lockers hadn't been assigned yet and so didn't have any padlocks on them.

The "jocks" in the class would go out to the row of lockers, which were all closed, and begin opening all of them. Then they'd close every even-numbered locker, and then open or close every third locker, then every fourth locker, and so on up to 100, "toggling" each locker in the sequence, opening if it was closed, closing if it was open.

Once the jocks had toggled the last locker for the last time, a certain sequence of locker doors would be open. It was the nerds' job to figure out in a more elegant way which locker doors would still be open, before the jocks finished going through their "brute force" routine.

If the nerds cracked it, they were excused from PE class for the rest of the year. If they couldn't, they'd face the jocks in the traditional first-day dodgeball game. In the P.E. teacher's 30 year career, not a single nerd ever avoided his fate.

What sequence of doors remains open when toggled according to this sequence, and why? And no cheating, running up and down the halls of your own school toggling lockers.

Answer 1

Every locker is closed except for square numbers.

Say on turn 1, they make sure every locker is open.

On turn 2, they close the even lockers.

On turn 3, they toggle the lockers divisible by 3.

If locker N has a prime number, it will only be closed on turn N and opened on turn 1.

If locker N is even and greater than 2, it have been toggled on turn N/2.

If locker N is divisble by x and greater than s, it have been toggled on turn N/x.

If locker N is square, it will $\sqrt N=N/\sqrt N$ so this will cause it to be flipped a time with no corresponding pair.

This means every locker N will be toggled equal to the number of its unique factors.

Answer 2

At this point, I can only determine that lockers with an even number of factors of the same number (e.g. 16 = 2 x 2 x 2 x 2 ; 81 = 3 x 3 x 3 x 3) will have the locker doors open (includes door 1, since that has 0 non-one factors)

For a more intuitive answer:
Factor out each number (e.g. 12 = 2 x 2 x 3). Take the number of each factor, add 1, and multiply each factor together. This will give the total number of times a door is opened. (e.g. 2x 2's, 1x 3's -> 3 x 2 = 6 toggles, door is closed). This works because you have to find each combination of factors, so you can use the 2's (0-1-2) times, and the 3's (0-1) times.

To have a door opened, you need all of your factors to be odd. The only way to do this is to have all your factors be even, which means you have a square number.

Answer 3

Every square number from 1 to 100.

1, 4, 9, 16, 25, 36, 49, 56, 64, 81, 100

Obtained with a Lua script ran on iPod:

local Open = {}    
local Closed = {}    

for i = 1,100 do    
    Closed[tostring(i)] = true    
end    

for i = 1,100 do    
    for locker = 1,100 do    
       if locker % i == 0 then    
          if Open[tostring(locker)] then    
             Open[tostring(locker)] = nil    
             Closed[tostring(locker)] = true    
          elseif Closed[tostring(locker)] then    
             Closed[tostring(locker)] = nil    
             Open[tostring(locker)] = true    
          end    
       end    
    end    
 end    

 for i,v in pairs(Closed) do
    print(i)    
 end    
 print("Open:")    
 for i,v in pairs(Open) do    
    print(i)    
 end

This is because they are toggled an odd number of times.

Answer 4

1, 2, 5, 10, 17, 26, 37, 50, 65, 82

I obtained this list running some simple JavaScript code:

var lockers = [];
for(i=0;i<100;i++){
    lockers.push(false); // all closed at the beginning
} 
for (i = 1; i<100; i++) {
    for (j=0;j<100;j+=i) {
        lockers[j] = !lockers[j]; // toggle
    }
}