School Lockers - Solution
|
|
School Lockers - Solution |
10 lockers are open at the end.
Any given locker is open if an odd number of pupils switch it, and closed if an even number switch it.
A pupil switches a locker if her number is a factor of the locker number. For example, for Locker 12, Pupils 1, 2, 3, 4, 6 and 12 are factors of 12 and will therefore switch it.
In the example above, notice that the factors come in pairs - [1 and 12], [2 and 6], [3 and 4]. This is because each factor must be multiplied by its "twin" to make the number.
This means that, typically, each locker number will have an even number of factors, since the factors come in pairs.
The only exception is where there is a factor which doesn't have a "twin". This is the case if the locker number is a square number, since its square root is its own "twin". For example, the factors of 16 are 1, 2, 4, 8, 16, where [1 and 16], [2 and 8] are pairs, but [4] is multiplied just by itself to give 16. So, every locker number that is a square will have an odd number of factors.
So, the only locker numbers which are open (ie switched by an odd number of pupils) are the squares between 1 and 100.
These are: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
This means that there are 10 lockers open at the end.
If you think about it, the number of squares up to a given number is the largest whole number which is less than or equal to its square root.
For example, if there are 1,000,000 lockers, then √1,000,000 ie 1,000 lockers will be open at the end.
|
© 2002 Ian Hadden |