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.

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.

Leave a Reply