¿Cuál es el problema lógico más difícil que has encontrado? Sea lo suficientemente amable como para mencionar la solución también.

El problema lógico más difícil que conozco se llama acertadamente “El problema lógico más difícil jamás” por George Boolos.

Planteamiento del problema

Se declara de la siguiente manera:
Tres dioses A, B y C se llaman, sin ningún orden en particular, Verdadero, Falso y Aleatorio. True siempre habla de verdad, False siempre habla de manera falsa, pero si Random habla de manera verdadera o falsa es una cuestión completamente aleatoria. Su tarea es determinar las identidades de A, B y C haciendo tres preguntas de sí a no; cada pregunta debe hacerse exactamente a un dios. Los dioses entienden inglés, pero responderán todas las preguntas en su propio idioma, en el que las palabras para sí y no son da y ja , en algún orden. No sabes qué palabra significa cuál.
Boolos proporciona las siguientes aclaraciones:

• Podría ser que a algún dios se le haga más de una pregunta (y, por lo tanto, a algún dios no se le hace ninguna pregunta).
• Cuál es la segunda pregunta, y a qué dios se dirige, puede depender de la respuesta a la primera pregunta. (Y, por supuesto, de manera similar para la tercera pregunta).
• Si Random habla de verdad o no, debe considerarse que depende del lanzamiento de una moneda escondida en su cerebro: si la moneda cae cara abajo, habla de verdad; si colas, falsamente.

Solución

Boolos proporcionó su solución en el mismo artículo en el que introdujo el rompecabezas. Boolos afirma que “el primer movimiento es encontrar un dios del que puedas estar seguro que no es aleatorio y, por lo tanto, es verdadero o falso”. [1] Hay muchas preguntas diferentes que lograrán este resultado. Una estrategia es utilizar conexiones lógicas complicadas en sus preguntas (ya sea bicondicionales o alguna construcción equivalente).
La pregunta de Boolos fue preguntarle a A:
¿Quiere decir sí si eres falso si B es aleatorio?
Equivalentemente:
¿Es cierto un número impar de las siguientes afirmaciones: usted es falso, da significa que sí , B es aleatorio?
Roberts (2001) e Rabern y Rabern (2008) observaron de forma independiente que la solución del rompecabezas se puede simplificar mediante el uso de ciertos contrafácticos. La clave de esta solución es que, para cualquier pregunta sí / no Q, hacer la pregunta Verdadero o Falso
Si te preguntara Q, ¿dirías ja ?
da como resultado la respuesta ja si la respuesta veraz a Q es sí , y la respuesta da si la respuesta veraz a Q es no (Rabern y Rabern (2008) llaman a este resultado el lema de la pregunta incrustada). La razón por la que funciona se puede ver al observar los ocho casos posibles.

• Suponga que ja significa sí y da significa no .

1. True se pregunta y responde con ja . Como él está diciendo la verdad, la respuesta veraz a Q es ja , lo que significa que sí .
2. True se pregunta y responde con da . Como él está diciendo la verdad, la respuesta veraz a Q es da , lo que significa que no .
3. Falso se le pregunta y responde con ja . Como él está mintiendo, se deduce que si le preguntas a Q, él responderá a da . Él estaría mintiendo, por lo que la respuesta veraz a Q es ja , lo que significa que sí .
4. Falso se pregunta y responde con da . Como él está mintiendo, se deduce que si le preguntaras a Q, él respondería de hecho a ja . Él estaría mintiendo, por lo que la respuesta veraz a Q es da , lo que significa que no .

• Suponga que ja significa no y da significa sí .

1. True se pregunta y responde con ja . Como él está diciendo la verdad, la respuesta veraz a Q es da , lo que significa que sí .
2. True se pregunta y responde con da . Como él está diciendo la verdad, la respuesta veraz a Q es ja , lo que significa que no .
3. Falso se le pregunta y responde con ja . Como él está mintiendo, se deduce que si le preguntaras a Q, él respondería de hecho a ja . Él estaría mintiendo, por lo que la respuesta veraz a Q es da , lo que significa que sí .
4. Falso se pregunta y responde con da . Como él está mintiendo, se deduce que si le preguntas a Q, él responderá a da . Él estaría mintiendo, por lo que la respuesta veraz a Q es ja , lo que significa que no .

Independientemente de si el dios preguntado está mintiendo o no e independientemente de qué palabra significa sí y cuál no , puede determinar si la respuesta veraz a Q es sí o no . Sin embargo, si el dios está respondiendo al azar, la respuesta a la pregunta aún no tiene sentido.

La solución a continuación construye sus tres preguntas utilizando el lema descrito anteriormente.

1. Pregúntale al dios B: “Si te preguntara ‘¿Es aleatorio?’, ¿Dirías ja ?”. Si B responde a ja , B es aleatorio (y responde aleatoriamente) o B no es aleatorio y la respuesta indica que A es aleatorio. De cualquier manera, C no es aleatorio. Si B responde da , B es aleatorio (y responde aleatoriamente) o B no es aleatorio y la respuesta indica que A no es aleatorio. De cualquier manera, conoces la identidad de un dios que no es aleatorio.
2. Dirígete al dios que fue identificado como no aleatorio por la pregunta anterior (ya sea A o C), y pregúntale: “Si te preguntara ‘¿Eres falso?’, ¿Dirías ja ?”. Como no es Aleatorio, una respuesta de da indica que es Verdadero y una respuesta de ja indica que es Falso.
3. Pregúntale al mismo dios la pregunta: “Si te preguntara ‘Is B Random?’, Dirías ja ?”. Si la respuesta es ja , B es aleatorio; si la respuesta es da , el dios con el que aún no has hablado es Aleatorio. El dios restante puede ser identificado por eliminación.

Fuente: Wikipedia

He conocido a bastantes personas que estudian o han estudiado lógica filosófica a nivel de posgrado que estaban desconcertados por este tipo de problema (si es que no lo habían oído antes, eso es; la mayoría de ellos sí), así que creo que si bien es Siempre es difícil clasificar algo como “el problema más difícil”, sin duda es un buen candidato para este puesto. 🙂

Muy bien, recibí esta pregunta en una pregunta de examen final de algoritmos recientemente y creo que es interesante, así que la publicaré. Siéntase libre de eliminar cualquier error que pueda haber cometido.

Planteamiento del problema

Supongamos que tengo un gráfico G y ejecuto el algoritmo de Kruskal en ese gráfico para obtener MST T y luego tomar G, compensar todos sus pesos de borde por algún positivo k> 0 para producir G ‘. Ejecutemos Kruskal’s nuevamente en G ‘para obtener un MST T’ ¿el conjunto de bordes de T ‘sería idéntico a T? Por qué o por qué no

Mi respuesta

Mi respuesta a esa pregunta es un sí y hay una elegante “prueba” detrás.

La razón detrás de mi lógica es la siguiente: consideramos cómo funciona el algoritmo de Kruskal, esencialmente tomamos todos nuestros pesos de borde y los clasificamos en orden ascendente, luego implementamos una estructura de datos Union Find para fusionar los componentes conectados según sea necesario. Si compensamos todos los bordes por k, el algoritmo de Kruskal seguirá considerando los bordes en el mismo orden relativo que los bordes en el gráfico original de una manera codiciosa y de la misma manera T y T ‘producirán conjuntos de bordes idénticos.