Nerds, Jocks, and Lockers

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.

• @warspyking - Nope, wrong. Some locker doors remain open. Which ones? Nov 18, 2014 at 20:45
• Lol that excludes the obvious answer. Anyway my Lua script returned this: Closed: 53 43 73 63 47 37 67 57 27 17 13 33 23 42 52 62 72 46 56 66 90 83 97 96 95 94 93 92 26 91 12 22 32 71 61 51 41 65 55 45 35 59 39 29 99 89 79 69 84 3 2 19 7 6 15 87 86 31 21 11 85 60 70 40 50 54 34 44 48 58 28 38 88 98 68 78 82 80 77 76 18 75 74 14 24 5 20 30 8 10 Open: 36 100 16 49 1 4 25 64 81 9 Nov 18, 2014 at 20:52
• You're on the right track, but like Scimonster I can't condone your methods, as any script that just models what the jocks are doing can't be described as "elegant". Nov 18, 2014 at 20:53
• I would argue it's elegant. It's faster than brute force and requires no pencil-paper working it out. Nov 18, 2014 at 21:06
• Nov 18, 2014 at 21:15

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.

• ding ding ding congrats, you win 15 rep. Nov 18, 2014 at 21:01
• I still get to skip PE right? Nov 18, 2014 at 21:02

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)

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.

• Your answer is correct, so uptick, but for a more complex reason than it has to be. kaine got his answer right and has the more intuitive explanation. Nov 18, 2014 at 21:00
• Added a more intuitive reasoning. Nov 18, 2014 at 21:03

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.

• So you are a jock then who knows how to program to do the brute force way... ok... ok... Nov 18, 2014 at 21:25
• Revenge of the jocks! Apr 25, 2018 at 14:12

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
}
}

• There must be a bug in that code; the sequence is incorrect. In addition, this is little more than the programming version of running up and down the hall, so I can't condone the methodology. Nov 18, 2014 at 20:52
• Looking closer, yes there is a bug; the jocks would toggle the 100th locker as it is the first multiple of 100. You're not doing so. In addition, there seems to be some "off-by-one" error in printing out the number associated with each index of your array. Nov 18, 2014 at 20:56