A new school has exactly 1000 lockers and 1000 students. On the first day of school, the first student enters the school and opens all the lockers. The second student then enters and closes every locker with an even number. The third student will 'reverse' every third locker(if closed, it will be opened and if open, it will be closed). The fourth student will reverse every fourth locker and so on, until all 1000 students have entered and reversed the proper lockers. Which lockers will be open at the end?
Need answers AND explination quickly please...!!!! Thanks!!!!!!!!!!!!
This is an old one known as the "locker problem".....let's take a more simple example that will lead us to where we want to go
Let's take an example with just 10 students...o = open, c = closed
Student 1 o o o o o o o o o o
Student 2 o c o c o c o c o c
Student 3 o c c c o o o c c c
Student 4 o c c o o o o o c c
Student 5 o c c o c o o o c o
Student 6 o c c o c c o o c o
Student 7 o c c o c c c o c o
Student 8 o c c o c c c c c o
Student 9 o c c o c c c c o o
Student 10 o c c o c c c c o c
Do you notice which lockers remain open?? ... 1, 4 and 9....
In other words......the ones whose numbers are perfect squares
So....the lockers that remain open are just the ones that are perfect squares from 1 - 1000
And these are {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}
You might be curious as to why this happens....
Notice that non-sqares aways have an even number of divisors [ including themselves]
So that each "non-square" locker is visited an even number of times
For example....locker 6 is visited by the first student who opens it, by the second student who closes it, by the third student who opens it and then by the sixth student who closes it and it is never touched again
But consider locker 9...it's opened by the first student, closed by the third and opened by the ninth and never touched again....!!!!...in other words, it is visited an odd number of times....the same number as the number of its proper and improper divisors....!!!!