|
Since we "toggle" the doors, we can realize that the only doors that are open at the end of the exercise are the ones that are toggled an odd number of times. We also know that a door is toggled once for each divisor that it has.
But divisors come in pairs. By definition, if N is divisible by M, there is also some other number K = N/M which N will be divisible by.
The only way around this is when K = M, which means that N = M^2. When we are dealind with doors whose number is a perfect square, they will be toggled only once for the pair of divisors that is a square of.
(So 4 can be broken into 1*4 and 2*2, meaning it will be open on the first, closed on the second and re-opened on the fourth passes.)
Since there are 10 perfect squares between 1 and 100, that's how many doors will stay open. |
