Problem #10 HARD
The Infinite Hallway of Lockers
Microsoft Math Pattern Recognition
Problem Statement
A school hallway contains 100 closed lockers, numbered 1 to 100.
A student walks down the hall and opens every locker. A second student walks down and closes every second locker (2, 4, 6, ...). A third student changes the state of every third locker (3, 6, 9, ...), opening it if it was closed, and closing it if it was open. This process continues until 100 students have walked down the hallway.
After the 100th student finishes, which lockers will remain open?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
Only the perfect square lockers (1, 4, 9, 16, 25, 36, 49, 64, 81, 100) will remain open because they have an odd number of factors.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
A locker's state changes every time its number is a multiple of the student's number. This means Locker N is toggled by Student D if and only if D is a divisor (factor) of N.
All lockers start closed. A locker will end up OPEN if it is toggled an odd number of times, and CLOSED if it is toggled an even number of times.
Thus, the question reduces to: Which numbers between 1 and 100 have an odd number of factors?
Factors usually come in pairs (for example, the factors of 12 are 1 & 12, 2 & 6, 3 & 4). The only way a number can have an odd number of factors is if one factor pairs with itself (e.g., 4 * 4 = 16).
These are the perfect squares. Their factors are:
- 1: 1 (1 factor - odd)
- 4: 1, 2, 4 (3 factors - odd)
- 9: 1, 3, 9 (3 factors - odd)
- 16: 1, 2, 4, 8, 16 (5 factors - odd)
Therefore, the lockers that remain open are the perfect squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.