I'm a big fan of logic
puzzles. Normally, we only get asked these kind of questions during interviews but they are pretty fun to think about outside of an interview setting.
Here we go:
There are 100 doors in a long hallway. They are all closed. The first time you walk by each door, you open it. The second time around, you close every second door (since they are all opened). On the third pass you stop at every third door and open it if it's closed, close it if it's open. On the fourth pass, you take action on every fourth door. You repeat this pattern for 100 passes.
Question: At the end of 100 passes, what doors are opened and what doors are closed?
Snaps if you can figure it out. (No googling allowed!)
Update:
See answer below:
So, there are many ways to approach this problem.
Here's how I went about solving this puzzle. There are two states a door to be in, opened or closed. On each pass of a door, the door's state is toggled. Since all the doors starts off closed, we can say if we visit a door an even number of times, the door will be closed. If we visit the door an odd number of times, it will be opened in the door. Let's see this in action with 5 doors (O = Opened, C = Closed)
| Pass # |
Door 1 |
Door 2 |
Door 3 |
Door 4 |
Door 5 |
| Initial |
C |
C |
C |
C |
C |
| Pass 1 |
O |
O |
O |
O |
O |
| Pass 2 |
O |
C |
O |
C |
O |
| Pass 3 |
O |
C |
C |
C |
O |
| Pass 4 |
O |
C |
C |
O |
O |
| Pass 5 |
O |
C |
C |
O |
C |
One thing to note is once we pass door X X times, we never will have to toggle door X again. For example, once we pass door 10 on the 10th pass, on the 11th pass and subsequent passes, we will never have to revisit doors 10 and all the doors before 10.
Looking at the 5 doors shown in the table above, we see that only door 1 and door 4 are left open. They will remain open for the rest of the passes to 100. What's special with 1 and 4? What makes us visit a door an odd number of times versus an even number of times? Let's look what made us close door 2, 3, and 5 and open 1 and 4.
On the first pass, we opened all of the doors because it was the 1st pass.
Here we know door 1 is going to remain opened.
On the second pass, we closed all of the doors with numbers that were even or divisible by 2. (doors 2, 4, 6, 8, etc)
Here, we know door 2 is going to remain closed.
On the third pass, door 3 gets closed and remains closed.
On the fourth pass, door 4 gets reopened and remains opened.
On the fifth pass, door 5 is closed.
The factors of 1 are 1 and itself. It has one factor
The factors of 2, 3, and 5 are 1 and themselves. They have two factors.
The factors of 4 are 1 and itself, as well as 2. 4 has three factors.
Didn't we say if we visit a door an odd number of times, it remains open?
It turns out the number of factors a number has is the same number of times we visit it.
If a number has an odd number of factors, we visit it an odd number of times.
If a number has an even number of factor, we visit it an even number of times.
So, the big question is what numbers have an odd number of factors?
Looking at 1 and 4 gives us some insight. Both numbers have factors that are performing double duty.
1 has 1x1 and 4 has 2x2. While factors come in pairs, we only count these factors that are performing double duty as one.
What do we call numbers that have factors that perform this double duty?
Perfect squares.
The answer is doors 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 are opened. The rest are closed.
