## How many lockers are open after 100 passes of toggles

There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?

My initial thoughts (Solutions):
Before the 1st pass, all the lockers are closed. To remain open in the end, the locker must be toggled odd number of times. Let us then think about it: when will closer i be toggled? It depends on the factors of i. For example, if i = 6, since the factors of 6 are 1, 2, 3 and 6. It will be toggled at the 1st, 2nd, 3rd and 6th passes. As a result, it will be closed after 100 passes. Therefore, all the lockers with odd number of factors will be open in the end. What are the numbers with odd number of factors? From cant-remember-name theorem, the number of factors of number $n = p_{1}^{r_{1}} \times p_{2}^{r_{2}} \times \dots p_{k}^{r_{k}}$ is given by $(r_{1}+1) \times (r_{2}+1) \times \dots (r_{k}+1)$. To make this number odd, you must have $(r_{k}+1)\%2=1$ for any $k$. That is, $r_{k}$ is even for all $k$. What does that mean? That means n is a perfect number! So, how many perfect numbers are there from 1 to 100? 10 of them. Therefore, after the 100th pass, we will have 10 lockers open.