This problem has been circulating around the internet as an example of a problem posed at job interviews.

You have a row of 100 doors that are all closed. You are going to pass along the row from 1 to 100 switching the status of the doors. If a door is open, you closed it, if it is closed, you open it.

On your first pass, you switch every door. On the second pass, you switch doors 2, 4, 6, etc. On the third pass, you switch doors 3, 6, 9, etc. You keep doing this until on the 100th pass, you switch only door 100.

What will the status of the doors be when you're done? Will there be any interesting pattern?

Solution

I love this problem because it has such an elegant solution. The number of times a door will be switched is equal to the number of factors it has. For instance, door 32 will be switched on the 1st, 2nd, 4th, 8th, 16th, and 32nd passes--6 in all. Most doors have an even number of factors, so they will end up in their current state–closed.

The perfect squares have an odd number of factors, so in the end, they will be left open!

It will be interesting to see if anyone in the class solves this either with a spreadsheet or by writing code to see what happens. Seeing the different approaches that others take is part of the fun of problem solving.

Menu