How do I go about proving which lockers will be closed?

Question

"At first, all the lockers are closed. A person walks by, and opens every other locker, starting from locker 2. Thus lockers 2, 4, 6, ... 998, 1000 are open. Another person walks by, and changes the "state" (open or closed) of every third locker. Another person changes the state of every fourth locker, and so on."

I have figured out the answer to this question - lockers whose numbers are perfect squares will be closed (1, 4, 9, 16, 25, and so on). It's simple once you think about it; the number of factors a number has is how many times its "state" has been changed. If we look at 6, it can be broken into 1 x 6 and 2 x 3. Disregarding 1 (because nobody went around changing all the closed lockers to open), the state has been changed 3 times leaving it open. Now take 25. Breaking it apart into its factors, we get 1 * 25 and 5 * 5. We can't include 5 twice, so there are an even number of state changes leaving it closed.

So I understand this problem, but how can I prove it?

Answer 1

You may prove it almost as you have said. You need to put forward a few key-points, though.
1) the lock will be open if its state would be changed odd amount of times, and will be closed if its state would be changed even amount of times.
2) If a number N is not a perfect square, when it has a fact p, it must have another fact q<>p, such that pq = N. Therefore, If a number is not a perfect square, it must have even numbers of factors.
3) If a number N is a perfect square, there must be a number r such that r^2 = N. Therefore, If a number is a perfect square, it must have odd numbers of factors.
4) Since there was not a person to come to changes the "state" for every locker, the factor "1" for every number does not corresponds to a state change.
5) Hence, if the lock number is not a perfect square, its state would be changed odd number of times, and the locker would be finally open, and vice versa.

Answer 2

To prove that perfect squares have an odd number of factors, you prime factorize it.

Suppose arbitrarily there is a perfect square n. Then it can be factored as:

a1^e1 a2^e2 a3^e3 a4^e4 ... ak^ek, where a1 a2 a3... ak are prime numbers, which have no factors themselves. e1 e2 e3...ek are positive even integers. Then the number of factors of n can be calculated by taking the product of each exponent+1 because that is the number of ways you can make a number that is divisible by n. So the number of factors is (e1+1)(e2+1)(....)(ek+1)

Since e1+1, e2+1,... ek+1 are odd numbers, so is their product. So a perfect square has an odd number of factors.

To prove the converse, suppose a number has an odd number of factors. Then it follows that e1+1,e2+1... ek+1 are all odd. Therefore e1,e2,....ek are even. So that number is a perfect square.