Answer: Tuesday Teaser #25
Apologies for how tough this teaser was. It relies on an extremely cunning trick.
Bourbaki’s strategy relies on looking at all the possible ways in which the names can be arranged in the boxes (the permutations).
He starts by giving each person a number from 1-6 and labelling each of the boxes 1-6, such that each person has a corresponding box. The exact order does not matter here, so let’s suppose they’re labelled in order:
- Alfred Dreyfus
- Jean Calas
- Emile Outreau
- Jeanne d’Arc
- François Outreau
- Nicolas Bourbaki
If you’re not familiar with permutations, here’s a very quick primer which we’ll need in order to understand the trick. These gives us a way of representing the arrangements by writing them in terms of the cycles they contain.
For example, if 1’s name is in box 2 and 2’s name is in box 1, that would give us a cycle of size 2. If 3’s name was in box 3, then it already matches, so that would give us a cycle of size 1. If 4’s name was in box 5, 5’s name was in box 6 and 6’s name was in box 4, that would give us a cycle of size 3. We’d then write that permutation with it’s separate cycles as follows: (1 2)(3)(4 5 6).
Other example permutations might be (1)(2)(3)(4)(5)(6), where all the names are in the correct boxes, or (1 2 3 4 5 6), where each name is “one box away” from the correct box [1’s name is is box 2, and so forth].
Now suppose Bourbaki’s strategy is as follows: Each person will go into the room and open their assigned box. If their name is there, then they’ve achieved their goal. If not, they will open the box that corresponds to the name they found inside the box. Having opened the second box, they use the same method to determine which box to open on their third attempt.
If we consider the possible arrangements, it turns out a large number of them will mean that this strategy is successful. If the arrangement is such that all the cycles are of length 3 or less, everybody will get back to their own name within 3 turns. If you are unsure as to whether or not this is true, take a minute to jot down a few examples, which should help to illustrate why it is true.
Equally, it is clear that if there is a cycle of length 4 or greater, at least one of the people will fail to find their name in three turns with this strategy. So the strategy will win if and only if the names are arranged such that all the cycles are of length 3 or less.
Now it is simply a case of counting the cycles to compute the probability. There are 6! = 6*5*4*3*2*1 = 720 possible permutations in total. Those of which that have at least one cycle of length 4 or greater are the following types:
- One 6-cycle
- One 5-cycle and one 1-cycle
- One 4-cycle and either two 1-cycles or one 2-cycle
The maths here gets a little tricky, but there is a formula which will help us count these numbers. We know each of the above permutations have only a single cycle of length 4 or greater. So :
For a given k (where k is 4 or greater, as above), there are n!/(n-k)! ways to choose the elements of the k-cycle [this is a standard combinatorics formula which shows how many ways to choose k things from n things], (k-1)! ways to order those elements within the cycle and (n-k)! ways to order the remaining elements. This gives:
n!/(n-k)! * (k-1)! * (n-k)! = (n)!/k permutations.
So for the three possibilities previously mentioned:
One 6-cycle: This leaves us with (6!)/6 = 120 such permutations.
One 5-cycle and one 1-cycle: This leaves us with (6!)/5 = 144 such permutations.
One 4-cycle and either two 1-cycles or one 2-cycle: This leaves us with (6!)/4 = 180 such permutations.
So the strategy will fail a total of 444 times out of 720, but incredibly it will work 276 times out of 720, leaving a seemingly impossible 38.3% chance of release.
