Maths Olympiad Prep

Library / /29 of 43

Number theory Difficulty 5.6 AIME, harder Find the answer Italy

There are 1000010000 light bulbs numbered starting from 11, 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 11 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 22) are pressed once, then those marked with multiples of 33, subsequently the state of those relating to multiples of 44 is changed, and so on, up to the multiples of 1000010000. Which of the following bulbs remains on at the end of the operations?

Pick one

Solution

Solution:

The answer is (E)\mathbf{( E )}. The switch in position nn is touched once for each positive divisor of nn. So the nn-th bulb remains on at the end if and only if nn has an odd number of divisors. This happens only for perfect squares: indeed if nn is not a perfect square, we can pair up its divisors by forming all the pairs of the type (d,n/d)(d, n / d), and this tells us that they are even in number. If n=m2n=m^{2} is a perfect square, we can pair up all its divisors except mm by again pairing (d,m2/d)(d, m^{2} / d): hence m2m^{2} has an odd number of divisors. At this point, it is easy to check that the only perfect square among the possible answers is 972=940997^{2}=9409.

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.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.