Jeremy’s Sametime Status Proudly Presents: Brain Teaser Week! (Fairly Difficult and Using Excel is Cheating) A school for mischievous students has a hallway with 100 lockers. All the lockers are closed. Student one walks down the hallway and opens every locker. Student two walks down the hallway and closes every second locker, starting at locker two. Student three walks down the hallway and changes the state of every third locker, starting at locker three (If it’s open, he closes it....if it’s closed, he opens it). And so on, student n changes the state of every n-th locker. After 100 students have passed through the hallway, which lockers are left open?
One of the most popular Theme Weeks was this spring’s “Brain Teaser Week.” In fact, the finale of that week still resides on my system as my “I’ve gone to lunch” message. It allows people to ponder the most difficult brain teaser, since nobody’s ever figured it out without me telling them the answer.
Regardless, this particular brain teaser was the Thursday edition, so it was the second hardest one. It tests people’s knowledge of mathematical principals, pattern generation, fractal drawing, mazes, hoodlums, and duct tape. Truth be told, a couple loyal readers managed to untangle the logic behind this puzzle, but I don’t think anybody really figured it out. Most tried a brute force method, which will work for the first handful of lockers, but obviously gets more difficult as the numbers get higher. You just have to hope that you recognize what you see in the Brute Force method before you either pass out or make a mistake. Or, you can change the number of students and lockers to 2000 and actually try to figure it out logically.
Since this Theme Week never originally translated to Blag form, I’ll post the answer after Thanksgiving. Good luck!
2 comments:
I know the answer! I know the answer!
I am so smart. S-M-R-T...
Since I won't be here on Monday to tell you myself, I'll post my answer as a comment. You can delete this if you want.
All of the lockers start out closed. In order for a locker to be closed when all is said and done, an even number of actions have to be performed on it. For a locker to be open, an odd number of actions have to be performed on it.
An action is performed on a locker each time we consider a student n such that n is a divisor of that locker number. So, locker 1 is opened for n=1. Locker 2 is opened for n=1 and n=2. Locker 3 is opened for n=1 and n=3.
In other words, the number of actions on a given locker is the number of divisors that number has. 1 has one proper divisor (1). 2 has two proper divisors (1,2). 3 has two proper divisors (1,3). Since divisors always come in pairs, the only integers with an odd number of divisors are the perfect squares (where one pair of divisors are equal), hence the only lockers between 1 and 100 that will be open are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.
If I have misread the question and am horribly wrong, then please delete this comment and yell at me to stop patting myself on the back.
Post a Comment