Skip to content

Intercambiando el sitio en las cenas de Navidad

by en 23/12/2013

¡Hola a todos!

Ya están aquí las vacaciones de Navidad, y todos tenemos un poquito más de tiempo para dedicarnos a nuestras aficiones… de modo que… ¡vamos con la nuestra!

El otro día, en una de las habituales cenas que se realizan por estas fechas, estábamos seis amigos en un restaurante alrededor de una mesa redonda, esperando que nos sirvieran los postres. Quizá fuera inspirado por la comilona o, más probablemente, aguijoneado por los vapores del alcohol, alguien lanzó un absurdo reto al aire. Básicamente quería que consiguiéramos estar sentados de tal manera que todos tuviéramos a nuestra derecha a quien en ese momento teníamos a nuestra izquierda, y viceversa. Para conseguirlo, lo único que podíamos hacer era intercambiar nuestra posición con alguien que tuviéramos al lado. Y, obviamente, teníamos que conseguirlo con el menor número de intercambios posible.

Todos empezamos a intercambiar el sitio con otros, en un caos de movimientos y sillas arrastrándose que no nos llevó a nada útil. Cuando finalmente llegaron los postres, nadie estaba sentado donde debía, y fue tal el desbarajuste que organizamos que el dueño del restaurante nos pidió amablemente que no volviéramos por allí.

Con la claridad mental que da estar sobrio, la pregunta es en realidad fácil de entender. Si la mesa tiene, por ejemplo, únicamente 3 comensales:

A
C B

basta con que dos cualquiera se intercambien para que el orden se haya dado la vuelta:

C
A B

Fíjate que en la primera configuración, el orden de los comensales en el sentido de las agujas del reloj es ABC. Tras un único cambio de dos personas adyacentes, en la segunda configuración el orden en sentido inverso de las agujas del reloj es también ABC. Las posiciones concretas de cada comensal no importan; lo único importante son las posiciones relativas.

Con una mesa para cuatro personas se necesitan dos cambios. Como antes, destacamos los comensales que se han movido en cada paso:

A B            B A            B A
D C            D C            C D

De nuevo, en la primera configuración el orden es ABCD en el sentido de las agujas del reloj, y en la última es ABCD pero en sentido opuesto.

Para 6 comensales, como éramos el otro día, hay que hacer 6 movimientos (¡¡quién lo hubiera dicho, con la que liamos!!). Por comodidad, pondremos los “nombres” de los comensales todos seguidos; recuerda que es una mesa redonda, por lo que el último tiene a su lado al primero.

Paso Comensales
0 A B C D E F
1 B A C D E F
2 B A D C E F
3 B A D E C F
4 B A E D C F
5 F A E D C B
6 A F E D C B

Al principio (“paso 0”) los comensales están colocados en el orden A-F de izquierda a derecha. En el primer paso, aparecen destacados los comensales B y A por ser los que han cambiado de sitio. Merece especial atención el paso 5, en el que se intercambian las posiciones los comensales B y F. Como dijimos antes, dado que la mesa es redonda el comensal del extremo derecho de la tabla está en realidad al lado del situado en el extremo izquierdo. Al final, tras 6 cambios, los comensales están en el orden A-F pero de derecha a izquierda.

Nuestras preguntas de hoy son fáciles de esperar. ¿Cuál es el mínimo número de movimientos para una mesa de 7 comensales? ¿Y de 10? ¿Y de 20?

Tened en cuenta que, como muchos estaréis de vacaciones, nos hemos atrevido con un acertijo un poquito más difícil de lo habitual (pero no mucho más 🙂 ). La parte buena es que el planteamiento no sólo es muy fácil de entender, sino que además puede ser un tema de conversación y de entretenimiento durante las sobremesas de las comidas y cenas de Navidad. De modo que si no das con la solución ¡¡reta a tus familiares y amigos durante los postres, a ver si alguno te ayuda!! 🙂 El acertijo se presta perfectamente a eso… y si os animáis, quizá terminéis todos moviéndoos alrededor de la mesa, como nos pasó a nosotros 🙂

¡Ah! Y si al final das con la solución y la programas, puedes probarla aquí. ¡Y esta vez el reto tiene premio! En el momento de escribir estas líneas, sólo hay 59 personas en el mundo que lo han resuelto… ¿te atreves a ser el 60?

Anuncios

From → Difíciles, Problemas

4 comentarios
  1. David permalink

    Después de darle unas cuantas vueltas (a la mesa), me parece haber visto la luz! =)
    Espero no estar precipitándome..
    7 chairs = 9
    10 chairs = 20
    20 chairs = 90

    http://www.codeskulptor.org/#user28_wveFntDzMsRSd8m.py

  2. Gualterio permalink

    ¡Muy divertido el acertijo!

    Yo también creo que lo tengo… y estoy de acuerdo con David 🙂
    Me tiro a la piscina con otras dos mesas distintas. Para una mesa de 25, se necesitan 144. Y para una mesa de 30, se necesitan 210 intercambios.
    A ver si hemos acertado!

    Feliz navidad a todos…

  3. David permalink

    Bueno se me ocurrió una fórmula para calcularlo de manera más eficiente (como viene siendo necesario en los concursos).

    http://www.codeskulptor.org/#user28_wveFntDzMsRSd8m_0.py

  4. Gualterio permalink

    Vaaale, dejo yo también la fórmula a la que llegué yo 😉

    Para una mesa de N sillas: (N/2) * ( (N/2) – 1) + (N/2)*(N mod 2).

    O lo que es lo mismo, (N/2) * ((N/2) – 1) y a eso sumarle (N/2) si N es impar.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: