Add Me!Close Menu Navigation

The Locker Room Problem

Twenty bored students take turns walking down a hall that contains a row of closed lockers, numbered 1 to 20. The first student opens all the lockers; the second student closes all the lockers numbered 2, 4, 6, 8, 10, 12, 14,16, 18, 20; the third student operates on the lockers numbered 3, 6, 9, 12, 15, 18: if a locker was closed, he opens it, and if a locker was open, he closes it; and so on. How many lockers remain open after all the students finish?

This is actually a simple problem after considering Divisors of Perfect Squares.

1. Reducing the problem into an instance of counting divisors

From the definition of the problem, we can gather that student i can only open lockers that are multiples of i. This naturally suggests that locker i will be operated on by student j if and only if i is a multiple of j. This can be easily proven.

Locker i will be operated on by j only when i is a multiple of j

By definition, i will be operated on by j if some multiple of j becomes i. Similarly, when i is a multiple of j, then student j will have to operate on locker i. \blacksquare

Because only only divisors of i will touch the i^{th} locker, then it’s clear that the number of times locker i gets operated on is the number of divisors of i.

2. Only lockers that are perfect squares remain open

Naturally, if a locker is operated on for an even number of times, it remains closed, because there are an integer sequence of opening-then-closing that locker. Similarly, if a locker is operated on for an odd number if times, it will become open.

Because the number of times the i^{th} locker is operated on is the number of divisors of i, then only those lockers with odd number of divisors can remain open. As we’ve proven previously, only perfect squares have odd divisors, hence only the perfect squared lockers remain open in the end. \blacksquare

Posted By Lee

Woosh