Dan’s Geometrical Curiosities

Quite some time ago, I came across a riddle, and I’d like to share a variant of it with you:

100 prisoners are incarcerated in a very peculiar jail. The jail has a single room with a light controlled by a switch that is initially off. The prisoners are each told that they will be taken one at a time into this room, and will be allowed to flip the switch if they so desire. They will then be taken back to their room, and another prisoner will be brought to the room, given the same privilege, etc. While there is no specific reasoning whatsoever to the order in which the prisoners are sent to the room, there is only one known fact: the order doesn’t forbid any prisoner from entering the room after some time. That is, if the order were to continue indefinitely, no prisoner would enter the room for his or her last time (this happens almost surely anyway). If any one prisoner at any time correctly claims that every prisoner has been to the room at least once (by shouting “DONE!”), then all the prisoners are set free. If he or she is wrong, they all are killed. Before the prisoners begin to be led into the room, they are allotted a single planning session in order to discuss a strategy. Is there a certain escape strategy for the prisoners?

If you like riddles, think about this one for a while before reading ahead. Keep in mind that the exact time of unanimous entry need not be known, but when a prisoner shouts “DONE!” each prisoner must have visited the room at least once, 100% of the time, always. If you get bored with this one, try to solve the problem assuming you do not know the initial condition of the switch.Here is the strategy my friend and I came up with:

Each prisoner should flip a switch on the first time they notice the light to be off. After that (or if the light is already on), no action should be taken. Also, During the planning session, the prisoners also select a special individual to be the so-called counter. This person’s job is to keep a mental count of the number of times the light was on when the counter enters the room. After taking note of this, the counter turns the light back off. If the light is already off when entering the room, then no action is taken.

When the count reaches 99, he knows each of the other prisoners have been there at least once, so he can now shout “DONE!”. That is, only the counter is allowed to end the game in this case.

A new friend, Dana Albert, piqued my interest in analyzing this scenario more thoroughly. After all, there are some interesting questions that these prisoners would have about how long they’re going to have to stay there. For instance:

What are the chances we’ll get out of here in exactly n trips?

What is the average time I’ll have to stay here?

etc.

Let’s set up a formalism for solving this problem. Assign a name to each prisoner. Call the counter ‘C’, and call the rest of the prisoners by the names of the natural numbers, (i.e. 1,2,3,…,k-1), with k the number of prisoners. ‘C’ and all of these numbers will each be referred to as characters. Now we can talk about ways to describe the order in which people enter the switch-room by specifying the order on these names of the prisoners.

Call a string a random combination of the letter ‘C’ and the numbers {1,2,3,…,k-1}. This string represents a unique order of prisoners entering the switch-room by reading the sequence from left to right. Further, call a string “valid” if the game actually ends right at the end of the string.

 For instance, the following string with three prisoners

$$c12c2c$$

is a string signifying that the counter enters, then 1 enters, followed by 2, followed by another counter, 2 enters again, and finally a counter enters. This is also a valid string, because the second counter notices the switch flipped by 1, and the last counter notices the switch flipped by 2. Now the counter knows everyone has been in the room, so he can declare victory.

Here’s a question: how many valid strings are there of length n for various number of prisoners? To correctly analyze this, I’m going to devise the following counting strategy: a box around a character signifies that it is allowed to be used any number of times in a row. A box around more than one character signifies that those characters can be repeated in any order as many times as you like. These can even be used zero times if desired. For example

$$\fbox{2 c}1c\;\fbox{2}$$

means a collection of 2s and Cs followed by a 1C followed by some number of 2s. This way of writing a family of strings will be referred to as shorthand.

Now we are ready to figure out how many valid strings there are of a certain length. Let’s start with only two prisoners. What’s the shortest valid string? Well, 1 is the only character who needs to be clocked in by C, so obviously the answer is

$$1c.$$

Further, we can say that any longer valid string must have this same form, except with some other characters woven between. How could we uniquely write this using our formalism? We could write, by simply interlacing arbitrary strings between the shortest valid string above

$$\fbox{1 c}\:\color{blue}{1}\:\fbox{1 c}\color{blue}{c}\:\fbox{1 c}.$$

