Source

I got this problem from Rustan Leino, who got it from Mariela Pavlova.

I solved it and wrote up my solution.

Problem

A room has 100 light switches, numbered by the positive integers 1 through 100. There are also 100 children, numbered by the positive integers 1 through 100. Initially, the switches are all off. Each child $k$ enters the room and changes the position of every light switch $n$ such that $n$ is a multiple of $k$. For instance, child 1 changes all the switches; child 2 changes switches $2, 4, 6, 8, \ldots$; child 3 changes switches $3, 6, 9, 12, \ldots;$ and child 100 changes only light switch 100. When all the children have gone through the room, how many of the light switches are on?

Solution
Reveal

Ten switches are on at the end, those numbered with squares of integers.

The reason for this is as follows. If child $k$ switches a switch $n$, child $n/k$ also switches it. So, children's switchings always cancel each other out in pairs except when $k = n/k.$ This is equivalent to $n = k^2,$ so the only time a child switches the light without being cancelled is when $n$ is a perfect square and the child $k$ satisfies $k = \sqrt{n}.$