You are standing in a school hallway lined with 100 closed lockers. You then open all 100 lockers. After this, you then close every 2nd locker (so the 2nd, 4th, 6th…98th and 100th are all closed). Then, you go to every third locker and open it if it is closed or close it if it is open (let’s call this toggling the locker for our discussion). You proceed to toggle every nth locker on pass number n. So, for example, on pass number 16 – you will toggle every 16th locker. After your hundredth pass of the hallway, in which you toggle only locker number 100, how many lockers are now open? In a hall with x lockers, how many lockers remain open after pass number x?
A locker will end up closed if it has an even number of factors, because the number of times a locker is toggled equals the number of factors. If a locker has an odd # of factors, the locker will end up being open.now all we need to do is figure out how many numbers between 1 and 100 have an odd # of factors.
What exactly does it mean when we say that c is a factor of d, for some #’s c and d?
It means that c multiplied by some other number b is equal to d. The number of factors is usually even since factors tend to come in pairs.
What if the factors are the same numbers – if b is equal to c? Then, the number d would be a perfect square, since b*b would equal d, which would be a perfect square.
So the answer is exactly 10 lockers will remain open.
Generalizing the solution to this brain teaser
If there are x lockers, the number of open lockers will be the number of perfect squares between 1 and x (inclusive). To count them, all you need to do is find the square root of the largest perfect square less than or equal to x. So, the general solution would be: floor(sqrt(x))
Here’s an example to help illustrate this: If x = 200, then sqrt(200) = 14.142 .
No comments:
Post a Comment