Mind swapping problem from Futurama S06E10

In episode 10 of season 6 of Futurama, titled The Prisoner of Benda, Professor Farnsworth built a machine that allowed two bodies to switch minds. After experimenting it with Amy, they realised that the machine cannot be used to switch back two minds that have already performed a switch with each other. In the attempt to return to their original bodies, the other crew members performed switches with one another as well, resulting in everybody having a different mind.

Ken Keeler, who wrote the episode and has a PhD in Mathematics, created a theorem and proof with respect to the following problem:

Suppose there are k bodies and distinct mind switches are performed on these bodies. The condition of the switch is such that, if two bodies have performed mind-switching before, they cannot repeat this process with each other. How can we then restore the bodies with their original minds without violating the condition stated?

The proof of this theorem is written in the following screenshot, which we will further elaborate:


In the process of explaining the solution, we will translate it into a Python program. Firstly, we let the array A contain k Body objects, where the index of each Body object will correspond to its mind_id attribute.

The transcribed first part of the proof is as follows:

First let π be some k-cycle on [n] = {1 ... n} WLOG write:
π = 1  2  ...  k  k+1  ...  n
    2  3  ...  1  k+1  ...  n

Let <a,b> represent the transposition that switches the contents of a and b.
By hypothesis π is generated by DISTINCT switches on [n].

We have k bodies that are messed up. From the above diagram, the first row represents the body id, while the second row represents the mind id. We then arrange them such that each body will be to the right of the body that possesses its mind, i.e. body 2 will be on the right of body 1 as body 1 contains the mind of body 2, so on and so forth. There is an exception for bodies 1 and k, where the right of body k is body 1, so that the k bodies are arranged in a circle.

We define the Body class as follows:

class Body(object):
    def __init__(self, mind):
        self.mind = mind
        self.has_switched_with = []

    def can_switch_with(self, other_body):
        if other_body in self.has_switched_with: 
            return False
        else: 
            return True
    def switching(self, other_mind, other_body):
        self.mind = other_mind
        self.has_switched_with.append(other_body)

The attribute

self.has_switched_with

stores the body ids of other bodies it has performed a switch with, so that it may perform a check in the method

can_switch_with

to ensure that it has not already switched with the body it is currently trying to switch minds with. This should be an invariant throughout the entire proof, i.e.

self.has_switched_with

should always return True.

The following code will obtain a user input for the number of bodies which will be passed as an argument into the program.

bodies = []
size = int(sys.argv[1])

# Assume distinct switches are already performed on bodies

for i in range(size): 
    body = Body((i+1)%size) 
    body.has_switched_with.extend(range(size)) 
    bodies.append(body) 
    print str(i) + '\t', 
print '\n',
for body in bodies: 
    print str(body.mind) + '\t', 
print '\n'

First, we initialise the array of bodies such that each body has a mind id equal to the next body's body id, except for the last body which will have the mind id equivalent to the 1st body id. This corresponds to the arrangement of the k bodies in a circle. The line

body.has_switched_with.extend(range(size))

assumes that each body has switched with every other body. (The body will include itself in the array according to the code, but it isn't necessary to remove it as it will never perform switching with itself.)

Transcribing the next part we have:

Introduce two "new bodies" {x,y} and write

π* = 1  2  ...  k  k+1  ...  n  x  y
     2  3  ...  1  k+1  ...  n  x  y

Now we introduce two bodies that haven't been mind-swapped and initialise them with mind_ids corresponding to their body_ids:

# Introduce 2 bodies that haven't been mind-swapped
body_x = Body(size)
body_x_index = size
body_y = Body(size+1)
body_y_index = size+1
bodies.append(body_x)
bodies.append(body_y)

for i in range(len(bodies)): 
    print str(i) + '\t',
print '\n',
for body in bodies: 
    print str(body.mind) + '\t',
print '\n'

And the last part:

For any i=1 ... k let σ be the (l-to-r) series of switches

σ = (<x,1> <x,2> ... <x,i>) (<y,i+1> <y,i+2> ... <y,k>) (<x,i+1>) (<y,1>)

Note each switch exchanges an element of [n] with one of {x,y} 
so they are all distinct from the switches within [n] that generated π 
and also from <x,y>. By routine verification

π* σ = 1  2  ...  n  x  y
       1  2  ...  n  y  x

i.e. σ reverts the k-cycle and leaves x and y switched 
(without performing <x,y>).

NOW let π be an ARBITRARY permutation on [n]. It consists of disjoint 
(nontrivial) cycles and each can be inverted as above in sequence after 
which x and y can be switched if necessary via , as was desired.

Next, we pick a random body with index i

# Pick any k from 0 to size-1
k = random.randrange(size)
print 'k = ' + str(k)

and do the following:

First, from the first body to the ith body, we perform switches with body X.

# Swap minds of start to index k with body_x
for i in xrange(k+1): 
    if not switch(body_x_index, i): 
    print 'Error!' 
    break

Next, from the i+1th body to the last body, we perform switches with body Y.

# Swap the rest of the minds with body_y
for j in xrange(k+1, size): 
    if not switch(body_y_index, j):
    print 'Error!'
    break

Now each body possesses its own mind except for index 0 and k+1 (and of course bodies X and Y). Body 0 has its mind in body Y and body k+1 has its mind in body X. Hence we do the following:

# Swap body_x's mind with the k+1th body
if k+1 < size: 
    if not switch(body_x_index, k+1): 
    print 'Error!'

# Swap body_y's mind with the 0th body
if not switch(body_y_index, 0): 
    print 'Error!'

Voila! Now all the bodies, except for X and Y, possess their original minds. And it perfectly fine that X and Y are swapped, because they can simply perform a pairwise switch between themselves and get back their own bodies.