Alice eligió un entero positivo $n$ y Bob trata de adivinar.
En cada vuelta, Bob va a adivinar un número entero $x$ $(x>0)$:
Si $x$ es igual a $n$, entonces Alice le dice a Bob que la encontró, y el juego termina.
Si no, entonces Alice le dice a Bob si $x+n$ es primo o no.
Cómo jugar a este juego de forma óptima (es decir, para encontrar el número en el menor número de vueltas)?
Usted puede asumir $0< n\le100$ (o cualquier razonable enlazado).
PS: Este juego es inventado por mí.
No es posible resolver el juego en todos los casos con menos de 7 conjeturas, porque después de 6 adivina usted tiene por lo menos el 95 unguessed números y 6 bits de información e $2^6<94.$
Pero en realidad 7 no es alcanzable, ya que en la mayoría de los 26 números primos pueden aparecer en cualquier bloque de 101. Así, la primera conjetura, en el peor de los casos, tendrá al menos 74 números restantes, y así al menos 8 de las conjeturas son necesarios desde $2^6<68$.
El objetivo en cada paso es encontrar los números que se dividen los números restantes en dos conjuntos de aproximadamente el mismo tamaño. Aquí están los inicios de una estrategia para el 9. Pregunte acerca de 3. Si el número es 3 está hecho; si n + 3 es un número primo que no debe ser difícil de adivinar el número en 8 intentos más.
De lo contrario, 74 números siguen siendo: 1, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23, 24, 25, 27, 29, 30, 31, 32, 33, 35, 36, 37, 39, 41, 42, 43, 45, 46, 47, 48, 49, 51, 52, 53, 54, 55, 57, 59, 60, 61, 62, 63, 65, 66, 67, 69, 71, 72, 73, 74, 75, 77, 78, 79, 81, 82, 83, 84, 85, 87, 88, 89, 90, 91, 92, 93, 95, 96, 97, 99. Ahora pregunte sobre 10. Si n+10 es primo debe ser fácil de encontrar el número en más de 7 intentos.
De lo contrario el 50 números siguen siendo: 5, 6, 11, 12, 15, 17, 18, 22, 23, 24, 25, 29, 30, 32, 35, 36, 39, 41, 42, 45, 46, 47, 48, 52, 53, 54, 55, 59, 60, 62, 65, 66, 67, 71, 72, 74, 75, 77, 78, 81, 82, 83, 84, 85, 88, 89, 90, 92, 95, 96. Ahora pregunte sobre 12. Si n es 12 está hecho; si n+12 es primo tiene 6 intenta encontrar de 16 números.
Ahora 33 números siguen siendo: 6, 15, 18, 22, 23, 24, 30, 32, 36, 39, 42, 45, 46, 48, 52, 53, 54, 60, 62, 65, 66, 72, 74, 75, 78, 81, 82, 83, 84, 88, 90, 92, 96. Ahora pregunte acerca de 1. Si n+1 es primo hay 15 posibilidades y tienes 5 intentos.
Ahora acaba de 18: 15, 23, 24, 32, 39, 45, 48, 53, 54, 62, 65, 74, 75, 81, 83, 84, 90, 92. Esto es un poco complicado, pero supongo que 1139 (o 1148) para dividir el resto en dos grupos de 9.
De cualquier manera que vaya al menos uno de los conjuntos tiene 5 miembros (4 sería posible sólo si se ha seleccionado uno de los 18).
Tengo bastante fresco, pero probablemente poco práctico a la solución.
Considere la posibilidad de esta tabla de números primos de$1$$110$:
$$ \begin{matrix} 2 & 3 & 5 & 7 & 11 \\ 13 & 17 & 19 & 23 & 29 \\ 31 & 37 & 41 & 43 & 47 \\ 53 & 59 & 61 & 67 & 71 \\ 73 & 79 & 83 & 89 & 97 \\ 101 & 103 & 107 & 109 \\ \end{de la matriz} $$
Observe las diferencias entre todos los números primos. La tabla quedaría así:
$$ \begin{matrix} 2 & 1 & 2 & 2 & 4 \\ 2 & 4 & 2 & 4 & 6 \\ 2 & 6 & 4 & 2 & 4 \\ 6 & 6 & 2 & 6 & 4 \\ 2 & 6 & 4 & 6 & 8 \\ 4 & 2 & 4 & 2 \\ \end{de la matriz} $$
Echemos un vistazo a las combinaciones de 6 diferencias en orden. Están ordenados de izquierda a derecha y de arriba a abajo por su valor como si las secuencias representadas dígitos de un número de 6 dígitos:
$$1,2,2,4,2,4 \ \ \ \ \ \ \ \ \ \ 2,1,2,2,4,2 \ \ \ \ \ \ \ \ \ \ 2,2,4,2,4,2$$ $$2,4,2,4,2,4 \ \ \ \ \ \ \ \ \ \ 2,4,2,4,6,2 \ \ \ \ \ \ \ \ \ \ 2,4,6,2,6,4$$ $$2,4,6,6,2,6 \ \ \ \ \ \ \ \ \ \ 2,6,4,2,4,6 \ \ \ \ \ \ \ \ \ \ 2,6,4,2,6,4$$ $$2,6,4,6,8,4 \ \ \ \ \ \ \ \ \ \ 4,2,4,2,4,6 \ \ \ \ \ \ \ \ \ \ 4,2,4,6,2,6$$ $$4,2,4,6,6,2 \ \ \ \ \ \ \ \ \ \ 4,2,6,4,6,8 \ \ \ \ \ \ \ \ \ \ 4,6,2,6,4,2$$ $$4,6,6,2,6,4 \ \ \ \ \ \ \ \ \ \ 4,6,8,4,2,4 \ \ \ \ \ \ \ \ \ \ 6,2,6,4,2,4$$ $$6,2,6,4,2,6 \ \ \ \ \ \ \ \ \ \ 6,4,2,4,6,6 \ \ \ \ \ \ \ \ \ \ 6,4,2,6,4,6$$ $$6,4,6,8,4,2 \ \ \ \ \ \ \ \ \ \ 6,6,2,6,4,2 \ \ \ \ \ \ \ \ \ \ 6,8,4,2,4,2$$
Aviso de que no hay dos secuencias son iguales en la lista de arriba
Empezar a iterar sobre los valores de $x$ $[0,7]$ gradualmente hasta alcanzar el primer número primo. Deja este valor de $x$ se denota como $k$.
El paso anterior requiere de $8$ conjeturas en el peor de los casos
Usted tiene que usar los nuevos valores de $x$ igual a $k + o$ donde $o$ es un desplazamiento que se inicia en $1$ y cambios en función de lo principal y lo que no.
Si $k + 1$ es primo, se puede parar. $n = 2$.
Otra cosa, intente $k + 2$ y si eso no funciona, $k + 4$,$k + 6$.
Si, por ejemplo, $k + 4$, a continuación, intente $k + 4 + 2$. Si ese es el primer demasiado, y luego continuar con estas combinaciones de la misma manera:
$$4,2,4,2,4,6$$ $$4,2,4,6,2,6$$ $$4,2,4,6,6,2$$ $$4,2,6,4,6,8$$
Utilizando el método anterior, se deriva el valor de la primer $n + k$. $k$ es conocido, por lo que inmediatamente puede deducir el valor de $n$.
De hecho, podemos optimizar que por encima de la tabla de diferencias para eliminar los innecesarios ensayos y combinar algunos de ellos:
$$ \begin{matrix} 1 & 2,1 & 2,2 \\ 2,4,2,4,2 & 2,4,2,4,6 & 2,4,6,2 \\ 2,4,6,6 & 2,6,4,2,4 & 2,6,4,2,6 \\ 2,6,4,6 & 4,2,4,2 & 4,2,4,6,2 \\ 4,2,4,6,6 & 4,2,6 & 4,6,2 \\ 4,6,6 & 4,6,8 & 6,2,6,4,2,4 \\ 6,2,6,4,2,6 & 6,4,2,4 & 6,4,2,6 \\ 6,4,6 & 6,6 & 6,8 \\ \end{de la matriz} $$
La magia de los números para agregar a $k$ cuando adivinar sería:
$$ \begin{matrix} 1 & 2,3 & 2,4 \\ 2,6,8,12,14 & 2,6,8,12,18 & 2,6,12,14 \\ 2,6,12,18 & 2,8,12,14,18 & 2,8,12,14,20 \\ 2,8,12,18 & 4,6,10,12 & 4,6,10,16,18 \\ 4,6,10,16,22 & 4,6,12 & 4,10,12 \\ 4,10,16 & 4,10,18 & 6,8,14,18,20,24 \\ 6,8,14,18,20,26 & 6,10,12,16 & 6,10,12,18 \\ 6,10,16 & 6,12 & 6,14 \\ \end{de la matriz} $$
Es imperativo que los ensayos se realizan en orden de izquierda a derecha y de arriba a abajo en esta tabla, de lo contrario, obtendrá información falsa. Un ejemplo de optimización es evitar conjeturas cuando la única combinación posible para continuar con es 1 porque nosotros sabemos que $n + k$ es primo.
Un ejemplo:
El último paso es redundante. Si $k + 16$ es compuesto, se puede omitir el $k + 18$ paso porque usted sabe que va a ser el primer.
Espero que esto sea lo suficientemente clara.
Para obtener un poco algoritmo eficiente, lo primero que se puede calcular de varias opciones de $x$ lo que las respuestas de Alice sería, para cada elección de $n$$1$$100$.
Como señaló Charles, no importa lo $x$ es, en la mayoría de las $26$ de la $100$ opciones posibles de $n$ la respuesta sea "Sí, $n + x$ es primo". Esta tasa máxima de información se logra sólo por la elección de $x = 1$, por lo que se quiere hacer esta pregunta como nuestra primera pregunta. Hay cinco opciones de $x$ para los que no se $25$ números donde la respuesta es "Sí", que se $2, 3, 4, 9, 10$. Por simplicidad, supongamos que tenemos la primera consulta de la primera $4$ números con una alta "tasa de información": $$x \in \{1, 2, 3, 4\}.$$ Ahora, para cada elección de $n$, podemos calcular lo que las respuestas hubieran sido. Para los números de $n = 1, 2, 3, 4$ tendríamos un partido y hacer, mientras que para los otros $96$ números no son sólo $7$ posibles secuencias de respuestas. Junto con las opciones de $n$ que conducen a estas respuestas, estas secuencias son: $$\begin{align} NNNN &: \{23, 24, 31, 32, 47, 48, 53, 54, 61, 62, 73, 74, 83, 84, 89, 90, 91, 92\} \\ NNNY &: \{7, 13, 19, 25, 33, 37, 43, 49, 55, 63, 67, 75, 79, 85, 93, 97\} \\ NNYN &: \{8, 14, 20, 26, 34, 38, 44, 50, 56, 64, 68, 76, 80, 86, 94, 98\} \\ NYNN &: \{5, 11, 17, 21, 29, 35, 41, 45, 51, 59, 65, 71, 77, 81, 87, 95\} \\ YNNN &: \{6, 12, 18, 22, 30, 36, 42, 46, 52, 60, 66, 72, 78, 82, 88, 96\} \\ NYNY &: \{9, 15, 27, 39, 57, 69, 99\} \\ YNYN &: \{10, 16, 28, 40, 58, 70, 100\} \end{align}$$ Así que con $4$ preguntas, nos permite reducir el espacio de búsqueda en la mayoría de los $18$ números. Para cada grupo, se puede ser capaz de elegir las preguntas de seguimiento, de tal manera que en total, se puede necesitar sólo acerca de $10$ preguntas o así, pero esto va a ser muy complicado. Por supuesto, podríamos consulta de cada uno de los en la mayoría de las $18$ números en cada uno de los grupos, para un total de más de $4 + 18 = 22$ preguntas, pero que, evidentemente, no será óptimo.
Un poco más simple estrategia sería hacer más preguntas en la etapa inicial, tales como consultar primero $$x \in \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}.$$ En este caso, no se $48$ cadenas posibles de respuestas (y $10$ coincidencias exactas), y cada grupo contiene a $3$ o menos de los valores de $n$ que conducen a estas respuestas. Así que una vez que sabemos las respuestas a estas $10$ de las consultas, que son capaces de reducir el espacio de búsqueda en la mayoría de los $3$ números, y con en la mayoría de las $2$ preguntas que se puede, a continuación, ser capaz de determinar el valor correcto de $n$. Así que esto podría llevar a un peor de los casos la complejidad de $10 + 2 = 12$ preguntas.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
