26 light switches flipped by multiples of 1, 2, 3, 4 .... to 26. How many light switches are flipped on?

Question

I am stuck on this math problem.

There are 26 light switches. All the even ones are off and all the odd ones are on. Pere switches all the lights that are multiples of 1, then 2, then 3, until 26. How many light switches remain on?

Answer 1

Work out how many times each switch is flipped i.e. turned from on to off or from off to on.

For example, switch 8 is flipped four times because it is a multiple of 1, 2, 4 and 8. But switch 9 is only flipped three times because it is a multiple of 1, 3 and 9.

Which switches are flipped an even number of times (and so end up in the same state that they started) ? Which switches are flipped an odd number of times ? Can you see a pattern ?

Answer 2

Note that very perfect square has an odd number of divisors and a number that is not a perfect square has even number of divisors. This is easy to prove by noting that if there is a number $n$ with a divisor $d$, there is a divisor $\frac{n}{d}$, and so there are pairs of divisors. But in case of perfect square, $d=n/d$ for some unique $d$, so there will be total divisors $2k+1$ i.e. some odd number of divisors.

Switches that are odd perfect squares will be off, even perfect squares on, other even numbers off, and other odd numbers on.