SGCG

Volver arriba

Demostración de un teorema en Futurama

2010-08-22

¡Atención! Este artículo desvela parte del argumento de una obra de ficción.

Vamos a hablar del décimo episodio de la temporada más reciente de la teleserie de animación Futurama (The Prisoner of Benda, emitido por primera vez el 19 de agosto de 2010). Este episodio es muy interesante porque incluye una demostración constructiva relacionada con las permutaciones cortesía del guionista y matemático Ken Keeler.

El argumento como problema matemático

Una disparatada máquina permite intercambiar mentes entre dos cuerpos, pero tiene un pequeño problema: una pareja de cuerpos sólo puede intercambiar mentes una vez. Esto lleva a toda clase de situaciones cómicas con numerosos intercambios de mentes. Al final del episodio, las matemáticas salvan el día: una demostración constructiva indica cómo lograr que todos los personajes vuelvan a residir en sus propios cuerpos con la ayuda de únicamente dos cuerpos auxiliares.

Matemáticamente, podemos modelar un conjunto de intercambios de mentes como un ciclo en el que cada transposición de elementos es equivalente a un intercambio de mentes entre dos cuerpos. Por simplicidad en la notación, asignemos un número natural a cada uno de los cuerpos. Llamemos π a tal ciclo. Sin pérdida de generalidad, supondremos que es como sigue:

π ≡	(	1	2	3	…	k−1	k	)
		2	3	4	…	k	1

La anterior notación indica que la mente que originalmente ocupaba el cuerpo 2 ahora está en el cuerpo 1, la mente que originalmente ocupaba el cuerpo 3 ahora está en el cuerpo 2, la mente que originalmente ocupaba el cuerpo 4 ahora está en el cuerpo 3, …, la mente que originalmente ocupaba el cuerpo k ahora está en el cuerpo k−1 y la mente que originalmente ocupaba el cuerpo 1 ahora está en el cuerpo k. Es decir, la primera fila indica el cuerpo y la segunda fila indica la mente.

La pregunta que debemos hacernos es ésta: ¿es posible (quizá haciendo uso de cuerpos nuevos) aplicar una permutación al ciclo π consistente únicamente en transposiciones diferentes de las que generaron π y tal que se obtenga un ciclo trivial, es decir, que todas las mentes acaben en sus respectivos cuerpos? Es decir, ¿existe una permutación inversa de π o de algún ciclo aumentado que contenga a π tal que las transposiciones que forman esa permutación son disjuntas de las transposiciones del ciclo de partida? ¿Y si hay varios ciclos independientes?

La demostración constructiva

Es posible resolver el problema y devolver cada mente a su cuerpo sin usar dos veces una misma pareja de cuerpos. La mejor forma de demostrarlo consiste en explicar un método para deshacer los intercambios de mente. La idea fundamental del método es la de usar dos cuerpos auxiliares que permitan almacenar de forma temporal las mentes al trasladarlas de vuelta a sus cuerpos originales. Como estos dos cuerpos auxiliares no han intercambiado mentes con los cuerpos del conjunto inicial, ofrecen posibilidades nuevas para mover las mentes.

Introducimos dos cuerpos nuevos, x e y. Aumentamos el ciclo π con los dos nuevos cuerpos para formar el ciclo π^*:

π* ≡	(	1	2	3	…	k−1	k	x	y	)
		2	3	4	…	k	1	x	y

Ahora sea <a,b> la transposición de los elementos a y b. Para cualquier i ∈ {1,…,k−1} definimos el conjunto de intercambios σ:

σ ≡ (<x,1> <x,2> … <x,i>) (<y,i+1> <y,i+2> … <y,k>) (<x,i+1>) (<y,1>)

Esta permutación está generada por transposiciones (parejas de cuerpos) diferentes de las que generaron π ya que x e y no estaban en el conjunto original de cuerpos.

Se comprueba fácilmente que σ deshace el ciclo π y deja intercambiados x e y:

π* σ =	(	1	2	3	…	k−1	k	x	y	)
		1	2	3	…	k−1	k	y	x

Si no hay un único ciclo sino varios, entonces podemos aplicar el mismo mecanismo a todos los ciclos. Al final, si x e y siguen intercambiados (es decir, el número inicial de ciclos independientes es impar), aplicamos el intercambio <x,y>.

Ejemplo

Ilustremos el proceso con un ejemplo práctico. Partamos de un caso sencillo en el que tres personas (1, 2 y 3) han intercambiado sus mentes de modo que 1 reside en el cuerpo de 3, 2 reside en el cuerpo de 1 y 3 reside en el cuerpo de 2. Podemos ilustrar los intercambios de mente necesarios para llegar a semejante situación en una tabla. La primera columna corresponde al cuerpo 1, la segunda columna corresponde al cuerpo 2 y la tercera columna corresponde al cuerpo 3. Cada fila corresponde a un paso en el proceso de intercambio de mentes. En cada celda aparece la mente que ocupa el cuerpo correspondiente a su columna en el paso correspondiente a su fila. Los cuerpos que intercambian mentes están indicados en cada paso con asteriscos y una tipografía diferenciada.

Intercambios de mentes iniciales.

1	2	3
2*	1*	3
2	3*	1*

Como no podemos hacer más de un intercambio de mentes entre dos cuerpos dados, ya no podemos devolver cada mente a su cuerpo. Afortunadamente, tenemos dos voluntarios, x e y. Ampliemos la tabla con ellos:

Intercambios de mentes iniciales con los dos nuevos voluntarios presentes.

1	2	3	x	y
2*	1*	3	x	y
2	3*	1*	x	y

Ahora podemos aplicar el método de la anterior sección:

Intercambios de mentes desde el principio hasta el final.

1	2	3	x	y
2*	1*	3	x	y
2	3*	1*	x	y
x*	3	1	2*	y
x	2*	1	3*	y
x	2	y*	3	1*
x	2	3*	y*	1
1*	2	3	y	x*
1	2	3	x*	y*

¡Conseguido! Hemos devuelto cada mente a su cuerpo original sin tener que hacer intercambios dos veces con una misma pareja de cuerpos.

---

Categorías: Matemáticas

Artículos publicados el mismo mes

Permalink: http://sgcg.es/articulos/2010/08/22/demostracion-de-un-teorema-en-futurama/

Volver arriba