The Locker Problems Solved

imageA few days ago, I posted a couple of problems that I had stumbled across over at Math Jokes for Mathy Folks.  If you haven’t already, take a moment to read the puzzles:  The Locker Problems.

Problem 1

To start with, we can simply begin walking through process by hand.  Locker 1 will begin closed, then the 1st person will come in an open it.  After that, no one touches the 1st locker so we know it stays open.

Locker 2 is opened by the 1st person, closed by the 2nd and it stays closed.  Locker 3 is opened by the 1st person, left alone by the 2nd and then closed by the 3rd.  This is going to get tedious if I keep explaining in words.  Lets use a table.  If a locker is open, I’ll put a “o”, if it’s closed I’ll put a “c”.

 

image

This is also going to get tedious if I want to do this for 1000 lockers and 1000 students.  We definitely need to find a pattern. 

My next step was put together a lazy little Matlab script to do the same exact thing as my table. (See here.)  Using the “spy” function in MATLAB allows me to see the sparsity pattern of the matrix.  The open lockers are represented by 1’s and the closed ones by 0’s.  Here’s what it looks like for 100 lockers and 100 students.

image

There is definitely a pattern!  Notice those open lockers form the bands you see in the picture.  So why do some end up open and some end up closed?

The easiest way to see why is to consider what happens to a single locker.  For example, think about locker 24.  When does it change state?  Obviously, person 1 opens the locker, person 2 closes it, person 3 opens it, person 4 closes, person 5 does nothing, etc.  Notice that if the locker number, 24, is divisible by the person number, then the state changes:

image

The number 24 has 8 factors, that is, 8 numbers that divide evenly into it.  So the key is that any locker number with an even number of factors will end up with closed and any with an odd number will end up open. So what numbers have an odd number of factors?

At first thought, it seems that all numbers should have an even number of divisors since they always occur in pairs: 

24 = 1 x 24
24 = 2 x 12
24 = 3 x 8
24 = 4 x 6

Consider a number like 36, though.

36 = 1 x 36
36 = 2 x 18
36 = 3 x 12
36 = 4 x 9
36 = 6 x 6 <—- Ah ha!!

Perfect squares are the only numbers that can have an odd number of divisors.  So locker numbers which are perfect squares (i.e., 1, 4, 9, 16, 25, …) will remain open while the rest stay closed!! That matches exactly with the table above and the graph from MATLAB.

All we need to know is how many perfect squares are less than 1000. 

\sqrt{1000} \approx 31.6222

ANSWER:  There will be 31 open lockers

Problem 2

In the second version of the problem, we have only 30 students and some are absent.  In fact, we need to determine which ones were absent so that all the lockers except the first on remain closed.

Starting in a similar fashion as before, we could build a table by hand and determine who would have to be sick.  For example, the 1st student is clearly present since the first locker remains open.  After that, the 2nd and 3rd are both present since those lockers end up closed.  The 4th person must be absent since if they were present then the 4th locker would be open. 

So any locker number that has an odd number of factors (only counting factors if that person is present) must not be there.  For example, consider the 8th locker.  The number 8 has 4 factors but one of them is 4 so it actually only has 3 factors when counting those present.  So 8 must be out sick. 

Following this pattern, we eliminate all multiples of 4.  Then when we get to the 9th locker, they will also absent.  So will all multiples of 9.  Continue this pattern until you reach 30.

image

The numbers that are not shaded are called squarefree since they have no repeated factors when you they are prime factored.  (Read more about squarefree numbers.) The absent folk are the "non-squarefree” numbers, also known as squareful.

ANSWER: There are 11 squareful numbers less than 30 so 11 students are absent.

That was fun!

10 thoughts on “The Locker Problems Solved

  1. Appropriate for what grade level? I know fellow college freshmen that were stumped. Should my 6th grade brother be seeing this in his homework?

    “Preparing America’s students for success.” …

  2. Maybe appropriate for the middle school math team, but not for 6th grade homework .
    There are other ways to teach kids common factorization .
    Got it for homework as well…

Leave a Reply