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.

Advertisements

4 Comments (+add yours?)

  1. kelsoking
    Jun 24, 2012 @ 00:29:06

    I agree that there are ten lockers open but aren’t familiar with whats-it-called theorem. I thought of the solution as the numbers that are squares, have an odd number of distinct factors, so 1 squared, 2 squared, up to 10 squared. These numbers can have other factors, but they are in pairs, e.g. 4 squared is also 2 x 8. Probably exactly what you’re saying but I thought the squaring thing was worth mentioning.

    Reply

  2. oshin choudhary
    May 24, 2013 @ 00:33:35

    what about prime nos?!?! and btw 1 will not be open!! so there are 9 + prime nos!!

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: