There are 1,000 students and lockers in a school. The first student opens every locker with an even locker number.How many lockers will be left open?

Question

We have 1,000 students and 1,000 lockers in a school. Each student must enter the school and complete their respective task. The first student enters and opens every locker with an even number all the way through the 1,000 lockers. The second student enters and reverses every second locker through all 1,000 lockers. Meaning, if a locker is closed it must be opened, if a locker is open it must be closed. The third student enters and reverses every third locker through all 1,000 lockers. Meaning, if the locker is open they close it, if a locker is closed they open it. The fourth student reverses every fourth locker. The fifth student reverses every fifth locker. This continues until all 1,000 students have completed their respective task. After all students have had their turn, how many lockers remain open?

Answer 1

As written then.

 

The options here are binary; the locker is either opened or closed. You can model the behavior of the locker by (-1)ⁿ, where n is the number of times the locker is opened/closed and a result of -1 means the locker is open and 1 means the locker is closed. So any random locker will remain open after the 1000th student if n is an odd number.

 

How do we figure out how many times a locker has been opened/closed? Let's look at an example: locker 12 is opened/closed by the 1st, 2nd, 3rd, 4th, 6th, and 12th students. 1, 2, 3, 4, 6, and 12 are the factors of 12, so locker 12 is opened/closed 6 times. So we just need to find numbers between 1 and 1000 that have an odd number of factors.

 

Here's where the wrinkle appears, though. The 1st and 2nd students are opening/closing the same lockers and are canceling each other out. So we need to look for numbers with an odd number of factors after excluding the factors 1 and 2. There are two cases here: even numbers and odd numbers.

 

All even numbers have both 1 and 2 as factors. An odd number - 2 is still an odd number, so we are looking for even numbers with an odd number of factors.

 

No odd numbers have 2 as a factor, so each odd number is only having one factor discounted (1). So we are looking for odd numbers with an even number of factors.

 

When would a number have an odd number of factors? Factors always come in pairs. Back to the example of 12, the factor pairs are 1 and 12, 2 and 6, and 3 and 4. A number only has an odd number of factors if one of the factor pairs is two of the same number, so perfect squares.

 

Which lockers will remain open then? Even numbered lockers that are perfect squares and odd numbered lockers that are not perfect squares. There are 500 even and 500 odd numbers between 1 and 1000. 31² = 961 and 32² = 1024, so there are 31 locker numbers that are perfect squares. 15 of these are even and 16 are odd. The total is then the 15 even lockers that are perfect squares plus the 500 - 16 odd lockers that are not. So the total is 15 + (500 - 16) = 499.

 

If instead you meant that the 1st student opens all of the lockers, then the answer is just the locker numbers that are perfect squares, so 31.