How did they come up with 159 million million possibilities in the Imitation Game?

There are no spoilers in this post. Also, before you even start there were multiple variations of the Enigma machine. This math is for the most common of those variations.

First of all, if you haven’t seen the movie, you should. Historical accuracy isn’t really much of a thing, but the basic truths are there and Benedict Cumberbatch is awesome as always even if his portrayal of the character strays a fair bit from the real life Alan Turing.

The movie made me a bit curious as to how the Enigma machine actually worked. Towards the beginning everyone stands around the table with the Enigma and impressively starts throwing out the number of possible combinations. So how did they come up with that? Well, first of all, in reality they probably didn’t do it on the spot because you can’t just glance at the thing and know exactly how it works unless you’re a clairvoyant. I’m going to focus a bit less on the mechanical operation of the enigma and more on the math of how to come up with it’s possible combinations. If you want to know more about how it mechanically works, there’s a nice post here.

From a math perspective you need to know that the enigma machine has four different properties that matter: which rotors (wheels) you pick, the order you place the rotors, the ring settings on the rotor, and the plugboard settings. We’ll go through them one at a time.

  1. Select the rotors you will use. There were five rotors and you had to choose three of them to operate the enigma machine. This means there are 5 choose 3 ways to select three wheels. The formula for choose is n!/[r!(n-r)!] which gives you 5!/[3!(5-3)!] = 10.
    • There’s a more in depth explanation for the below here.
    • Unfortunately, before I can explain the choose operation, I must explain permutations because you can’t understand choose without a permutation. While it sounds fancy, permutations are actually fairly straightforward. Let’s say I have a bag of 10 marbles and I tell you to pull three marbles from the bag and place them on the carpet in order. I said carpet because I don’t want them to roll in case you were wondering. How many ways can you draw the 3 marbles from the bag and place them in order? Well, when you first pull a marble out of the bag there are 10 marbles to choose from. On your second draw, there are 9 to choose from, then finally 8. This means there are 10 x 9 x 8 = 720 possible ways to select those three marbles. You can derive this from there are 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 ways to choose all 10 marbles. This is written as 10!. If you want to eliminate the choices you aren’t making, you divide by (#of choices – #total draws). This is written as n!/(n-r)! where n is the number of total choices and r is number you will pick from those total choices. So in our case we would have 10!/(10-3)! = 720.
    • Now let’s get back to the choose operation. Let’s also keep our 10 marbles in a bag scenario except this time I tell you I want you to select three from the bag without putting them back? The question is, how many possible combinations are there of the three marbles? Basically, the answer is the same as the permutation except that you don’t care about the order things are in. If you pick three marbles, there are 6 possible orders you could have those three things in. If order does not matter, any way that you select those three things still only counts as one combination. This means we take our n!/(n-r)! formula and reduce it by the number of possible orders, which gives you n!/[r!(n-r!)]. Check out the link at the beginning of this section for a more thorough explanation.
  2. So you can have 10 possible wheel combinations, but the order of those wheels also matters. Since you have three items you have 3 x 2 x 1 possible ways of ordering those items. Combine that with 10 possible ways to pick three wheels and you have 10 x 6 = 60 possible ways to select and then order the wheels.
  3. Each wheel could start in any one of 26 possible positions. You have three wheels each with 26 possibilities, which gives you 26^3 = 17,576.
  4. After the right hand rotor rotates 26 times it would kick the middle rotor. When the middle rotor rotated 26 times it would kick the left hand rotor. This would occur continuously throughout the course of encryption. The right hand rotor and the middle rotor also had ring settings to adjust the point at which this kick occurred. The position of the kick could be anywhere along the alphabet. Therefore there are 26 x 26 possible ring combinations.
  5. Finally, we must account for the plugboard. The plugboard contains a plug for each letter and has 10 wires which each connect two plugs. This means that 20 letters will be connected and 6 will not. Now here’s the hard part, how many ways can we plug 10 wires into 26 holes? Well let’s just do it in order. We pick up our first wire, how many ways can we plug it in? The answer is 26 choose 2. Now we pick up our second wire. We can plug it in 24 choose 2 ways. We continue in the way and end up with this number: C(26, 2) x C(24, 2) x C(22, 2) … x C(2, 2). If you write it all out, this ends up simplifying to 26!/(6! x 2^10). Here’s the issue though: that sequence assumes it matters which wire is plugged in where. In reality though all the wires are the same. It doesn’t matter if the first wire connects A and K or the second wire does it – the effect is the same. Therefore we must account for that in our equation by dividing by a further 10! to eliminate this. The end result is 26!/(6! x 2^10 x 10!).

Now we’re ready to put it all together.

-60 possible ways of selecting and ordering the three wheels.
-26^3 possible starting position combinations for each of the three wheels.
-26^2 ways to configure the kick location of the wheel.
-26!/(6! x 2^10 x 10!) possible plugboard combinations.

Now multiply it all together gives you: 1.0745868732725e+23.

So there you have it. That’s how they came up with the number in the movie. I don’t remember exactly what they said, 159 million million or something like that. If so, it’s actually 158 million million million.

2 thoughts on “How did they come up with 159 million million possibilities in the Imitation Game?

  1. Reply

    Daniël Willems

    Can you explain to me what the “!” means in “26!”.

  2. Reply

    Dustin

    It means 26 factorial so 26x25x24…x1

Leave a Reply