Fog Creek Software
Discussion Board


The final status of a particular door will be determined by the number of factors it has, I think.
e.g 27
Door #27 will be flipped during the following passes:
#1 , #2, #3,  #9, #27 (all of which are factors of 27)

So if number of factors is odd the status of the door will change. If its even, it'll remain the same. 

Monday, April 29, 2002

actually 2 is not a factor of 27 :)

but, i agree about the even & odd number of factors.  i don't know why the solution says only perfect squares.  why doesn't the #6 qualify?

6 will be toggled 4 times: 1,2,3,6 ... and so will any # that has even # of factors.

why only perfect squares?!

Monday, April 29, 2002

well, as you point out, 2 is not a factor of 27, and as the solution points out, the door will be open and closed for every pair of factors the number has.

so 27 has 1 and 27, and 3 and 9.  so it will be hit 4 times.  so it will be closed.  in fact since factors are always PAIRED, every number will be hit an even number of times, EXCEPT THOSE DOORS THAT HAVE PERFECT SQUARES.

this is because the perfect square factor makes the number of passes for the door odd.

an example: door 9.  factors are 1 and 9, 3 and 3.  so it will be hit on pass 1 and 9, but then only once on pass 3!  so it will only be touched an ODD number of times, and hence its state will toggle.

just remember, EVERY number has an even number of factors.. due to the definition of what a factor is, its got to have another number to go with it.. but perfect squares have duplicate factors, so the unique factors for the number are actually odd.

Michael H. Pryor
Monday, April 29, 2002

of course!  don't know what i was thinking.  thanks for clearing that up.

Tuesday, April 30, 2002

*  Recent Topics

*  Fog Creek Home