¿Cuál es la forma óptima de tomar $16$ ¿una prueba de verdadero/falso con cuatro intentos?

Question

Pregunta:

Supongamos que un estudiante está cursando un $16$ -Prueba de verdadero/falso con cuatro intentos. Deben conservar la tienda que obtengan después del cuarto intento.

No sabe la respuesta a ninguna pregunta. Una vez terminada la prueba, el calificador le dice cuántas ha acertado, pero no cuáles.

¿Cuál es la mejor manera de maximizar el valor esperado del cuarto intento?

---

Mis pensamientos:

Así que, para aclarar la pregunta, una forma de hacer que el valor esperado sea igual a $9.5$ es la siguiente:

Intento 1: Responder a la pregunta $1$ y dejar el resto en blanco. Si el calificador te dice que tienes $1$ Bien, ya sabes la respuesta a la pregunta $1$ con certeza. Si el calificador te dice que tienes $0$ correcto, entonces todavía sabe la pregunta a $1$ con certeza (si pones verdadero, entonces será falso).

Intento 2: Repite con la pregunta 2.

Intento 3: Repite con la pregunta 3.

Por lo tanto, nos garantizamos tres preguntas correctas, y el valor esperado para el cuarto intento es $3 + \sum_{i=1}^{13}1 \cdot 1/2 = 3 + 6.5 = 9.5$ . Así que se espera que consigamos $9.5$ de la derecha.

---

Otra cosa que podría hacer alguien es responder "VERDADERO" a cada pregunta del intento $1$ . Eso te dirá cuántas preguntas de verdadero/falso hay en total. A continuación, en el segundo intento, deja la segunda mitad de la prueba en blanco y responde VERDADERO a todo lo que hay en la primera mitad. Esto es una especie de búsqueda binaria. Te dice cuántas son verdaderas en la primera mitad, y en el primer cuarto, etc.

No conseguí nada con esto.

¿Es mi solución de un valor esperado de $9.5$ ¿la solución más óptima? ¿Y si hubiera $3$ intentos en lugar de $4$ ?

Answer 1

Aquí hay una estrategia que supera a la suya:

Intento 1 : Responde al azar a las preguntas 1-5 y deja el resto en blanco.

Intento 2 : Responde al azar a las preguntas 6-10 y deja el resto en blanco.

Intento 3 : Responde al azar a las preguntas 11-15 y deja el resto en blanco.

Prueba final : Para las preguntas 1-5 dé las mismas respuestas que en el intento 1, excepto que invierta todas ellas si tuvo menos de 3 correctas. Del mismo modo, para las preguntas 6-10 y 11-15. Conteste la pregunta 16 al azar.

Esto le garantiza al menos 3 respuestas correctas en cada grupo de 5, y alguna probabilidad de incluso más. Si estoy calculando correctamente el esperado número de derechos en cada grupo es $3\frac{7}{16}$ para una expectativa total de $3\cdot 3\frac{7}{16} + \frac12 = 10\frac{13}{16}$ .

Answer 2

No sé si son óptimas, pero son ligeramente mejores que las otras respuestas. La estrategia general es empezar adivinando "Verdadero" para todas las preguntas en el primer intento, como sugeriste al final de tu pregunta. Las siguientes conjeturas subdividirán la prueba en intervalos, y en la conjetura final podemos tomar lo mejor de cada intervalo (es decir, mantener nuestras conjeturas o voltearlas si menos de la mitad del intervalo fueron correctas).

Por otro lado, no has especificado la distribución de las respuestas, por lo que un examinador malintencionado podría intentar engañarnos eligiendo las respuestas de forma que el algoritmo diera el peor resultado posible. Pero podemos evitar esto simplemente adivinando al azar en lugar de "Verdadero"; para simplificar, entonces, vamos a suponer que las respuestas son independientes e idénticamente distribuidas.

Utilicemos $[a]$ para denotar la pregunta $a$ y $[a,b]$ para denotar preguntas $a$ a través de $b$ . Además, deja que $C_k$ sea el número de aciertos en el $k$ la suposición. Por simetría, podemos suponer que al menos la mitad de las conjeturas en cualquier intervalo son correctas.

Se permiten 2 aciertos: $9.571$

La información resultante de la primera suposición es suficiente para permitirle obtener una puntuación esperada de $9.571$ en su segunda suposición. Esto ya es mejor que la estrategia de cuatro suposiciones que propusiste.

