Problem of the Week 1048

Another Locker Dilemma

A hallway contains 1048 closed lockers. Suppose students numbered 1, 2, 3, ... , 1048 walk down the hall in order. Student k will look only at lockers whose number is divisible by k and open it if it is closed and close it if it is open. A famous problem asks which lockers remain open after all the students pass. The answer is the squares, those being the only numbers with an odd number of divisors.

Suppose that we want to have only locker #1 be open at the end, and we can restrict the set of students who are sent down the hall as we choose. Which students should be sent?

Source: A recent paper by Bruce Torrence (Randolph-Macon College), Mathematica in Education and Research 11:1 (2006) "Extending the locker problem."

One can pose many variations of this question. Here are some, in rough order of difficulty. We may as well consider the full infinite sequence of lockers (1 ,2, 3, ...) and have a similarly infinite supply of students, numbered 1, 2, 3, ....

1. (Torrence) Suppose we want to have only locker #k open at the end. Which students should be sent?


2. (Torrence) Suppose we want to have only lockers whose number is prime open at the end. Which students should be sent?


3. (Torrence and Wagon) Suppose we want to have only lockers whose number is a perfect cube open at the end. Which students should be sent?


4. (Buhler, Torrence, and Wagon) As noted, if S is all positive integers, then the corresponding open-locker-set A is the squares. In short A = S². Find a set S that reverses this, in the sense S = A². (Well, if A is the empty set, then A² is the empty set; and that works as S. There is a nonempty set with this property.)


5. And for something completely different, an unsolved problem (due to Torrence): Consider the original question (with n lockers and n students, all of whom flip lockers). Note that the order in which the students are sent does not affect the final configuration. So there are n! ways of sending the students. Now, for each such permutation, let its "open count" be the sum, over all lockers, of the number of time periods each locker is open. Viewed graphically, one can imagine using white squares for open lockers and black for closed. Then the result of sending a permutation of the students through is an nxn array of white and black squares and the open count is the total number of white squares. Is there a characterization of the permutation that minimizes the open count? For n = 100, the best is a permutation found by Witold Jarnicki for which the total open count is 730.

© Copyright 2006 Stan Wagon. Reproduced with permission.