Rompecabezas de lógica común: explicación de los problemas de los caballeros y bribones, Monty Hall y los filósofos gastronómicos

Si bien no están estrictamente relacionados con la programación, los acertijos de lógica son un buen calentamiento para su próxima sesión de codificación. Puede encontrar un acertijo de lógica en su próxima entrevista técnica como una forma de juzgar sus habilidades para resolver problemas, por lo que vale la pena estar preparado.

En este artículo, hemos recopilado algunos acertijos de lógica famosos y sus soluciones. ¿Puedes resolverlos sin mirar la respuesta?

Caballeros y bribones

Para este rompecabezas de lógica, imagina que hay dos tipos de personas, caballeros y bribones. Los caballeros solo dicen la verdad, mientras que los bribones solo dicen mentiras.

Hay muchas variaciones de este rompecabezas, pero la mayoría implican hacer una pregunta para averiguar quién es el caballero y quién es el bribón.

Rojo y azul

Hay dos personas frente a ti, Roja y Azul. Blue dice: "Los dos somos bribones". ¿Quién es realmente el caballero y quién es el bribón?

Solución

Es imposible que Blue sea el caballero. Si Blue fuera un caballero, la afirmación, "Ambos somos bribones", en realidad sería una mentira. Por lo tanto, Azul es un bribón ya que su declaración es una mentira, y Rojo debe ser un caballero.

Dos caminos

Llega a una bifurcación en la carretera y debe elegir el camino correcto que lo lleve a su destino. Hay dos personas paradas en la bifurcación, y sabes que uno debe ser un caballero y el otro debe ser un bribón.

¿Qué pregunta podría hacerle a una de las personas para determinar el camino correcto, A o B?

Solución

La pregunta que puede hacer a cualquiera de las dos personas es: "¿Qué camino me diría la otra persona es el correcto?" La respuesta siempre será el camino equivocado a seguir, y puede tomar el otro camino con seguridad.

Imagina que el camino correcto es A.

Si pregunta directamente, "¿Cuál es el camino correcto?" el bribón dirá que B tiene razón, mientras que el caballero dirá A.

Sin embargo, cuando se le pregunte qué camino diría la otra persona que es correcto, el bribón mentirá y dirá que el caballero le dirá que el camino B es correcto. Mientras tanto, el caballero dirá la verdad sobre la respuesta del bribón y dirá que el bribón te dirá que el camino B es el correcto.

En ambos casos, sabes que la respuesta, el camino B, es en realidad una mentira, así que debes tomar el otro camino.

El problema de Monty Hall

El problema de Monty Hall es un acertijo de probabilidad que lleva el nombre del presentador del programa de juegos de los 70 en el que se basa, Hagamos un trato . Este problema en particular es una paradoja verídica, lo que significa que hay una solución que parece contraria a la intuición, pero que se ha demostrado que es cierta.

Imagina que estás en un programa de juegos y hay 3 puertas, cada una con un premio diferente detrás de ellas. Detrás de una de las tres puertas hay un coche. Detrás de las otras dos puertas hay cabras.

Debes elegir una de las 3 puertas para seleccionar como tu premio.

Supongamos que decide abrir la puerta 1. El anfitrión, que sabe dónde está el coche, abre una puerta diferente, la puerta 2, que revela una cabra. Luego le pregunta si desea abrir la Puerta 3 en su lugar.

¿Debería elegir la Puerta 3 en lugar de su elección original? ¿Incluso importa?

Solución

Resulta que su elección realmente importa, y en realidad es beneficioso para usted elegir la Puerta 3 en lugar de la Puerta 1. He aquí por qué.

Cuando eligió la Puerta 1 de las 3 puertas cerradas, tenía 1 de cada 3 posibilidades de elegir la correcta. Tanto la Puerta 2 como la Puerta 3 también tienen 1 de cada 3 posibilidades de tener un automóvil detrás.

Otra forma de pensarlo es que las Puertas 2 y 3 tienen una probabilidad de 2 sobre 3 de tener un automóvil detrás combinado .

Pero cuando el anfitrión abre la Puerta 2 y revela la cabra, de repente tienes más información sobre el problema.

Recuerde que las puertas 2 y 3 tienen una probabilidad combinada de ocultar el automóvil 2/3 de las veces. Cuando se abrió la puerta 2, usted sabe que no había ningún automóvil detrás.

Pero esta revelación no cambia la probabilidad combinada de las dos puertas. ¡Esa es la conclusión clave aquí!

Como sabe que la puerta 2 tiene una probabilidad de 0/3 de ocultar el automóvil, ahora puede decir que hay una probabilidad de 2/3 de que el automóvil esté detrás de la puerta 3. La puerta 1 permanece sin cambios; solo hay un tercio del automóvil. Detrás de eso.

