A room contains 1001 bulbs each numbered from 1 to 1001. the bulbs are controlled by a toggle switch and all the bulbs are initially turned off. There are 1001 number theory experts each wearing a label also numbered from 1 to 1001. Each number theory expert is assigned to go into the room and press the switch of a bulb once if and only if the label he or she is wearing is a divisor of the number on the bulb. Which bulbs would be switched on after all the number theory experts have finished their assignment?
Asked
Active
Viewed 66 times
0
-
So, a question titled "How to solve this" is a duplicate of a question titled as "A tedious puzzle (but not homework)"... Work on your titles, please! – Dec 03 '14 at 05:14
3 Answers
2
HINT: The bulb in room $n$ will be turned on if and only if $n$ has an odd number of divisors. (Why?) What positive integers fit that description?
It never hurts to get your hands dirty working out a few cases by hand. What happens to bulbs $1$ through $20$, say?
Brian M. Scott
- 616,228
2
If all the bulbs are off at the beginning, then in order for a bulb to be on at the end, it must be switched on or off an odd number of times.
Each bulb is switched on or off if the number the professor is wearing a number that divides the number of the bulb. That is, if $b$ is the bulb number and $n$ is the professor number, then the bulb is switched iff $n|b$.
By putting these pieces together, what do you get?
Edward Jiang
- 3,670
