The clank of the little kids...
You walk into a school with 100 kids all of which are hyperactive. The school has 100 lockers one for each numbered from 1 to 100. The first kid walks into the locker room and opens all of them. The second kid zooms past and changes the status of every even numbered locker. The third kid waltzes through the room changing the status of lockers divisible by 3 (3,6,9 etc.), the fourth one does the same with all that is divisible by 4 and they do the closing and opening alternately. Which lockers are open at the end of the day? And what's your logic?
posted by littlecow at 10/05/2005 09:12:00 PM
8 Comments:
It will be even numbered closed and odd numbered open. This is because the odd numbered always open any multiple of (2n+1)and the even numbered closes any multiple of 2n. After, the 2nth guy closes up 2nth locker, no one touches it and same thing with (2n+1)th locker being open.
@bal: I have reworded the question a bit. You did not catch the correct answer as yet.
@lc: u had the question wrong... I was thinking after answering ur previous question that the current question would have been much tougher than the previous question, Anyways, will probably htink about the answer tonight.
@a: You are wrong. You have to think beyond the local stuff.
@L.C: The answer is that it is 10 lockers that are open - only the perfect squares.
Proof: To remain open, the number of factors of the locker number should be odd.
So, locker 1 will remain open cos it's only factor is itself - 1.
Any prime numbered locker will have 2 factors - 1 and itself. Hence they will be open.
For any other locker, let the prime factors be a,b,c,... The number will be (a^m)(b^n)(c^o)....
n,o >= 0. m>0 (atleast one factor... not a prime number which I have already proved is closed).
If there is 1 factor a:
Then the factors will be 1, a, a^2, ..., a^m-1, a^m .
so number of factors is m+1. If m is odd, then the locker is closed. If m is even, the locker is open but it is also the square of the number a^(m/2).
If there are 2 factors:
The factors are 1, a, a^2,..., a^m, ab, a^2b, a^3b,.....,a^mb,....a^mb^n.
The number of factors are 1+m*n. To remain open, m and n have to be open implies that the locker number is a perfect square of a^(m/2)b^(n/2).
This can be proved similarly for any number of factors.
QED.
PS: Brain wave in the shower led to this revelation ;)
In the above I meant both m and n have to be even.
@~a~: you are on the right track to work out examples and get the logic next. better luck next time!
@erstwhileroomie: *clap, clap, clap*, you got it right!
@~a~: right ho! the crucial question now is why are these perfect squares divisible by an even number of numbers?
@~a~: you got it but bornalibran got there before you! i like your recursion logic which is pretty neat (and clever). i debated as to whether i should give you a point for this but decided otherwise. but way to go! -- and good luck to beat the field!
Post a Comment
<< Home