Question

We have 100 lamps, numbered 1, 2, …, 100. Initially they are all off.

1) we press the switches of the lights whose number is an integer multiple of 1, that is, the switches of all 100 lamps are pressed and therefore are turned on.

2) we then press the switches of the lights whose number is an integer multiple of 2, that is, the switches of lamps 2, 4, 6, …, 100 are pressed and therefore are turned off.

3) we then press the switches of the lights whose number is an integer multiple of 3, that is, the switches of lamps 3, 6, 9, …, 99 are pressed and therefore are turned off (if before they are on) or turned on (if before they are off).

4)

5)

……

100)

Which lamps are left on after these tireless on’s and off’s? Is there a beautiful way to solve the problem?

Answer

Consider any integer N. In the beginning its “off”.

If the integer N is “on” after “all the processes above” is done, it means that it must have undergone “off” “on” repeatedly say k times. Thus,
N : “off”, “on” [ k times ] and “ends” in “on”.
Now, each “off” and each “on” is ONLY performed on N for a “factor” of N. N has 2k + 1 factors as shown above including 1. This Means that we have an “odd number of factors for N including 1”. What kind of integers that have an odd number of factors including 1?
Let N = 1* p(1)^a(1) * p(2)^a(2) … p(k)^a(k) in its prime factorization including ‘1’. p(1), p(2)… p(k) are primes while
a(1), a(2), … a(k) are integers for the exponent of the primes.
It can be shown that ONLY PERFECT squares have “odd number of factors including 1”. Thus only, perfect squares have the “lights being set to on”.

For non perfect squares, they will be “off” because they have a total of “even number of factors including 1”.

End of Answer.

P/S:

A proof for the “theorem” that “only squares have an odd number of factors including 1?” if we “dont consider 1 as a factor, then it is equivalent to showing N has a even number of factors”.

So the problem is equivalent to finding what numbers have an even number of factors, and which have an odd number of factors.

Consider a number N, if a is a factor of N, then there exists a number b such that ab = N, by definition of a factor. So that means that for every factor, there exists another factor in the set of factors of N.

Consider N such that that for all a that are factors of N, the b for which ab = N is not a. Thus for every factor a, there is another factor. Thus, there is an even number of factors.

Consider N such that there exists an a in the set of of factors of N, such that ab = N where b is a, or in other words that a^2 = N. For now, assume that there is only one such a (to be proven later). Now if you remember from the previous case, the number of all factors of N besides a is even. Thus including a would lead to an odd number of factors. Now, if our assumption is true, then we have proved what we wanted to.

To prove there is at most one a such that a*a = N, assume the opposite. That is, assume there is distinct A and B such that there squares are equal to N, with A being the greater. Let B be represented by A – C.
Then A*A = (A – C)(A – C). Take the square root of both sides, A = A – C. But this is true only if C = 0. But then B = A, contradictory to hypothesis. Thus there is no more than 1 a such that a*a = N.

So all of this demonstrates mathematically why only the square numbers are on.