# Doors Problem

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.

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.