However, this is actually not correct. There are several issues. First, By adding the last \(\fbox{1 c}\) may add more characters beyond a point at which the string has already become valid. If we eliminate this mistake, then we have a valid string representation. However, the expression is not unique. For instance, consider the string \(c1\:\color{blue}{1}\;\color{blue}{c}\). This valid string can be obtained either by \((c1)\:\color{blue}{1}\:()\;\color{blue}{c}.\) OR by \((c)\:\color{blue}{1}\:(1)\;\color{blue}{c}\). (The parenthases represent that their contents originally came from the same box) If we want to avoid double-counting, then we must count these both as the same thing. How can we avoid this?

It sounds rather difficult to be able to keep track of when two boxings give rise to two identical strings, but there is an easy way around this. The problem is that the 1 in the above example is losing its identity; in the first case, the blue 1 was the second 1 to appear, and in the first case, it was the first to appear! We are counting as if the blue 1 is distinguishable from the regular 1, when really this is just a visual aide! Therefore, we must IMPOSE an order. We will say that the blue characters are required to be the first of their kind between blue characters. This way, we will never have the problem described above. With this in mind, let’s look again at the most general, unique representation of a valid string with two prisoners:

$$\fbox{c}\:\color{blue}{1}\:\fbox{1}\color{blue}{c}.$$

Now we can attempt to figure out how many valid strings of length n there are with two prisoners. There are n-2 characters coming from the boxes since two are used up as blue characters. The question reduces to asking how many ways there are to assign some of these n-2 visits to the first box and the rest of them to the second box. If I have j objects, I can split it into a left pile and a right pile in the following ways: (0,j),(1,j-1),(2,j-2)…(j-1,1),(j,0). Since we started at zero, there are actually j+1 ways to group them. That means there are \((n-2)+1\), or n-1 ways to have a string of length n. We will call the function \(f_{k}(n)\) that gives the number of valid length n strings with k prisoners the number function. Thus \(f_2(n)=n-1\).

We can do more. Every possible string of a fixed length n happens with equal probability (since each of the n choices happen with a specific number of choices), so the probability of any one of these occuring is \(\frac{1}{2^n}\). Then the probability of a string having exactly n characters is

$$\frac{f_2(n)}{2^n}=\frac{n-1}{2^n}.$$

If you want to compute the expected length of a string with 2 prisoners, you could take the following sum:

$$\sum_{n=2}^{\infty}\frac{n(n-1)}{2^n}=4.$$

I’ll get back to computing the expected lengths later with various prisoner numbers.

How about with three prisoners? What is the shorthand for this case, and what is the number function here? The shortest valid string here will be

$$\color{blue}{1}\color{blue}{c}\color{blue}{2}\color{blue}{c}.$$

using shorthand for an arbitrary extended case, and allowing, without loss of generality, the blue numerals to increase from smallest to largest we have

$$\fbox{c}\:\color{blue}{1}\fbox{1 2}\:\color{blue}{c}\fbox{c 1}\:\color{blue}{2}\fbox{1 2}\:\color{blue}{c}.$$

Using the shorthand notation above, let’s compute the number function for the case of three prisoners. This gets a little more complicated, so let’s use mathematics to help us and write the function as a sum. In the following equation, I have allowed the letters a, b, and c to represent the number of characters from each of the first, second and third boxes, respectively. We are then forced to take \(n-4-a-b-c\) characters from the fourth box in order to make sure the total number of characters is n. Also notice that we must introduce a k! (in this case 2!) to account for the fact that we are assuming that the digits are admitted in order from smallest to largest. 

$$f_3(n)=2!*\sum _{a=0}^{n-4}\; \sum _{b=0}^{n-4-a}\; \sum _{c=0}^{n-4-a-b} \left(1*2^b*2^c*2^{n-4-a-b-c}\right).$$

This isn’t as bad as it looks. The variables \(b\) and \(c\) cancel inside the summation, which simplifies matters substantially. When the dust settles, we are left with

$$f_3=\frac{2^n (n^2- 7 n +14 )}{8}-2.$$

Again, the expected length could be computed as

$$\sum_{n=4}^{\infty} \frac{f_3(n)}{3^n}=\frac{21}{2}.$$

It is remarkable how such a complex formula could result in such a simple, rational number. We’ll come back to this later.

