Dadas 10 afirmaciones relacionadas entre sí, ¿cuál es el número máximo de afirmaciones verdaderas?

Question

Dadas 10 afirmaciones relacionadas entre sí, ¿cuál es el número máximo de afirmaciones verdaderas?

lógica
rompecabezas
Matemáticas
optimización discreta

Lê Thanh Đạt

(No sé si esto se puede clasificar como una pregunta de matemáticas real . Siéntase libre de eliminar esto si no califica).

Dadas las siguientes afirmaciones,
$\begin{aligned} 1. & Al menos cinco de las afirmaciones enumeradas a continuación son verdaderas. \\ 2. & Al menos cuatro de las afirmaciones enumeradas a continuación son falsas. \\ 3. & Al menos tres de las afirmaciones enumeradas a continuación son verdaderas. \\ 4. & Al menos dos de las afirmaciones enumeradas a continuación son falsas. \\ 5. & Al menos una de las afirmaciones enumeradas a continuación es verdadera. \\ 6. & Al menos una de las afirmaciones enumeradas anteriormente es falsa. \\ 7. & Al menos dos de las afirmaciones enumeradas anteriormente son verdaderas. \\ 8. & Al menos tres de las afirmaciones enumeradas anteriormente son falsas. \\ 9. & Al menos cuatro de las afirmaciones enumeradas anteriormente son verdaderas. \\ 10 & Al menos cinco de las afirmaciones enumeradas anteriormente son falsas. \end{aligned}$ $\begin{align} 1. &\text{ At least five of the statements listed below are true.}\\ 2. &\text{ At least four of the statements listed below are false.}\\ 3. &\text{ At least three of the statements listed below are true.}\\ 4. &\text{ At least two of the statements listed below are false.}\\ 5. &\text{ At least one of the statements listed below is true.}\\ 6. &\text{ At least one of the statements listed above is false.}\\ 7. &\text{ At least two of the statements listed above are true.}\\ 8. &\text{ At least three of the statements listed above are false.}\\ 9. &\text{ At least four of the statements listed above are true.}\\ 10. &\text{ At least five of the statements listed above are false.}\\ \end{align}$ Siempre que las declaraciones verdaderas proporcionen información respaldada por evidencia y las declaraciones falsas proporcionen información que contradiga la evidencia, ¿cuál es el número máximo de declaraciones verdaderas?

Correcto, en primer lugar, supongamos que hay exactamente cuatro afirmaciones falsas entre $(3)$ y $(10)$ . (Debo aclarar que siempre que "entre $(a)$ y $(b)$ " se menciona, se aplica a todas las declaraciones $(n)$ dónde $a \le n \le b$ .) Las otras cuatro afirmaciones entre $(3)$ y $(10)$ son verdaderas y, además, declaración $(2)$ es correcto. Esto significa que hay exactamente cinco afirmaciones verdaderas entre $(2)$ y $(10)$ y declaración $(1)$ por lo tanto es correcto.

Habiendo identificado las condiciones dadas en declaraciones $(1)$ y $(2)$ se cumplen, también podemos inferir que la afirmación $(7)$ es verdadera, y de la que se infiere esa afirmación $(5)$ también es cierto Consulte esta lógica nuevamente y las dos siguientes declaraciones correctas que se encuentran son $(9)$ y $(3)$ en ese orden.

Hasta ahora, seis afirmaciones tienen que demostrar ser ciertas: $(1) - (2) - (3) - (5) - (7) - (9)$ (que consisten en todas las declaraciones relacionadas con el número de declaraciones verdaderas y una declaración en la que basamos nuestra hipótesis). Esto elimina la posibilidad de que haya cinco o más afirmaciones correctas entre $(1)$ y $(9)$ , por lo tanto, declaración $(10)$ es falsa, lo que implica declaración $(5)$ es verdad. Siguiendo con esta lógica, las condiciones presentadas en declaraciones $(7)$ y $(9)$ no se cumplen, por lo que podemos confirmar su falsedad.

Al final, hay tres declaraciones falsas: $(6) - (8) - (10)$ , lo que contradice la hipótesis presupuesta de que hay "exactamente cuatro enunciados verdaderos entre $(3)$ y $(10)$ ". (¿Por qué tiene que terminar de esta manera? Iba tan bien~)

