100 Doors Puzzle: Analytical Solution
(16 August 2018)
This is a famous problem that sometimes gets asked in interviews for technical positions. A friend of mine posed it to me recently and I found a neat analytical solution. I haven't seen this solution anywhere so I am posting it here for fun. Any excuse to use the Riemann zeta function right?
The Puzzle
Before you is a set of doors. There are exactly 100 of these doors and they are all identical. To make it easier to visualise; imagine every door is numbered, 1 to 100. All of them are initially closed and they are all in a row (as pictured).
Toggle: In this context, toggling a door means changing its state to be the opposite of what it presently is. If it is open, you close it; if it is closed, you open it.
Starting at the first door, you proceed to toggle every door.
Counting from the first door, you go to every second door and toggle it. So you skip the first door, toggle the second door; skip the next door, toggle the fourth door etc.
Counting from the first door, you go to every third door and toggle it.
Counting from the first door, you go to every fourth door and toggle it.
You repeat this process until you end up skipping 99 doors and toggling the 100th door.
The Question
What is the state of every door in the set of 100? Which ones are open and which ones are closed? Ideally, I'd want an analytical solution where I give you a door number and you tell me whether it is open or closed after this process has been completed.
The Analytical Solution
Before I show you how I did it, it is worth taking some time and grappling with the problem. Try your hand at solving it before looking at my answer, which may bias your thinking.
Have you tried to find your own solution to the puzzle yet?
No really... try it! It's quite fun.
Mapping The Toggle
To begin with, we need some way to represent the door state and some operation which toggles it. Let the door state be b and the toggle operation be T.
The door is either open or closed. Hence, a binary variable can represent the door state exactly. We therefore need 100 bits of information for our answer, 1 bit for each door.
The usual way of representing a binary number is by using 0 and 1. I'm going to use -1 and 1 to represent my binary number, b, since I'm only interested in mapping the toggle operation; I do not intend to perform any other logical operations on the set of doors.
The toggle operation T, multiplies whatever the value of b is by -1. Observe that toggling twice should bring you back to the state you started with. With this definition, applying T twice multiplies the value of b by -1 and then again by -1 i.e. (-1) x (-1) = 1. The result is no change in initial state. So these definitions behave exactly like we want them to for the sake of the puzzle.
Edit 16 Aug: I've found a neater solution which allows you to count the total number of open doors. It uses modular arithmetic and is presented at the end of the article.
Partial Solution
We are in a position to write the partial analytical solution down already, the answer is that
where the subscript n, ranges from 1 to 100 and b_n represents the state of the door. The function d(n) is still to be determined. We are assuming the initial condition of every door is 1 i.e. 1 means closed and -1 means open.
Finding The Function
With a bit of thought, you should be able to see that you toggle any given door exactly the same number of times that it has integer divisors.
A prime number for example has exactly 2 integer divisors, 1 and itself. Hence, every prime number will be a closed door. Explicitly d(p) = 2 where p is a prime number.
A thought-sized example is door number 5. Initially it is closed. We start the process and toggle every door. So it is opened. Every second, third and fourth door skip over door number 5. Every fifth door toggles it (open to close) one final time. Done. Proof for all prime numbers is by induction.
Finding the number of integer divisors for an arbitrary integer can be done using a very clever trick called a Generating Function. This is a power series whose coefficients solve some important problem you are considering.
We will use the Riemann zeta function as our generating function. The definition of the Riemann zeta function is,
where s is a complex variable. For our purposes we do not care what the value of s is. We will not actually be trying to work out what value this series converges to, or if it does at all. We are only interested in the coefficients of the power series. Observe that the coefficient of every term in the Riemann zeta power series is 1.
Something quite spectacular happens when you square this power series, have a look
if you do a term by term multiplication you will see something wonderful. I highly encourage you to do this and see what I'm about to tell you for yourself.
You will observe is that,
and be happy to see that the coefficient of every term is exactly the number of integer divisors sought. The first few coefficients are 1,2,2,3,2,..
In other words,
and we have our function for the number of integer divisors neatly wrapped up in a bow.
General Solution: Any Number Of Doors
Finding a computationally efficient means to calculate the number of integer divisors for any n would mean that you could quickly tell whether a number was prime or not. You would do this by checking whether this explicit formula for d(n) equals to 2. I understand that hunting for prime numbers is a thing which (some) people like to do; so this is definitely not an easy undertaking!
For now, we at least have the analytical solution for the state of the door for any value of n where a well known power series has been used as a generating function to describe this analytical solution.
Neater Solution
The following solution uses conventional binary numbers 0 and 1 and modular arithmetic. Let 0 be a closed door and 1 be an open door.
Note that applying the toggle operation twice means that the door will return to its initial state as a result of the mod function. This is as it should be.
Since every door is initially closed, all doors are initialised to the value 0. The door state for any n is therefore given by,
where d(n) is still defined using the Riemann zeta generating function. You get this result by summing the number of toggles that each door undergoes, using the definition of the toggle operation and recalling that the initial state of every door is 0.
Again, every prime number has d(n) = 2 mod 2 = 0 and hence every prime numbered door is closed.
By using the conventional binary mapping, the total number of open doors can be found very simply; the total number is given by
and the total number of closed doors is given by
The exact door states for all 100 doors, using the above reasoning are:
1,0,0,1,0,0,0,0,1,0,
0,0,0,0,0,1,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,
0,0,0,0,0,1,0,0,0,0,
0,0,0,0,0,0,0,0,1,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,1.
We can clearly see that most doors are closed and that there only 10 doors open.
I hope you enjoyed this! I'd love to hear your thoughts if you have a neater solution or any comments on how I went about this.