Solución: Intercambiando el sitio en las cenas de Navidad

¡Feliz Navidad a todos!

Damos un descanso a nuestros estómagos entre turrón y turrón para contaros la solución al acertijo de la semana. Aunque en realidad ¡¡las soluciones que dieron nuestros lectores están bien!! Esto demuestra que podemos subir la dificultad de los acertijos, porque no sólo han acertado… también parece que alguno lo mandó al juez on-line de la Universidad de Valladolid porque ya hay 60 personas que tienen el problema aceptado 🙂 ¡Enhorabuena!

En esta ocasión, os proponíamos un acertijo que podía servir como tema de conversación para las sobremesas de las comidas y cenas de Navidad. En concreto consistía en averiguar el mínimo número de intercambios en las posiciones de comensales adyacentes en una mesa para conseguir que todos tuvieran a su izquierda a la persona que tenían originalmente a la derecha, y viceversa. Os pusimos unos cuantos ejemplos, y os preguntábamos por el número de cambios necesarios en una mesa de 7 comensales, una de 10 y una de 20.

David acertó el primero y nos puso su solución en Python, que luego mejoró usando una fórmula. Gualterio amplió la respuesta añadiendo nuevas preguntas 🙂 y nos regaló una expresión todavía más resumida. ¡Enhorabuena a los dos!

Como siempre, para el resto de nuestros silenciosos lectores, toca hoy explicar la solución. En realidad, estamos seguros de que hay varios razonamientos para llegar a ella, y el nuestro no tiene por qué ser el mejor, el más corto o el más fácil de entender… Si alguien ha llegado a la solución usando un razonamiento más sencillo, le animamos a que nos lo cuente en los comentarios. En cualquier caso, un aviso… Esta entrada es un poco larga, porque hemos intentado contarlo todo despacio y con detalle para no dejar flecos sueltos, pero el razonamiento es más fácil de lo que la longitud del texto daría a entender en principio 🙂 Dicho esto… basta de charla y… ¡vamos allá!

Lo que vamos a hacer es ir poniendo los intercambios necesarios para tamaños de mesa cada vez más grandes, e iremos haciendo «tablas resumen» de todos los resultados conocidos, para buscar un patrón que nos ayude a averiguar la «fórmula general». Los primeros términos son fáciles… Si en la mesa no hay nadie o sólo hay una persona, no hay posibilidad de intercambios 🙂 Si hay dos personas, como tanto a su izquierda como a su derecha tienen al mismo comensal, tampoco es necesario intercambiar a nadie para que el orden sea el contrario. Por tanto, la tabla resumen inicial que nos proponemos rellenar es muy sencilla:

Nº comensales	Intercambios
0	0
1	0
2	0

El número de intercambios necesarios con tres personas lo pusimos como ejemplo en la explicación del acertijo. En la siguiente tabla, ponemos en cada fila una configuración de la mesa, y vamos resaltando los comensales que se han intercambiado respecto a la configuración anterior. Os recordamos que la mesa es redonda, por lo que el último comensal tiene a su lado al primero. En realidad, con sólo tres comensales la tabla es muy corta:

Paso	Comensales
0	A	B	C
1	B	A	C

Si en la primera configuración los comensales están colocados A,B,C (de izquierda a derecha), en la última lo están A,B,C de derecha a izquierda, por lo que cada uno tendrá a su izquierda el que antes tenía a su derecha y viceversa, tal y como queríamos. Por tanto, con tres comensales necesitamos un único intercambio:

Nº comensales	Intercambios
0	0
1	0
2	0
3	1

El caso con cuatro comensales también lo pusimos el otro día como ejemplo:

Paso	Comensales
0	A	B	C	D
1	B	A	C	D
2	B	A	D	C

Si rellenamos la tabla global:

Nº comensales	Intercambios
0	0
1	0
2	0
3	1
4	2

Lo importante del caso de 4 comensales es que hemos pasado por la configuración de 3. Fijáos que en el paso 1 (tras un intercambio) hemos tenido a los comensales colocados en el orden BAC, justo la configuración final (y correcta) del caso de tres comensales. Esto lo vamos a aprovechar para el siguiente paso. Para invertir el orden de 5 comensales, ABCDE, nos preocuparemos inicialmente de colocar a los 4 primeros, que ya sabemos hacerlo de manera mínima, y luego nos preocuparemos del quinto. Fijáos que la aparición del comensal E no puede hacer que seamos capaces de colocar los 4 primeros de manera más óptima; en todo caso nos molestaría añadiendo más intercambios al «ponerse en medio». Por tanto nos aprovecharemos de que sabemos la mejor forma de colocar los cuatro primeros, y luego nos preocuparemos del quinto. El inicio por tanto será:

