On the locker problem

Rather than sticking to 1000 and getting overwhelmed by the sheer magnitude, let us try smaller instances first. In order to do that, let us understand what the problem demands in general.

According to the problem description, there are n doors and n students. The nth student toggles every nth door. If we stick to smaller values of n, it is entirely feasible to do some simulations by hand and extract patterns.

We start with all doors being open, and start tracking from the first student onward.

• With n = 2, we have: closed closed; closed open.
• With n = 3, we have: closed closed closed; closed open closed; closed open open; closed open closed.
• With n = 4, we have: closed closed closed closed; closed open closed open; closed open open open; closed open open closed.

Let us pause for a moment to think about some properties of natural numbers, which are those typically used for counting in everyday life; no negatives, no rationals, nothing like that.

1. Every natural number is either even or odd.
2. Every natural number other than one has at least two numbers, called the divisors, such that dividing the given number by the divisor results in another natural number: one and itself.
1. Prime numbers are those that only have one and itself as divisors.
2. Composite numbers are those that have three or more divisors -i.e. at least one more divisor in addition to one and itself-. A composite number always has either an odd or an even number of divisors, but always at least three.

Let us number each door from 1 to n. Since we are working with natural numbers, knowing their global properties helps us predict which ones will be open or closed. In fact, we have already studied the following cases: when the number of the door is prime, and when the number of the door is composite with an odd number of divisors.

Recalling that all doors are initially open, we can make the following prediction: given any nth door, if n has an even number of divisors (two sub-cases: composite with even divisors; prime), the door will be open after all students have finished; if n is odd, the door will be closed.

Indeed, one can even write a computer program to simulate each student toggling the door. Here is code using Python 3 (excuse the lack of syntax highlighting):

'''

Using the command prompt, run this file by "python filename.py [0-9]+",

or "python3 filename.py [0-9]+", et cetera,

where the third argument, denotes how many doors there are.

USE PYTHON 3 OR LATER VERSION.

'''

import sys

#The python interpreter crops "python", so argv[0] = filename.py,

#and argv[1] = number of doors.

numDoors = int(sys.argv[1])

doors = list()

#Initialize the doors

for i in range(0, numDoors):

    doors.append(1)

    

#This variable is needed to control the toggling offset

#every door, every second door, every third door, etc

offset = 1

#Simulate how each student toggles every nth door

for i in range(0, numDoors):

    for j in range(i, numDoors, offset):

        

        #Use the exclusive-or operator to flip

        doors[j] = doors[j] ^ 1

    offset += 1

    

for i in range(0, numDoors):

    message = "Door #" + str(i + 1) + " is "

    if (doors[i] == 1):

        message += "open."

    elif (doors[i] == 0):

        message += "closed."

    else:

        message += "this should not happen."

    print(message)

Given any nth door, knowing that we can exploit properties concerning n to tell if it is closed or not, we can ask the following related questions:

• How do we know how whether a given natural number is prime or not? This is a worthwhile question to ask because primality allows for an immediate answer (i.e. two).
• If it is composite, how do we actually compute how many divisors it has, apart from 1 and itself?

As a degree-holder, I know how to answer these, using university-level mathematics. As an educator, this takes an interesting turn.

Both of these are an excellent opportunity to introduce students to the state-of-art and the sheer cosmic scale of mathematics. Primality testing is one thing; prime factorization in particular is a different story. By yourself, as the numbers get bigger (1000 is rather small), the computations may not finish within your lifetime; even grown-ups are completely stumped over how to perform prime factorization efficiently in general. This is such a problem that grown-ups are exploring a completely new architecture of computing- quantum computing.

Furthermore, this can show students how entire civilizations can hinge on seemingly innocent properties in mathematics. For instance, the fine art of mathematically obfuscating your information to make it inaccessible, called cryptography, relies on seemingly simple questions, like prime factorization, being nigh impossible to answer quickly. This is some real life sorcery right here.