Expert: Paul Klarreich - 3/1/2007

Question
Hi, I took an AP Calculus course last year, and after the AP we did a lot of theoretical insane problems. Well, I've recountered a problem that was extremely similar to the one of them. Think you could look it over and give me a hint or two?

In an exceptionally long corridor in a station, there are one thousand windows along one wall. Coincidentally, there are exactly one thousand workers in the station. The the first worker is ordered to open the blinds on every window. Then, the second worker is ordered to close the blinds on every second window. Then the third worker is told to go to every third window, and close the blinds if they are open, and open the blinds if they are closed. The fourth worker does this for every fourth window, and so on.

After all 1000 workers complete the process, how many blinds are open?




Thanks,
Patrick!

Answer
Questioner:   Patrick
Category:  Calculus
 
Subject:  MATHH *pulls hair out*
Question:  Hi, I took an AP Calculus course last year, and after the AP we did a lot of theoretical insane problems. Well, I've recountered a problem that was extremely similar to the one of them. Think you could look it over and give me a hint or two?

In an exceptionally long corridor in a station, there are one thousand windows along one wall. Coincidentally, there are exactly one thousand workers in the station. The  first worker is ordered to open the blinds on every window. Then, the second worker is ordered to close the blinds on every second window. Then the third worker is told to go to every third window, and close the blinds if they are open, and open the blinds if they are closed. The fourth worker does this for every fourth window, and so on.

After all 1000 workers complete the process, how many blinds are open?

Thanks,
Patrick!
...........................................
Hi, Patrick,

I think this is an oldie, but goodie.

Each window begins in the closed state and undergoes a series of reversals.  If there is an even number of reversals for the window, it remains closed, and if an odd number, it will be open.

Consider some number, say 10.  Which 'workers' will reverse window 10?  The answer is: Those workers whose numbers are divisors of 10, meaning 1,2,5,10.  That's an even number of divisors/workers, so W-10 remains closed.

Do all integers have an even number of divisors?  For any integer n, let a | n.  

[That is read  "a divides n" or "a is a divisor of n"].

Then  a/n is also a divisor of n, and we should expect the divisors of n to occur in matched pairs, giving an even number of divisors for every number,

UNLESS

(can you guess what the UNLESS is?)

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

That's right.  What if  a  and  n/a are the same number?  Then n = a^2, meaning n is a perfect square.  In fact, that's almost a number-theoretic definition of a perfect square -- an integer with an odd number of divisors.

So the windows which are perfect squares are the ones that will be open.  How many are there?  

The number of perfect squares up to 1000 would be the integer part of sqrt(1000), which is 31.6, so there will be 31 windows remaining open.

Cute.