[I got this problem from Mariela Pavlova.]

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. That is, child 1 changes all the switches, child 2 changes switches 2, 4, 6, 8, …, child 3 changes switches 3, 6, 9, 12, …, etc., 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?

©2020-2023 K.R.M. Leino - Split Template by One Page Love