A high school has a strange Headmaster. On the first day, he has his pupils perform an odd opening day ceremony:
There are one thousand lockers and one thousand pupil in the school. The Head asks the first pupil to go to every locker and open it. Then he has the second pupil go to every second locker and close it. The third goes to every third locker and, if it is closed, he opens it, and if it is open, he closes it. The fourth pupil does this to every fourth locker, and so on.
After the process is completed with the thousandth pupil, how many lockers are open?
Originally posted by MathurineThe toggling of a given door happens every time a factor of that door number is hit. For example, door 14 will be toggled on turn 1, 2, 7 and 14, all the factors of 14. Prime factors always come in pairs (eg. 1x14, 2x7). However, if you have a repeated prime factor, as in a perfect square (eg. 4) the repeated prime gets paired up with itself (eg. 4 = 1x4, 2x2) , resulting in an odd number of toggles. This doesn't happen with numbers that contain perfect squares as factors, as the square gets paired up (eg. 12 = 1x12, 2x6, 3x4). It doesn't happen with perfect cubes (eg. 8 = 1x2x2x2 = 1x8, 2x4) or squares of perfect squares either (eg. 16 = 1x2x2x2x2 = 1x16, 2x8, 4x4), because multiplying the repeated prime by itself is always less than the number in these cases.
A high school has a strange Headmaster. On the first day, he has his pupils perform an odd opening day ceremony:
There are one thousand lockers and one thousand pupil in the school. The Head asks the first pupil to go to every locker and open it. Then he has the second pupil go to every second locker and close it. The third goes to every third locker an ...[text shortened]... .
[b]After the process is completed with the thousandth pupil, how many lockers are open?[/b]
So, every door number that is a perfect square will remain open. Here's the list:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961
Nice analysis!
The only lockers that remain open are perfect squares (1, 4, 9, 16, etc) because they are the only numbers divisible by an odd number of whole numbers; every factor other than the number's square root is paired up with another. Thus, these lockers will be "changed" an odd number of times, which means they will be left open. All the other numbers are divisible by an even number of factors and will consequently end up closed.
So the number of open lockers is the number of perfect squares less than or equal to one thousand. These numbers are one squared, two squared, three squared, four squared, and so on, up to thirty one squared. (Thirty two squared is greater than one thousand, and therefore out of range.)
So the answer is 31