The Locker Problem FINAL DRAFT! =D

Jovan Millet

October 1, 2009

The Locker Problem

THE LOCKER PROBLEM: The Solution

 

            Here’s the scenario: High Tech High has 1000 new lockers, and they have 1000 students to test them out. The 1^st student opens every locker. The 2^nd student changes the state of every other locker, starting with locker 2. The 3^rd student changes the state of every 3^rd locker, starting with number 3. The fourth student changes the state of every 4^th locker, starting with number 4, all the way until the 1000^th student has changed the state of the 1000^th locker. These are 10 lockers, with locker numbers 1, 4 and 10 open.

 

[ ] [X] [X] [ ] [X] [X] [X] [X] [ ] [X]

 

            I solved it this way. I started with 100 lockers first, to see how it would turn out. I looked at the open ones at the end, and saw that there were 10 open lockers: Numbers 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. I also noticed that these were all perfect squares. After testing my theory of all of the open lockers being perfect squares, I found I was correct, with 31 open lockers out of 1000.

 

Why are the open lockers perfect squares? Simple. In order for a locker to be open, it has to have been touched an odd number of times. The first locker was touched once (Student 1). The second one was touched twice (Student 1 and Student 2). The third one was touched twice (Student 1 and Student 3). The fourth locker was touched 3 times (Student 1, Student 2, and Student 4). Get it?

 

Finally, perfect squares have an odd number of factors, but the others don’t. as you may have noticed in my explanation above. Let’s compare the factors of 16, a perfect square, to the factors of 8, a regular number:

 

16 = 1, 2, 4, 4, 8, 16

8 = 1, 2, 4, 8

 

You could write out the factors of 16 like that, and say I’m wrong. However, one of those 4s is going to be canceled out, because there’re two of them. So, 16 would have five factors, and 8 would have 4. But why do perfect squares have an odd number of factors? Let’s group them into pairs.

 

16 = [1 x 16], [2 x 8], and [4 x ?]

8 = [1 x 8], and [2 x 4]

 

See? 16 has two pairs and a pair-less number, 4, while 8 has two pairs with no remaining numbers at the end of it.

 

Ta-Da! That’s the solution to The Locker Problem! I know it’s very cliché, but this was live, Saturday Night!