Entonces, si decide cambiar, pasa de aproximadamente un 33,33% de probabilidad a un 66,67% de posibilidades de encontrar el automóvil. En otras palabras, estás duplicando tus posibilidades de éxito al abrir la Puerta 3.

Sí, es posible que la Puerta 1 se haya estado escondiendo todo el tiempo y el anfitrión te haya engañado. Eso no importa. Estás apostando aceptando el trato, pero estás apostando inteligentemente. Debes tomar la mejor decisión con la información que te dan y dejar que los dados rueden.

A la larga, obtendrás mejores resultados si cambias que un concursante que decida elegir su primera opción. Aunque no es obvio de inmediato, el anfitrión en realidad te está haciendo un favor al ofrecerte un mejor trato.

El problema de los filósofos gastronómicos

El problema de los filósofos de la cena es un ejemplo clásico de la informática para ilustrar problemas con la sincronización. Fue creado originalmente por Edsger Dijkstra en 1965, quien lo presentó a sus estudiantes como un puñado de computadoras que compiten por el acceso a unidades de cinta compartidas.

Imagine cinco filósofos silenciosos sentados alrededor de una mesa, cada uno con un plato de espaguetis. Hay tenedores sobre la mesa entre cada par de filósofos adyacentes.

Cada filósofo solo puede hacer una cosa a la vez: pensar y comer. Sin embargo, un filósofo solo puede comer espaguetis cuando tiene los tenedores derecho e izquierdo. Un tenedor solo puede ser sostenido por un filósofo a la vez.

Una vez que un filósofo termina de comer, debe dejar las horquillas izquierda y derecha para que estén disponibles para los demás. Un filósofo puede tomar un tenedor tan pronto como esté disponible, pero solo puede comenzar a comer una vez que tenga ambos tenedores.

Los filósofos son famosos por sus apetitos: todos pueden comer sin cesar y nunca llenarse. Además de eso, los tazones de espagueti se reponen mágicamente sin importar cuánto se coma.

El problema es, ¿cómo se puede asegurar que ningún filósofo se muera de hambre y que puedan seguir comiendo y pensando para siempre?

Sincronización y interbloqueo

En términos simples, el problema de los filósofos de la cena es una ilustración de cómo el acceso sincronizado a un recurso compartido puede resultar en la creación de una situación de punto muerto.

La sincronización se utiliza para controlar el acceso simultáneo a un recurso compartido. Esto es necesario en cualquier situación en la que múltiples actores independientes puedan estar compitiendo por el uso de un recurso como las bifurcaciones. Dado que solo hay un recurso disponible, utilizamos la sincronización para evitar confusiones y caos.

Un interbloqueo es un estado del sistema en el que no es posible avanzar. Esta situación puede ocurrir cuando se aplica la sincronización y muchos procesos terminan esperando un recurso compartido que está siendo retenido por algún otro proceso. Al igual que con los filósofos que están atrapados comiendo o pensando, los procesos simplemente siguen esperando y no se ejecutan más.

Soluciones

A primera vista, parece que no sería posible para un punto muerto en el que todos los filósofos están estancados comiendo o pensando. Por ejemplo, el patrón a seguir por cada filósofo podría ser:

1: piense hasta que la bifurcación izquierda esté disponible; cuando lo esté, recógelo;

2: piense hasta que esté disponible la bifurcación correcta; cuando lo esté, recógelo;

3: cuando se sostienen ambos tenedores, coma durante un tiempo fijo;

4: luego, baje el tenedor derecho;

5: luego, baje la horquilla izquierda;

6: repite desde el principio.

Fuente: Wikipedia

Hay muchas soluciones posibles para evitar el estancamiento. Si miramos de cerca, un problema en el algoritmo anterior es que todos los filósofos tienen las mismas posibilidades (tienen la misma prioridad) de adquirir una bifurcación. Esto evita que alguien adquiera dos bifurcaciones y todo el sistema se detiene.

A continuación, se muestran algunas posibles soluciones:

  1. Prioridad : a algunos filósofos se les asigna una prioridad más alta, por lo que se incrementa la posibilidad de adquirir ambas bifurcaciones.
  2. Prevención (cortesía): los filósofos abandonan el tenedor adquirido sin comer, en caso de que el otro tenedor no esté disponible.
  3. Arbitraje : un mediador asigna tenedores asegurándose de que se le den dos tenedores a una persona, en lugar de uno a muchas.

Ahora que sabe cómo resolver estos acertijos de lógica, disfrute de un plato interminable de espaguetis. Te lo has ganado.