Normalmente elegimos un inicio, realizamos los movimientos y descubrimos qué ocurre. Aquí cambia la pregunta: ¿qué inicio debemos preparar para obtener exactamente el resultado deseado? En estos dos problemas, las operaciones inversas se convierten en una forma concreta de razonar.
Abrir el laboratorio: cartas y Josephus, hacia delante y hacia atrás
Dos aplicaciones para probar con amigos:
Empezar por el final
Un algoritmo hacia atrás no es una serie de intentos al azar. Partimos de un estado final deseado y deshacemos las operaciones en orden inverso. El resultado de la última acción normal se convierte en el inicio de la primera acción inversa. Hay que saber qué información conservar: aquí guardamos las cartas sobre la mesa y distinguimos a quienes deben permanecer de quienes deben salir.
Problema 1: la baraja
Tienes 10 cartas numeradas del 1 al 10. ¿Cómo debes colocarlas para que, repitiendo los siguientes movimientos, salgan sobre la mesa en el orden 1, 2, 3, 4, 5, 6, 7, 8, 9, 10?
- Tomo la carta de abajo de la baraja.
- La pongo encima de la baraja.
- Tomo la carta de abajo de la baraja.
- La pongo descubierta sobre la mesa, encima de las anteriores.
El orden de salida es cronológico: primero 1, luego 2, hasta 10. En la pila final sobre la mesa, en cambio, 10 está arriba y 1 abajo. No debemos confundir estas lecturas.
El vídeo de las cartas al revés
Imaginemos que rebobinamos el vídeo. La mano está vacía y la pila final está sobre la mesa. Recuperamos primero el 10, luego el 9 y así sucesivamente. Invertimos tanto el sentido de cada traslado como el orden de las cuatro acciones:
- Tomo la carta de arriba de la pila sobre la mesa.
- La pongo debajo de la baraja en la mano.
- Tomo la carta de arriba de la baraja en la mano.
- La pongo debajo de la baraja en la mano.
Las dos primeras acciones deshacen la salida sobre la mesa; las dos últimas deshacen el traslado de abajo arriba. Incluso cuando solo hay una carta en la mano, el principio sigue siendo el mismo.
Tras cada grupo de cuatro acciones inversas, la baraja en la mano crece una carta. Leemos siempre de arriba abajo:
| Carta recuperada de la mesa | Baraja tras la ronda inversa, de arriba abajo |
|---|---|
| 10 | 10 |
| 9 | 9, 10 |
| 8 | 10, 8, 9 |
| 7 | 8, 9, 7, 10 |
| 6 | 9, 7, 10, 6, 8 |
| 5 | 7, 10, 6, 8, 5, 9 |
| 4 | 10, 6, 8, 5, 9, 4, 7 |
| 3 | 6, 8, 5, 9, 4, 7, 3, 10 |
| 2 | 8, 5, 9, 4, 7, 3, 10, 2, 6 |
| 1 | 5, 9, 4, 7, 3, 10, 2, 6, 1, 8 |
Disposición inicial, de arriba abajo:
5, 9, 4, 7, 3, 10, 2, 6, 1, 8
La misma disposición, leída de abajo arriba:
8, 1, 6, 2, 10, 3, 7, 4, 9, 5
Al jugar normalmente con esta baraja salen exactamente los números del 1 al 10. En el laboratorio se comprueba carta a carta; también puedes cambiar N o elegir otro orden de salida.
Una comparación: simulación y permutación
Podemos obtener la misma baraja sin deshacer directamente los movimientos. Etiquetamos las posiciones iniciales del 1 al 10, contando desde abajo. Simulamos el juego normal y registramos el orden cronológico de salida de esas etiquetas:
2, 4, 6, 8, 10, 3, 7, 1, 9, 5
A la primera posición que sale le asignamos el valor 1; a la segunda, el 2, y así sucesivamente. La tabla mantiene siempre el mismo sentido de lectura:
| Etiqueta de la posición que sale (desde abajo) | Valor asignado |
|---|---|
| 2 | 1 |
| 4 | 2 |
| 6 | 3 |
| 8 | 4 |
| 10 | 5 |
| 3 | 6 |
| 7 | 7 |
| 1 | 8 |
| 9 | 9 |
| 5 | 10 |
Al ordenar las etiquetas del 1 al 10 recuperamos la disposición de abajo arriba. Ambos métodos coinciden: la simulación observa la permutación de posiciones; la reconstrucción inversa deshace los traslados.
Problema 2: el círculo de Josephus
Disponemos N personas en círculo. Contamos hasta K, eliminamos a la K-ésima persona y volvemos a empezar con la siguiente. Queremos que queden V personas del grupo de ganadores después de P eliminaciones. ¿Cómo construimos la disposición inicial? No elegimos sus puestos de antemano: debemos descubrirlos mediante la reconstrucción.
En el juego de eliminación, el puesto 1 es el origen del recuento: quien está allí cuenta 1, la siguiente persona 2 y así hasta K. Después de cada eliminación, la siguiente persona vuelve a contar desde 1. Los puestos de la disposición completa se numeran en sentido horario; el juego sigue el sentido elegido. En los ejemplos principales se cuenta en sentido horario.
El puesto 1 es donde empieza el recuento para eliminar. No está ocupado necesariamente por la persona identificada con el número 1 y no es necesariamente ganador.
El juego muestra la simulación hacia delante. El nuevo laboratorio reconstruye la disposición hacia atrás y permite comprobarla también en ese juego.
Abrir el juego de Josephus existente
Reconstruir Josephus, movimiento a movimiento
El algoritmo solo conoce cuántos ganadores y perdedores hay y cada cuántos recuentos se elimina. Al principio reúne a todos los ganadores, uno detrás de otro. No tiene en cuenta posiciones anteriores ni les asigna todavía puestos finales. Para seguir el procedimiento numeramos a las personas: de 1 a V son ganadores; de V + 1 a N son perdedores.
- Colocamos en fila solo a los V ganadores, numerados 1, 2, …, V. Están juntos: todavía no son puestos numerados del juego.
- Tomamos al primer perdedor, con número V + 1, y lo ponemos en la cabeza de la fila.
- Repetimos K − 1 veces la misma pareja de operaciones: tomar el último número de la cola y ponerlo en la cabeza.
- Tomamos al siguiente perdedor y repetimos la inserción y los movimientos. Continuamos uno a uno hasta insertar a los P perdedores.
- Solo al final leemos la disposición completa desde la cabeza, asignamos los puestos 1, 2, …, N e identificamos los ocupados por ganadores. El recuento de eliminación empezará en el puesto 1.
El procedimiento utiliza exactamente K − 1 movimientos por inserción, como el bucle del programa. Por ejemplo, con K = 3: insertamos un perdedor en la cabeza y hacemos dos veces «tomar de la cola y poner en la cabeza». Con K = 1 solo insertamos al perdedor, sin movimientos.
Durante la reconstrucción, los números identifican a las personas. No indican sus futuros puestos ganadores. En el círculo del laboratorio, los ganadores verdes están juntos al principio; los perdedores azules esperan separados y se reinsertan uno a uno. Los puestos ganadores son el resultado del procedimiento, no un dato inicial.
Un ejemplo pequeño: N = 4, K = 3
Usamos V = 1 ganador, P = 3 perdedores y K = 3. El ganador es la persona 1; los perdedores son las personas 2, 3 y 4. Empezamos solo con el 1. Insertamos el 2 y hacemos dos movimientos de la cola a la cabeza; luego repetimos con el 3 y el 4. La tabla muestra cada inserción y cada movimiento completado:
| Operación | Fila: números de las personas, de la cabeza a la cola |
|---|---|
| Reunir solo a los ganadores | 1 |
| Insertar al perdedor 2 en la cabeza | 2, 1 |
| Mover 1 de la cola a la cabeza (1 de 2) | 1, 2 |
| Mover 2 de la cola a la cabeza (2 de 2) | 2, 1 |
| Insertar al perdedor 3 en la cabeza | 3, 2, 1 |
| Mover 1 de la cola a la cabeza (1 de 2) | 1, 3, 2 |
| Mover 2 de la cola a la cabeza (2 de 2) | 2, 1, 3 |
| Insertar al perdedor 4 en la cabeza | 4, 2, 1, 3 |
| Mover 3 de la cola a la cabeza (1 de 2) | 3, 4, 2, 1 |
| Mover 1 de la cola a la cabeza (2 de 2) | 1, 3, 4, 2 |
La fila completa es 1, 3, 4, 2. Solo ahora asignamos los puestos: en el puesto 1 está la persona 1, en el 2 la persona 3, en el 3 la persona 4 y en el 4 la persona 2. Por tanto, el puesto ganador es el 1. Si empezamos a contar allí y eliminamos cada tercera persona, salen los puestos 3, 2 y 4: queda el puesto 1.
El cumpleaños: ¡siempre gano yo!
Estamos en una fiesta: 9 invitados más quien cumple años, por tanto N = 10. Cumple 12 años: elegimos K = 12 y un solo ganador, V = 1. Los invitados que eliminar son P = 9.
Reconstruimos el círculo y asignamos el puesto ganador a quien cumple años. Desde el puesto 1, en sentido horario gana el puesto 10; en antihorario, el puesto 2.
No es suerte: hemos elegido el resultado y preparado la posición adecuada. Para otra fiesta, fija P como número de invitados, V = 1 y K como los años cumplidos. Quien cumple años se suma a los invitados para obtener N.
Eliminaciones en sentido horario:
2, 5, 9, 6, 4, 8, 7, 3, 1
La pareja: dos ganadores elegidos
Somos 20 amigos y queremos que queden dos personas elegidas antes de jugar. Fijamos N = 20, V = 2, P = 18 y K = 11.
La reconstrucción hacia atrás encuentra los puestos para la pareja: en sentido horario, 9 y 15; en antihorario, 7 y 13. El recuento empieza siempre en el puesto 1.
Las dos personas pueden intercambiar entre sí los dos puestos ganadores. Esto no significa que puedan ganar dos puestos arbitrarios: son las posiciones calculadas las que garantizan el resultado.
Eliminaciones en sentido horario:
11, 2, 14, 6, 19, 13, 8, 4, 1, 20, 3, 7, 12, 18, 16, 17, 10, 5
Dos grupos de 15 personas
Otro ejemplo usa dos grupos de 15 personas: V = 15, P = 15, N = 30 y K = 9. El método no cambia: empezamos con 15 ganadores y reinsertamos a 15 eliminados. Los puestos ganadores son:
Horario
1, 2, 3, 4, 10, 11, 13, 14, 15, 17, 20, 21, 25, 28, 29
Antihorario
1, 3, 4, 7, 11, 12, 15, 17, 18, 19, 21, 22, 28, 29, 30
Reconstruir el círculo de 30 personas
Otro ejemplo: 2 ganadores y 28 perdedores
Con V = 2, P = 28 y K = 11, al principio reunimos solo a los ganadores 1 y 2. Los perdedores del 3 al 30 se insertan uno a uno. No se fija ningún puesto ganador de antemano. Al final numeramos los 30 puestos y, contando en sentido horario desde el puesto 1, obtenemos estos puestos ganadores:
18, 28
Probar 2 ganadores, 28 perdedores y eliminar cada 11
Cómo usar el laboratorio
- En Cartas elige N y el orden deseado. En Josephus indica cuántos ganadores y perdedores hay, K y el sentido, o carga un ejemplo.
- Usa Siguiente y Anterior para cada movimiento, Iniciar/Pausa para la animación y el deslizador para volver a un paso exacto. La velocidad inicial es de un segundo por acción; puedes cambiarla.
- Durante la reconstrucción de Josephus, observa el primer grupo dispuesto en círculo: empieza solo con los ganadores verdes. Los perdedores azules permanecen en la segunda lista durante el recuento animado y entran uno a uno sin volverse verdes. La forma circular representa el grupo en construcción, no puestos ya asignados.
- Al final aparece la fila de puestos, con los ganadores en verde. El puesto 1 es el origen del recuento del juego de eliminación. Comprobar hacia delante reproduce ese juego para verificar la disposición.
Abrir el laboratorio: cartas y Josephus, hacia delante y hacia atrás
Qué hemos aprendido
Con las cartas reconstruimos la baraja que produce el orden de salida deseado. Con Josephus empezamos solo con los ganadores reunidos y reinsertamos a los perdedores uno a uno. No imponemos sus posiciones ganadoras: las encontramos al final. Una vez numerada la disposición completa, el puesto 1 determina dónde empezar a contar para eliminar. La comprobación hacia delante confirma el resultado.