Se permiten 3 aciertos: $10.367$

Si $C_1 = 16$ obtenemos todos los puntos.

Si $10 \le C_1 \le 15$ entonces usa la siguiente conjetura para ver sólo una pregunta, $[1]$ . Tenemos garantizado al menos $C_1$ puntos; si tenemos suerte, conseguiremos $C_1+1$ . (Suerte significa que nos equivocamos en $[1]$ y por lo tanto puede voltearlo para obtener un punto más).

Por otro lado, si $C_1 = 8$ o $9$ , entonces utiliza la siguiente conjetura para ver $[1,7]$ . Por el principio de encasillamiento, esto garantiza al menos $4 + 5 = 9$ puntos; de hecho, si se calculan las posibilidades, el número esperado de puntos es $9.713$ y $9.885$ para $C_1 = 8$ y $C_1 = 9$ respectivamente.

Se permiten 4 aciertos: $11.086$

Si $11 \le C_1 \le 15$ , entonces adivina $[1,2]$ siguiente. Si $C_2 = 1$ entonces podemos garantizar un punto más adivinando $[1]$ ; si no es así, adivina $[3]$ .

Si $C_1 = 10$ , adivina $[1,6]$ siguiente.

Si $C_1 = 9$ , adivina $[1,8]$ siguiente.

Si $C_1 = 8$ , adivina $[1,5]$ siguiente.

He omitido los detalles de estos tres últimos casos, pero puedo añadirlos si quieres. En resumen, una regla general para las conjeturas posteriores sería dividir un gran intervalo ambiguo por la mitad cuando sea posible ("ambiguo" significa que alrededor de la mitad de las respuestas eran correctas, por lo que no tenemos tanta información útil como nos gustaría y no podemos ganar mucho al voltear nuestras conjeturas).

---

Posdata: por lo que sé, siempre es beneficioso adivinar primero todo el conjunto de preguntas, en lugar de dividirlas en tercios, como en la respuesta de Henning Makholm / JMoravitz. Dicho esto, esa estrategia sigue funcionando bien y tiene la ventaja de ser sencilla.

Answer 3

Mis dos centavos sobre el problema.

1. Divide los problemas en secciones en las que quieras adivinar.
2. Si la conjetura anterior no aportó mucha información (resultados de alta varianza que nos permitirían acertar el máximo), incluya esa conjetura en este lote de conjeturas.

Así que aquí está cómo lo abordaría. 1. Adivinar todas las T del 1 al 5. Si obtenemos 0, 1, 4 o 5, dejamos el espacio en blanco en el siguiente intento porque obtendremos al menos 4/5 correctos en esta sección (aunque si realmente quieres, incluye la obtención de 4 o 1 correcto en el siguiente intento). Sin embargo, si obtenemos 3 aciertos, entonces

2. Adivina TTTFF en los problemas 1-5, adivina todas las T en los 6-10.

Ahora tiene un 0,3% de posibilidades de acertar los 10, un 1,6% de posibilidades de acertar los 9, un 5% de posibilidades de acertar los 8, un 12,5% de posibilidades de acertar los 7, un 21,2% de posibilidades de acertar los 6, un 23,8% de posibilidades de acertar los 5, un 18,8% de posibilidades de acertar los 4, un 11,2% de posibilidades de acertar los 3, un 4,7% de posibilidades de acertar los 2 y un 0,9% de posibilidades de acertar los 1.

Ahora, a partir de esta distribución, tenemos una buena información de nuestra conjetura anterior sobre el 1-5 y esta conjetura actual también. Si acertamos el 10, conocemos todos los 1-10.

Si acertamos el 9, sabemos con seguridad que hemos acertado los 5 primeros y 4/5 en el 6-10.

Si acertamos 8, la probabilidad condicional de que TTTFF sea la respuesta a las 5 primeras es (1/10*10/32)/(1/10*10/32+1/32*6/10) = 63%.

Si acertamos 7, la probabilidad condicional de que hayamos acertado los 5 primeros es sólo del 25%, mientras que hay un 75% de posibilidades de que hayamos acertado 4/5 del 6 al 10 y hayamos acertado 3 del 1 al 5.

Es una estrategia muy similar a la de otros que han publicado antes, que consiste en dividir en 3 secciones y dar la vuelta, pero siempre tratando de maximizar la información mediante el análisis de la distribución de probabilidad condicional. Esto debería obtener un valor esperado más alto.