Futurama theorem

[hurrycane]

I recently watched a pretty neat youtube video about a theorem that one of the writers of Futurama made up for one of their episodes

 

https://youtu.be/J65GNFfL94c

 

The professor has invented this mind switching chair that lets two people who sit on it switch their minds. But once two bodies have sat on the chair the same two bodies cannot switch minds a second time. In the episode the characters end up with their minds all over the place. They bring in two extra mathematician/basketball player characters who prove that they can sort out any mess using their two bodies as storage space (the Futurama theorem). Here are a few problems which I think would be fun to puzzle out.

 

Which n-person mind mess requires the maximum number of switches when we apply the algorithm in the theorem?

 

Is the algorithm that the theorem is about always best possible in terms of the number of switches required to sort out any mind mess, if all switches in the sorting out process involve at least one of the extra two players (as in the Futurama theorem algorithm)?

 

Any other good questions?

 

 

[conway]

good episode!