For four prisoners, we can write down the shorthand as

$$\fbox{c}\:\color{blue}{1}\fbox{1 2 3}\:\color{blue}{c}\fbox{c 1}\:\color{blue}{2}\fbox{1 2 3}\:\color{blue}{c}\fbox{c 1 2}\:\color{blue}{3}\fbox{1 2 3}\:\color{blue}{c},$$

And the summation formula gets even nastier, but is also simplifyable:

$$f_4(n)=3!*\left( \sum _{a=0}^{n-6}\; \sum _{b=0}^{n-6-a}\; \sum _{c=0}^{n-6-a-b} \;\sum _{d=0}^{n-6-a-b-c} \;\sum _{e=0}^{n-6-a-b-c-d} \left(1*3^b*2^c*3^d*3^e*3^{n-6-a-b-c-d-e}\right)\right)$$

Which comes out to

$$f_4(n)=\frac{3^n \left(4\text{  }n^3-78 n^2+584 n-1725\right)}{648}+\frac{3(2^{n+3}-1)}{8}$$

This makes the probability graph look like

If you’re looking for a tedious exercise in mathematical manipulations, you can verify that the sum of these probabilities sum up to 100% over all allowable values of n. You can also try to work out these values of \(f_k(n)\) for higher values of \(k\). I warn you, though, the summations get more and more numerous, and beyond \(k=7\), I can no longer use Mathematica on my computer to compute \(f_k(n)\) in a reasonable amount of time.

So we’ve figured out how do deduce the probability that the prisoners are freed upon the \(n\)th person being let into the switch room. We could also easily compute the cumulative probability, that is, the probability that the prisoners are freed before the \(n\)th person is let into the room. But this is just more math and summations, so let’s move on to a more interesting topic. We also learned how to compute the expected number of times the prisoners would have to enter the switch room by taking the sum

$$\sum_{n=2k}^{\infty}n \frac{f_k(n)}{k^n}.$$

While I was discussing this with some friends, someone noticed that this question has been considered before here. Stuart Anderson posted a solution, but I could tell it was wrong (albeit is approximately the correct answer) because the answer he claimed yields a value less than two for two prisoners. Naturally the expected value cannot be less than the minimum number of tries possible! 

There are many properties of the expected value, and often it is possible to find it without knowing the probabilities explicitly. The following is an approach that my new friend Dana Alberts came up with that is good if all you want to find is the expected value.

First let’s discuss one of the linearity properties of the expected value. For two random variables \(X\) and \(Y\), we have \(E(X+Y)=E(X)+E(Y)\). This is best understood with an example. If you want to know the expected value of rolling two six-sided dice, one approach would be to compute all the individual probabilities of the possible numbers that would come up, and compute the expected value that way. However, this is very tedious, and there is another way. If we let \(X\) be the number on the first die, and \(Y\) be the number on the second die, then the expected value of \(X+Y\) is just the sum of the individual expected values, which is \(3+3=6\). We have found the expected value to be six without resorting to computing individual probabilities. This is the pivotal point of Dana’s argument. Another thing we must know is that if an event happens consistently with probability p (e.g. the probability of a heads in a coin toss), then if we repeat the measurement, we can expect to get the event in an average of p tries.  

It goes like this: initially, we need some numeral to enter the room to get the switch flipped. This happens with (k-1)/k probability (since we don’t need the counter to enter yet). We wait for this numeral to enter. This should take an average of k/(k-1) tries. Now we require that eventually a counter enter, to “lock in” the switch-flip that our first numeral just made. This happens with 1/k probability, since the counter is one out of k prisoners, so we can expect it to happen in an average of k tries. Next, we require that one of the numerals who has not yet flipped the switch enter the room. This happens with probability (k-2)/k, so this happens on average in k/(k-2) tries. This pattern repeats, and we want to sum the expected times for each switch-flip to get locked in, so this comes out to be

$$k(k-1)+\sum_{i=1}^{k-1}\frac{n}{i},$$

Which gives \(10417.7\) for \(k=100\).

This formula is incredibly simple, and it is remarkable that such a simple formula could also emerge from the heinous summations above.

Hopefully we don’t have to ever find ourselves in a position of frantically figuring out a strategy to flip switches in a dark jail.