Empecemos al revés. Suponga que hay exactamente cuatro enunciados verdaderos entre $(1)$ y $(8)$ , las otras cuatro afirmaciones entre $(1)$ y $(8)$ son falsos Sin embargo, de acuerdo con esta hipótesis, la afirmación $(9)$ no es incorrecta, lo que significa que la afirmación $(10)$ Es falso. Como estamos buscando el número máximo de declaraciones verdaderas, supondremos que hay un mínimo de cuatro declaraciones verdaderas entre $(1)$ y $(8)$ , reafirmando esa declaración $(9)$ es correcta y afirmación $(10)$ Es incorrecto.

De este punto de partida, podemos deducir que la afirmación $(5)$ es verdad, (¿no empieza a parecerse a nuestro primer caso? Declaraciones $(5) - (9) - (10)$ son de hecho lo mismo), y en realidad, eso es todo. Técnicamente podemos ir más lejos si se nos ocurren más suposiciones, pero me detendré aquí por ahora.

¿Qué tal si repasamos nuestra primera hipótesis? Dado que estamos buscando el número máximo de declaraciones verdaderas, asumiremos que la declaración $(2)$ es falsa, lo que significa que la declaración $(1)$ es verdad. En realidad, saltémonos el tedioso razonamiento. He hecho una tabla que detalla el proceso que se necesita para decidir si cada declaración es verdadera de acuerdo con las afirmaciones anteriores. Esta es una de las configuraciones que proporciona información de apoyo a las afirmaciones verdaderas e información contradictoria a las falsas.

Pero, ¿es éste el caso que maximiza el número de enunciados verdaderos? ¿Hay alguna manera de probar que una combinación con más de siete declaraciones verdaderas no es lógicamente alcanzable? ¿Qué pasa con uno con la mayor cantidad posible de declaraciones falsas? Supongo que es básicamente lo contrario a la configuración anterior: $\text{T} - \text{F} - \text{T} - \text{F} - \text{F} - \text{F} - \text{F} - \text{F} - \text{F} - \text{T}$ .

Respuestas (3)

Dadas 10 afirmaciones relacionadas entre sí, ¿cuál es el número máximo de afirmaciones verdaderas?

bram28 · Answer 1

Si tuviera ocho o más afirmaciones verdaderas, entonces tendría como máximo dos afirmaciones falsas y, por lo tanto, 2, 8 y 10 tienen que ser todas falsas... ¡lo que contradice que tendría como máximo dos afirmaciones falsas!

Entonces no, no puede tener ocho o más declaraciones verdaderas.

Ahora, encontraste una solución con exactamente siete declaraciones verdaderas. ¿Hay otras soluciones con 7 declaraciones verdaderas? No, porque con 7 afirmaciones verdaderas, sabemos que 2 y 10 son falsas (de nuevo: no hay suficientes afirmaciones falsas), pero con 3 afirmaciones falsas y 10 ya siendo falsas, 8 puede tener como máximo dos afirmaciones falsas encima, y así 8 tiene que ser Falso también. Entonces, 2, 8 y 10 tienen que ser falsos si hay 7 declaraciones verdaderas, por lo que esta es la única solución con 7 declaraciones verdaderas.

Bien, pero ¿qué pasa con maximizar el número de declaraciones falsas?

Primero, tenga en cuenta que su solución para False's

$\text{T} - \text{F} - \text{T} - \text{F} - \text{F} - \text{F} - \text{F} - \text{F} - \text{F} - \text{T}$

¡No funciona del todo! Si usamos su distribución para evaluar las afirmaciones, ¡tendríamos que solo 9 y 10 tienen el valor de verdad correcto! Así que no, no puedes simplemente 'invertir' la solución aquí.

Bien, ¿cuántos falsos podemos tener?

Tenga en cuenta que tener seis o más afirmaciones falsas hace que 2, 4, 6, 8 y 10 se conviertan todas en verdaderas... y así inmediatamente ya no puede tener seis o más afirmaciones falsas. Por lo tanto, no puede tener seis o más declaraciones falsas.

Está bien, pero ahora considere: si 1 es falso, entonces 1 tiene como máximo cuatro declaraciones verdaderas debajo de él y, por lo tanto, al menos cinco declaraciones falsas debajo de sí mismo, lo que da un total de al menos seis declaraciones falsas. Pero ya establecimos que eso es imposible, entonces no puedo ser Falso. Entonces, sabemos que 1 tiene que ser Verdadero. Pero eso obliga a que 3, 5, 7 y 9 también sean verdaderos. Y eso a su vez obliga a 10 a ser Falso. Ahora, si 8 fuera verdadero, 2, 4 y 6 tendrían que ser todos falsos, pero ahora tenemos un problema con 4. Entonces, 8 es falso. Eso obliga a 4 a ser Verdadero. Eso hace que 2 sea Falso, y finalmente 6 tiene que ser Verdadero.

