Doors Problem

2008-07-28

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.

Contents