100 Doors | Puzzles for Interview - Interview Preparation PDF Download

Introduction

In the 100 Doors game, there are 100 doors initially closed in a row. A person walks through all doors multiple times and toggles them in a specific way. The puzzle is to find out which doors will be open at the end.

Method

In the first walk, the person toggles every door. In the second walk, the person toggles every second door. In the third walk, the person toggles every third door. And so on until the 100th walk when the person toggles only the 100th door.

Explanation

To solve the puzzle, we need to understand the pattern of door toggling. A door is toggled in an ith walk if i divides the door number. For example, door number 45 is toggled in the 1st, 3rd, 5th, 9th,15th, and 45th walks.
The door is switched back to an initial stage for every pair of divisors. For example, 45 is toggled 6 times for 3 pairs (5, 9), (15, 3), and (1, 45).
It looks like all doors would become closed at the end. But there are door numbers that would open. For example, door number 16 has divisors (1, 2, 4, 8, 16), and as the pair (4, 4) contributes only one divisor, making the number of divisors odd, it would become open at the end. Similarly, all other perfect squares like 4, 9, and 100 would become open.
For prime numbers like 2, 3, 5, 7, etc., the divisors are (1, that number), and it is a pair, so they will remain closed at the end. And for all other numbers, divisors are always in pairs, e.g. 15 = (1, 15), (3, 5), they will also remain closed.

Conclusion

Therefore, the doors that will be open at the end are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.