100 Lockers

23 Nov 2011

There are 100 lockers in a room. The 1st student opens every locker. The 2nd student closes the lockers whose number is divided by 2. The 3rd student toggles the lockers whose number is divided by 3. This is done until the 100th student finishes.

This problem shows exactly why I am not good at problem solving. I do not have an eagle eye to see the pivotal point.

At first, I come with the fact that

If x has prime factors a[0], a[1], ..., a[n], then we can see that x can be divided 2^n times (the empty set represents 1). With this way of thinking, any number is divided in an even number of times. Therefore, most of the lockers are closed.

The problem is it only works with a number with unique prime factors. It does not work with certain numbers, says 12, because 12 is 2 x 2 x 3. Two is used twice.

It turns out that the pivotal point is to see that:

if p divides n, then there is a counter part q in which p x q = n. Each pair of (p,q) is unique...

That is immediately conclusive that most of the lockers are closed except the lockers whose number is a perfect square.

The solution is just so simple if you can conceive it…

Give it a kudos