¡Entonces, de hecho, ahora hemos establecido que hay exactamente una y solo una posible solución a este rompecabezas!

Rob Pratt · Answer 2

Puede resolver el problema a través de la programación lineal entera de la siguiente manera. Para $i\in\{1,\dots,10\}$ , sea una variable de decisión binaria $x_i$ indicar si declaración $i$ es verdad. El problema es maximizar $\sum_{i=1}^{10} x_i$ sujeto a

\begin{aligned} X_{1} = 1 & ⟹ \sum_{i = 2}^{10} X_{i} \geq 5 \\ X_{2} = 1 & ⟹ \sum_{i = 3}^{10} (1 - X_{i}) \geq 4 \\ X_{3} = 1 & ⟹ \sum_{i = 4}^{10} X_{i} \geq 3 \\ X_{4} = 1 & ⟹ \sum_{i = 5}^{10} (1 - X_{i}) \geq 2 \\ X_{5} = 1 & ⟹ \sum_{i = 6}^{10} X_{i} \geq 1 \\ X_{6} = 1 & ⟹ \sum_{i = 1}^{5} (1 - X_{i}) \geq 1 \\ X_{7} = 1 & ⟹ \sum_{i = 1}^{6} X_{i} \geq 2 \\ X_{8} = 1 & ⟹ \sum_{i = 1}^{7} (1 - X_{i}) \geq 3 \\ X_{9} = 1 & ⟹ \sum_{i = 1}^{8} X_{i} \geq 4 \\ X_{10} = 1 & ⟹ \sum_{i = 1}^{9} (1 - X_{i}) \geq 5 \end{aligned}

$\begin{align} x_1 = 1 &\implies \sum_{i=2}^{10} x_i \ge 5 \\ x_2 = 1 &\implies \sum_{i=3}^{10} (1 - x_i) \ge 4 \\ x_3 = 1 &\implies \sum_{i=4}^{10} x_i \ge 3 \\ x_4 = 1 &\implies \sum_{i=5}^{10} (1 - x_i) \ge 2 \\ x_5 = 1 &\implies \sum_{i=6}^{10} x_i \ge 1 \\ x_6 = 1 &\implies \sum_{i=1}^5 (1 - x_i) \ge 1 \\ x_7 = 1 &\implies \sum_{i=1}^6 x_i \ge 2 \\ x_8 = 1 &\implies \sum_{i=1}^7 (1 - x_i) \ge 3 \\ x_9 = 1 &\implies \sum_{i=1}^8 x_i \ge 4 \\ x_{10} = 1 &\implies \sum_{i=1}^9 (1 - x_i) \ge 5 \end{align}$ Estas implicaciones lógicas se pueden linealizar de la siguiente manera:

\begin{aligned} (1) & \sum_{i = 2}^{10} X_{i} & \geq 5 X_{1} \\ (2) & \sum_{i = 3}^{10} (1 - X_{i}) & \geq 4 X_{2} \\ (3) & \sum_{i = 4}^{10} X_{i} & \geq 3 X_{3} \\ (4) & \sum_{i = 5}^{10} (1 - X_{i}) & \geq 2 X_{4} \\ (5) & \sum_{i = 6}^{10} X_{i} & \geq 1 X_{5} \\ (6) & \sum_{i = 1}^{5} (1 - X_{i}) & \geq 1 X_{6} \\ (7) & \sum_{i = 1}^{6} X_{i} & \geq 2 X_{7} \\ (8) & \sum_{i = 1}^{7} (1 - X_{i}) & \geq 3 X_{8} \\ (9) & \sum_{i = 1}^{8} X_{i} & \geq 4 X_{9} \\ (10) & \sum_{i = 1}^{9} (1 - X_{i}) & \geq 5 X_{10} \end{aligned}

$\begin{align} \sum_{i=2}^{10} x_i &\ge 5 x_1 \tag1 \\ \sum_{i=3}^{10} (1 - x_i) &\ge 4 x_2 \tag2 \\ \sum_{i=4}^{10} x_i &\ge 3 x_3 \tag3 \\ \sum_{i=5}^{10} (1 - x_i) &\ge 2 x_4 \tag4 \\ \sum_{i=6}^{10} x_i &\ge 1 x_5 \tag5 \\ \sum_{i=1}^5 (1 - x_i) &\ge 1 x_6 \tag6 \\ \sum_{i=1}^6 x_i &\ge 2 x_7 \tag7 \\ \sum_{i=1}^7 (1 - x_i) &\ge 3 x_8 \tag8 \\ \sum_{i=1}^8 x_i &\ge 4 x_9 \tag9 \\ \sum_{i=1}^9 (1 - x_i) &\ge 5 x_{10} \tag{10} \end{align}$ La única solución óptima resulta ser

