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?
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)
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.