Question 977107: In the regional power station there are a thousand switches on the main console and these are numbered in order of 1-1000. An engineer is employed to control the switches. At the beginning of the shift, the engineer switches on all of the 1000 switches. Sometime later he switches off all the switches with even numbers. A little while later he changes the state of every 3rd switch (3, 6, 9, etc). In other words he changes the switch to “ON” if it was “OFF” and vice versa. Still later, he changes the state of every 4th switch, then every 5th switch and so on until the end of his shift by which by which time has visited the main console 1000 times in all to attend to the switches.
Find with a full explanation which switches will be in the “ON” position at the end of his shift.
Answer by Edwin McCravy(20056)   (Show Source):
You can put this solution on YOUR website!
1. if he changes the state of a switch an even number of times, the switch will
be off, because it was off when he started.
2. if he changes the state of a switch an odd number of times, the switch will
be off, opposite from what it was when he started.
3. He will change the state of a switch once for each factor of the number of
the switch.
EXPLANATION:
For instance, switch 27 will be turned on when he turns every switch on. That's
once. Then it will be turned off when the employee changes every 3rd switch,
turned on when he changed every 9th switch, and turned off when he changes every
27th switch. That was 4 times, because 27 has the four factors 1,3,9,27.
4. Perfect squares have an odd number of factors, while all other integers have
an even number of factors. That's because factors come in pairs, one factor
pairs with another factor produced by dividing the number by that factor.
However perfect squares have a square root, which will not form a pair, because
it will "pair" with itself, which will only gives 1 extra factor besides the
pairs.
EXPLANATION:
For instant 25 has factors 1,5,25. So switch 25 will be turned on when he turns
every switch on, then it will be turned off when the employee changes every 5th
switch, and turned on again when he changed every 25th switch. That was 3 times,
because 25 has the three factors 1,5,25.
5. Conclusion: the only switches that will be turned on at the end will be the
switches whose numbers are perfect squares.
Switches, 1,4,9,16,25,36,... will be on and all the others off.
Edwin
|
|
|