Paso	Comensales
0	A	B	C	D	E
2	B	A	D	C	E

Para ahorrar espacio (algo que agradeceremos más adelante), no se han puesto todos los pasos para colocar a los cuatro primeros comensales. Vemos que en los primeros pasos (dos) colocamos a esos cuatro, y nos queda el quinto, que tendremos que colocar entre el comensal A y el D. Para eso, tenemos que hacer irremediablemente dos intercambios. De nuevo, hay que darse cuenta de que no es posible colocar a los cuatro primeros de una manera más eficiente (el quinto comensal sólo complica las cosas). Los nuevos intercambios quedan:

Paso	Comensales
0	A	B	C	D	E
2	B	A	D	C	E
3	B	A	D	E	C
4	B	A	E	D	C

Rellenando la tabla general:

Nº comensales	Intercambios
0	0
1	0
2	0
3	1
4	2
5	4

Vamos ahora con un caso importante, el de 6 comensales. Como acabamos de hacer, primero colocamos a los 5 primeros:

Paso	Comensales
0	A	B	C	D	E	F
4	B	A	E	D	C	F

Tras 4 movimientos, tenemos a los 5 primeros comensales bien colocados (si no fuera por F, estarían todos en sentido inverso del original) y toca mover a F para colocarlo entre A y E. En el caso anterior lo hicimos moviéndolo hacia la izquierda, pero si hacemos eso necesitaremos tres intercambios. Es mejor desplazarlo hacia la derecha, para poderlo hacer así en solo dos intercambios, igual que antes. Esto nos da una primera regla: salvo para menos de 4 comensales, colocar al nuevo comensal nos supone sólo dos movimientos más respecto a los que se hicieron para el caso anterior, independientemente de cuantos hubiera, pues no es necesario recorrerlos todos.

Ahora bien, hay una cosa importante que no podemos pasar por alto. Al colocar al comensal F estamos ahorrándonos desplazamientos al ir hacia la derecha. Pero cuando añadamos un nuevo comensal (y tengamos 7), a la derecha del comensal F tendremos uno más. Por tanto, al colocar a F en el caso de 7 comensales ya no nos ahorraremos nada yendo hacia la derecha, y el atajo desaparecerá. Es decir, aunque sea adelantarnos, si tuviéramos 7 comensales y acabáramos de colocar a los 5 primeros estaríamos en esta situación:

Paso	Comensales
0	A	B	C	D	E	F	G
4	B	A	E	D	C	F	G

Colocar a F aquí nos cuesta 3 intercambios vayamos por donde vayamos, y no 2. De hecho, si añadimos un octavo comensal, entonces lo eficiente vuelve a ser ir hacia la izquierda para hacer tres intercambios en lugar de cuatro (por culpa del hipotético octavo comensal, H). Es por tanto importante recordar que en el caso de 6 comensales estamos tomando un atajo que nos ahorra un intercambio que no podremos ahorrarnos en los casos siguientes. Por tanto, añadimos una nueva columna a nuestra tabla general:

Nº comensales	Intercambios	Ahorros por atajo
0	0
1	0
2	0
3	1
4	2
5	4
6	6	1 (F)

Al añadir el séptimo comensal, el atajo desaparece, y el intercambio que nos ahorramos se incrementa al número de intercambios para colocar a los 6 primeros:

Paso	Comensales
0	A	B	C	D	E	F	G
6+1	B	A	F	E	D	C	G

Para colocar a G necesitamos, yendo por la derecha, solo dos movimientos. Pero en esta ocasión estamos ahorrándonos 2, porque si fuéramos hacia la izquierda tendríamos que hacer 4 intercambios. En la tabla general, por tanto, el atajo de F se ha difuminado (y ha incrementado en 1 el número de intercambios), pero aparece uno nuevo, el de G, que se ahorra dos desplazamientos:

Nº comensales	Intercambios	Ahorros por atajo
0	0
1	0
2	0
3	1
4	2
5	4
6	6	1 (F)
7	9	2 (G)

