My friend gave me the following riddle over drinks. At the time, I was more interested in my drink than the riddle, so I asked him for the answer. It was interesting enough, though, for me to spend an hour proving that answer to myself the next day.
There are one-hundred doors labeled 1 through 100. The doors are in order. There are also one-hundred people labeled 1 through 100. The people are not necessarily in order, and are lined up before door 1. The doors all start closed.
Each person in line goes to every \(n\)th door and opens it if it's closed and closes it if it's open, where \(n\) is the person's label. For example, the person labeled 4 would visit every fourth door starting with door 4 and switch it from open to closed or vice versa.
After all one-hundred people go, which doors are open?
What follows is the solution to the riddle that was rigorous enough for me to feel comfortable about it. I think it hits the sweet spot of being nowhere near rigorous enough for real mathematicians, yet also inaccessible to people who aren't familiar with undergrad-level math and proofs. Let's begin.
It helps to start by looking at the problem from a pure-math perspective. Reframe it with math-y terms.
To start, let's just use the word "toggle" to mean "closing an open door or opening a closed door". That's what the people do. They toggle the doors.
Next, note that it doesn't matter what order the people go in. If person 3 toggles door 3 and then person 1 toggles door 3, the door has been "toggled" twice. Same thing if you switch person 1 and 3. Either way, the door has been toggled twice and ends up in the same state as when it started. We can even take this further. If the door gets toggled an even number of times, it will be in the same state as when it started. If it's toggled an odd number of times, it will be in a different state. We're looking for all the doors that end up open. So we're actually looking for all the doors that were toggled an odd number of times. There; that's much more math-y.
Next, note that person \(j\) will only "toggle" (close an open door or open a closed door) doors that are a multiple of \(j\). Take person 3 for example. Person 3 will go to door 3, then door 6, then 9, and so on. These are the multiples of 3. I could prove this for The Rigor, but I don't want to. That would just be more words that no one needs.
Let's look at this from a single door's perspective. If person \(j\) opens the doors that are a multiple of \(j\), then any door that gets opened by person \(j\) has \(j\) as a factor. Let's call the door \(k\). We can then say that a door \(k\) is toggled by every person \(j\) where \(j\) is a factor of \(k\).
This leads us to the first big finding. Since there's a person representing every integer less than or equal to the number on every door, all we have to do to find the number of times door \(k\) is toggled is find the number of factors of \(k\). Let's call this number \(F_k\). Actually, we don't even have to find \(F_k\). We just have to find whether \(F_k\) is even or odd for any \(k\).
It's very often helpful to know what you're trying to prove before you prove it. We don't know the answer, but we can probably take a guess at it if we try a few different doors with small numbers and then try to find a pattern. Once we have that pattern, we can try to more formally prove it for any door.
We've done enough cases to maybe see a pattern. It doesn't have anything to do with prime numbers, though that was my first thought. Doors 5 and 7 are both toggled an even number of times, but so are doors 6 and 8. That's not really a pattern.
However, if you look at the lists of numbers in each category, it's easier to see.
The odds are all perfect squares. So let's run with this and try to prove it formally. Also, I won't pretend that I got this answer on my own. It was given to me. I just think this is a reasonable way that I could have approached it.
Let's first state what we're trying to prove. This blog doesn't have a "Theorem" environment like LaTeX (yet!), so I'll use a Markdown quote.
Any door with a square label will be toggled an odd number of times. Any door with a non-square label will be toggled an even number of times.
I tried a few different approaches to this proof, and eventually settled on a doing a lesser proof first because it was easier. Let's just prove that all the square doors have an odd number of factors (toggles).
Since we're talking about factors and integers, it will probably be helpful to think about the prime factorization of integers. There's probably a proof of this somewhere, but I'll just state it: every positive integer has a prime factorization. A prime factorization is just list of prime numbers (repetition is allowed) that all multiply together to get the original number. More formally, for some integers \(k \in \mathbb{N} \) (the natural numbers, i.e. \(1, 2, 3, \ldots\)), we can say the following.
\[ k = p_1^{\alpha_1} p_2^{\alpha_2} \cdots = \prod_i p_i^{\alpha_i} \]
In that equation, every \(p\) is a prime number and every \(\alpha\) is a positive integer (member of \(\mathbb N\)). As an example, take the number 12. The prime factors of 12 are 2, 2, and 3. So its prime factor representatio would be:
\[ 12 = 2^{2} \cdot 3^{1} . \]
How does this "prime factor representation" help us? Well, it just so happens that the total number of factors (not just prime factors) can be counted using the values of \(\alpha\) in the prime factor representation. Think about it. Every factor of \(k\) can be built using some combination of the prime factors. In order to generate every factor of \(k\), you just have to find every possible combination of the powers (\(\alpha\) values) of the prime factors such that the powers are less than their value in the representation of \(k\). So, for \(\alpha_1\), you would use all possible powers of \(p_1\) from 0 to \(p_1\) (note that this adds up to \(\alpha_1 + 1\) possibilities).
Let's look at an example just to help prove this to ourselves. Take 12 again. The factors are 1, 2, 3, 4, 6, and 12. The prime factor representation is shown above. The different possible values for the \((\alpha_1, \alpha_2)\) pairs are:
Tada! We generated all the factors of twelve with this method. Each factor \(\alpha_i\) varies from zero to \(\alpha_i\). Again, that means there are \(1 + \alpha_i\) possibilities for each \(\alpha_i\). In combinatorics (the math of counting things), there's a law (and probably a formal proof somewhere) that says if you have \(A\) ways of doing one thing and \(B\) ways of doing another thing, you have \(A \cdot B\) ways of doing both together.
So, if we have \(1 + \alpha_i\) ways of choosing the power for each \(\alpha_i\), then we have
\[ (1 + \alpha_1)(1 + \alpha_2) \cdots (1 + \alpha_i) \equiv \prod_i (1 + \alpha_i) \]
combinations of powers, each one representing a different factor of the original number \(k\). Thus, again defining \(F_k\) to be the total number of factors of \(k\), we can say \[ F_k = \prod_i (1 + \alpha_i). \]
Cool! We found an expression for the number of factors. While we don't necessarily know anything about the \(\alpha_i\) values (yet!), this is still progress.
Before we move further, though, let's do a sanity check for the equation we just derived. For the 12 example, we had \(\alpha_1 = 2\) and \(\alpha_2 = 1\). This would lead us to believe that we had \( (1 + 2) \cdot (1 + 1) = 6 \) possible factors, which is right! Nice.
So what do we do with our fancy new expression for \(F_n\)? Well, let's try throwing a random piece of information at it and seeing what happens. It worked for me.
Let's say that our \(k\) is a square number. We're allowed to do this because we're proving the implication \[k \text{ is square} \implies F_k \text{ is odd}.\] We're allowed to assume whatever is on the left side of the implication. Think of it like saying "if \(k\) is square, then \(F_k\) is odd".
So if \(k\) is square, then some other integer \(l\) squared is equal to \(k\). That's what it means to be a square integer. More succinctly, \(k = l^{2}, l \in \mathbb N\). What can we do with this? Well, let's write the prime factor representation of \(l\) just for fun. We'll use \(\beta_i\) to represent the powers in \(l\)'s representation. We can still use \(p\) for the prime numbers since integers and their squares share the same "base" prime numbers. Think about it. They do. Now we have
\[ l = \prod_i p_i^{\beta_i}. \]
We also know that \( k = l^{2} \), so
\[ k = \left[\prod_i p_i^{\beta_i}\right]^{2} = \prod_i p_i^{2\beta_i}. \]
Interesting. Let's use our counting method in terms of the \(\beta\) powers.
\[ F_k = \prod_i (1 + 2\beta_i ) \]
Wait a second. We know that every \(\beta_i\) is an integer. We also know that every \(2\beta_i\) is an even integer (because it has an explicit factor of 2 right there), and that every \(1 + 2\beta_i\) is an odd integer because it's an even integer plus one. So \(F_k\) is actually the product of some number of odd integers, which means that it has to be odd. For something to be even, it has to have a factor of two. Multiplying a bunch of numbers without a factor of two leaves you with a larger number still without a factor of two.
That's it! We did it! We started by saying that \(k\) was a square integer, and ended up with the implication that \(F_k\) is odd. We're completely done!
We have successfully proven one half of what we needed. We now know that if \[k \text{ is square} \implies F_k \text{ is odd}\], i.e. doors that have square numbers are toggled/flipped/switched an odd number of times.
However, we also need to prove that doors that are not square are toggled an even number of times. More formally, we have to prove the implication \[k \text{ is not square} \implies F_k \text{ is even}.\] This seems harder to prove. After some thought, I decided it would probably be easier to prove the contrapositive of this statement, which is \[F_k \text{ is odd} \implies k \text{ is square}.\] You may notice that this is actually just proving the other side of a biconditional, or an "if and only if" statement. The full statement we're proving now is: \[k \text{ is square} \iff F_k \text{ is odd}.\] That biconditional says that the doors which are square are flipped an odd number of times, and only those doors. No other doors are flipped an odd number of times. We already proved right-to-left in the sections above, so now we're going to prove left-to-right.
To be clear, we're trying to prove \[F_k \text{ is odd} \implies k \text{ is square}.\] Huh. This seems mildly similar to the previous proof. What if we just do it... backwards?
We can start by saying that \(F_k\) is odd. Let's, uh... write down the equation that relates \(F_k\) and its prime factor powers \(\alpha_k\). Because we have it and I don't know what else to do. \[ F_k = \prod_i (1 + \alpha_i ) \] Well... we know that \(F_k\) is odd, because we started with that assumption. So we also know that each of the factors \(1 + \alpha_i\) also has to be odd. If one of them were even, \(F_k\) would have a factor of two, and would therefore not be odd.
Since each of the factors \(1 + \alpha_i\) is odd, we know that each \(\alpha_i\) is even. Because of the 1. You get it. So each \(\alpha_i\) is even, and can therefore be written as 2 times some other integer, which we'll call... \(\beta_i\). For symmetry. Now we have
\[ \alpha_i = 2 \beta_i \quad \text{for each } i,\]
where \(\beta_i\) is some integer.
Ok. So what do we know about \(k\)? Well, we know that \(k\) is some integer, and therefor has a... wait for it... prime factor representation! Let's write it down.
\[ k = \prod_i p_i^{\alpha_i} \]
But we already figured out that each \(\alpha_i\) can be written as \(2 \beta_i\). So let's use that fact.
\[ k = \prod_i p_i^{2 \beta_i} \]
Now let's do some algebra.
\[ k = \left[ \prod_i p_i^{\beta_i} \right]^{2} \]
Except... the expression inside the square brackets itself represents an integer. It's a bunch of prime numbers raised to integer powers all multiplied together. That's an integer. Let's call it, I don't know... \(l\). For symmetry.
Tada! We just proved that \(k\) is actually just the square of some other integer \(l\). Now we're actually done.
In the end, we really just needed to prove \[k \text{ is square} \iff F_k \text{ is odd}.\]
We started by proving \[k \text{ is square} \implies F_k \text{ is odd},\] and then finished by proving \[F_k \text{ is odd} \implies k \text{ is square}\]