x = (1, 0, 1, 1, 1, 1, 1, 0, 1, 0)

$x=(1,0,1,1,1,1,1,0,1,0)$ , con valor objetivo

7

$7$ . La relajación de programación lineal tiene un valor objetivo óptimo

23 / 3

$23/3$ , lo que implica un límite superior entero

⌊ 23 / 3 ⌋ = 7

$\lfloor 23/3 \rfloor = 7$ . Una solución dual óptima proporciona un breve certificado de optimización. Explícitamente, multiplique las restricciones

(6)

$(6)$ ,

(8)

$(8)$ , y

(10)

$(10)$ por

- 8 / 15

$-8/15$ ,

- 4 / 15

$-4/15$ , y

- 1 / 5

$-1/5$ , respectivamente, y agréguelos a las restricciones válidas

\frac{8}{15} x_{7} \leq \frac{8}{15}

$\frac{8}{15}x_7 \le \frac{8}{15}$ y

\frac{4}{5} x_{9} \leq \frac{4}{5}

$\frac{4}{5}x_9 \le \frac{4}{5}$ para obtener

\sum_{i = 1}^{10} x_{i} \leq \frac{23}{3}

$\sum_{i=1}^{10} x_i \le \frac{23}{3}$ .

Woah, ¡eso es realmente genial! Me pregunto cómo te diste cuenta de que efectivamente era $x = (1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0)$ , o más generalmente, solo quiero saber más sobre cómo funciona la programación lineal entera. Sé que mi amigo que se especializa en codificación utiliza esto en muchos de sus problemas (o eso es lo que me dijo al menos).
Oh, ohhh~ esas cosas existen. Bueno, esta pregunta se sacó de un examen, durante el cual una calculadora (y a veces un reloj porque algunas personas no saben cómo interiorizar su gestión del tiempo, supongo~) es el único dispositivo eléctrico permitido, lo que significa que puedo... En realidad, no use su solución en ese entorno. Pero gracias por darme una solución única, lo aprecio.

ross milikan · Answer 3

A menudo ayuda asumir lo más restrictivo porque es más fácil llegar a una contradicción y avanzar. Si asumimos que 5 es falso, entonces 6-10 son todos falsos y 10 nos dice que 1-5 debe ser falso. Entonces 1,3 son falsos y 2,4 son verdaderos, pero esto contradice que 7 sea falso, por lo que 5 es verdadero.

Ahora suponga que 6 es falso. Entonces 1-5 son todos verdaderos y 2 nos dice que 7-10 son falsos. Nuevamente 7 hace una contradicción, por lo que 6 es verdadero.

Esto hace que 7 sea verdadero, lo que hace que 3 sea verdadero, lo que hace que 9 sea verdadero, lo que hace que 1 sea verdadero. Entonces 10 es falso y 8 es falso. Eso hace que 4 sean verdaderos y 2 falsos. La única asignación consistente es 2,8,10 falsa y las demás verdaderas. Puede verificar que esto sea consistente con todos los datos.

Dadas 10 afirmaciones relacionadas entre sí, ¿cuál es el número máximo de afirmaciones verdaderas?

Lê Thanh Đạt

Respuestas (3)

bram28

Rob Pratt

Lê Thanh Đạt

Rob Pratt

Lê Thanh Đạt

ross milikan

¿Quién es el caballero, escudero y espía?

¿Cuál es el tipo de orden del conjunto de los números naturales, cuando se escriben en orden alfabético?

¿Cuántos platos se pueden colocar sobre la mesa de modo que no se superpongan entre sí ni sobre el borde de la mesa?

Análisis I (Terence Tao)—Variables libres y ligadas

Tratando de entender la pregunta en el ejercicio sobre las relaciones

Divertidos acertijos matemáticos para niños.

¿Es la teoría de los lenguajes formales regulares finitamente axiomatizable?

¿Es correcta esta notación de intervalo para la solución de un problema de desigualdad?

¿Qué sucede si la cabeza de una Máquina de Turing de Tiempo Infinito está en la celda más a la izquierda y el programa dicta que se mueva la cabeza hacia la izquierda?

Encontrar un universo adecuado para una estructura dada