Problem:

There are N doors in a hallway all closed. There is a robot that iterates through every ith door and it is programmed to invert that door’s state. After i=N the robot stops. For i=1 the robot opens all the doors. For i=2 all even doors get closed. For i=3, door 3 gets closed and door 6 is opened etc. Which doors are left open after the robot is done going through all the doors?

Solution:

I knew that once an ith door was reached whatever state it received became it’s final state. Which means door #1 is always open and doors #2 and #3 are always closed.

It wasn’t immediately obvious to me which doors would remain open, so I wrote a little python program to help me see a pattern.

1 2 3 4 5 6 7 8 9 10 11 12 |
import math def doors(x): for n in range(1,x+1): dstate = False for m in range(1,n+1): if n % m == 0: dstate = not dstate if dstate: print "%.2f^2" % math.sqrt(n), doors(1000) |

Output

1.00^2 2.00^2 3.00^2 4.00^2 5.00^2 6.00^2 7.00^2 8.00^2 9.00^2 10.00^2 11.00^212.00^2 13.00^2 14.00^2 15.00^2 16.00^2 17.00^2 18.00^2 19.00^2 20.00^2 21.00^222.00^2 23.00^2 24.00^2 25.00^2 26.00^2 27.00^2 28.00^2 29.00^2 30.00^2 31.00^2

Clearly the pattern is obvious. The mathematical reason why this is so is more interesting than a simple empirical trend. Every integer has an even number factors… except squares.

4:1,2,4

6:1,2,3,6

7:1,7

8:1,2,4,8

9,1,3,9

This is because the singleton factor is it’s own factor pair.