Doors 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?

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

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

Bridge Crossing Puzzle

I was reading Introduction to the Design and Analysis of Algorithms book and found a neat puzzle.

There are four people who want to cross a bridge; they all begin on the same side. You have 17 minutes to get them all across the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses either 1 or 2 people must have a flashlight. The flashlight must be walked back and forth, cannot be thrown. Person 1 takes 1 minute to cross. Person 2 takes 2 minutes. Person 3 takes 5 min. Person 4 takes 10 min. A pair must walk together at the slower person’s pace. For example if person 1 walks with person 4 it takes 10 minutes for both of them to cross. If person 4 takes the flashlight back, a total of 20 minutes has elapsed and the mission failed.

The most interesting part to me is the concept. You want to minimize the impact of the two slowest walkers, you try to avoid having either of them make more then one trip. You can mitigate the 5 min walker by sending him with the 10 min walker. The second optimization you try to do is decrease the “bringing-the-flashlight-back” time, so the fastest people should bring it back.

———– symbolizes the bridge the bridge
0) ———– 1 min 2 min 5 min 10 min
1) 1 min 2 min ———– 5 min 10 min
Time: 2
2) 2 min ———– 1 min 5 min 10 min
Time: 3
3) 2 min 5 min 10 min ———– 1 min
Time: 13
4) 5 min 10 min ———– 1 min 2 min
Time: 15
5) 5 min 10 min 1 min 2 min ———–
Time: 17