There are light bulbs numbered starting from , each of which is turned on and off by a normal switch. At the beginning all the bulbs are off; then all the switches of the bulbs marked with multiples of are pressed once (as a result all the bulbs are turned on), subsequently the switches of all those in even position (that is, multiples of ) are pressed once, then those marked with multiples of , subsequently the state of those relating to multiples of is changed, and so on, up to the multiples of . Which of the following bulbs remains on at the end of the operations?
Pick one
Solution
Solution:
The answer is . The switch in position is touched once for each positive divisor of . So the -th bulb remains on at the end if and only if has an odd number of divisors. This happens only for perfect squares: indeed if is not a perfect square, we can pair up its divisors by forming all the pairs of the type , and this tells us that they are even in number. If is a perfect square, we can pair up all its divisors except by again pairing : hence has an odd number of divisors. At this point, it is easy to check that the only perfect square among the possible answers is .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.