Ya sabemos que con 8 comensales, colocar a F (el sexto) es mejor hacerlo hacia la izquierda, con 3 movimientos. Colocar a G sigue siendo mejor hacerlo hacia la derecha, pero nos costará uno más que antes (al haberse puesto H en medio). Aun así, seguimos ahorrándonos un movimiento:

Paso	Comensales
0	A	B	C	D	E	F	G	H
9+1	B	A	G	F	E	D	C	H

Colocar al nuevo comensal, H, nos cuesta dos movimientos como siempre (por la derecha), pero ahora nos estamos ahorrando tres. A cambio, la cantidad de ahorro por G ha bajado en uno (y ha incrementado en 1 el coste de colocar a los 7 primeros):

Nº comensales	Intercambios	Ahorros por atajo
0	0
1	0
2	0
3	1
4	2
5	4
6	6	1 (F)
7	9	2 (G)
8	12	1 (G), 3 (H)

Si continuáis con este razonamiento, podréis llenar la tabla general con más casos, y es fácil encontrar un patrón:

Nº comensales	Intercambios	Ahorros por atajo
0	0
1	0
2	0
3	1
4	2
5	4
6	6	1 (F)
7	9	2 (G)
8	12	1 (G), 3 (H)
9	16	2 (H), 4 (I)
10	20	1 (H), 3 (I), 5 (J)
11	25	2 (I), 4 (J), 6 (K)
12	30	1 (I), 34 (J), 5 (K), 7 (L)

Fijaos que en el paso de 8 a 9 comensales hemos pasado de hacer 12 movimientos a hacer 16. Dos movimientos son debidos al desplazamiento del nuevo comensal hacia la derecha. Los otros dos son por el incremento de la colocación de G y H, en los que estábamos aprovechándonos del atajo hacia la derecha. Al tener un nuevo comensal más, el atajo supone un desplazamiento más, que hay que sumar.

Venga, que ya casi lo tenemos 🙂 Vamos a completar la tabla añadiendo la diferencia entre el paso anterior y el actual. Es decir, ¿cuántos intercambios más tenemos para n comensales respecto a los que teníamos para n-1?

Nº com.	Interc.	Ahorros por atajo	Incremento
0	0
1	0		0
2	0		0
3	1		1
4	2		1
5	4		2
6	6	1 (F)	2
7	9	2 (G)	3
8	12	1 (G), 3 (H)	3
9	16	2 (H), 4 (I)	4
10	20	1 (H), 3 (I), 5 (J)	4
11	25	2 (I), 4 (J), 6 (K)	5
12	30	1 (I), 3 (J), 5 (K), 7 (L)	5

Después de todo esto, finalmente, lo importante es la última columna, que nos dice los incrementos. Éstos son 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, … El número de intercambios para 6 comensales resulta ser:

0 + 0 + 1 + 1 + 2 + 2 = 2 × (0 + 1 + 2)

Para 12:

0 + 0 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 = 2 × (0 + 1 + 2 + 3 + 4 + 5)

¿Os resulta familiar? Esto resulta ser el doble de los números triangulares, de los que ya hablamos hace algunas semanas por aquí. Aunque hay que tener cuidado en los casos impares (donde no se ha «completado» el segundo número triangular completo), no es demasiado difícil sacar una forma de obtener el número de intercambios sin necesidad de pintar todo el proceso para saber qué intercambios son esos y contarlos. David, en su primera solución, calculaba los números triangulares con un bucle, y luego pasó a utilizar una fórmula. Gualterio también nos dio su fórmula, que, aunque diferente, da los mismos resultados que la de David. Nosotros la hemos simplificado aún más (Gualterio tenía una suma condicional a la paridad del número) y os confesaremos que basta con (n / 2) × ((n-1) / 2) donde las dos divisiones deben ser enteras (sin decimales).

Uséis la expresión que uséis veréis que, como nos dijo David, con 7, 10 y 20 comensales se necesitan 9, 20 y 90 intercambios. Gualterio también acertó al decir que con 25, se necesitan 144 y con 30, se necesitan 210. Y finalmente David tiró la casa por la ventana con 2³⁰ comensales, que necesitarían 288.230.375.614.840.832 intercambios.

Esperamos que hayáis llegado hasta aquí y hayáis entendido nuestro razonamiento 🙂 Si vosotros usasteis otro (quizá incluso más sencillo), ¡contádnoslo!

¡Hasta el próximo!